Equivalence Relations

[Ed Quanta]

I am not exactly clear on what an equivalence relation. If A is a set, then a relation on A is a subset R. The relation R is an equivalence relation on A if it satisfies the reflexive property, symmetric property, and transitive property. What types of relations are we talking about. And when could these relations ever not have these 3 properties. And what are equivalence classes? I need some simple examples to demonstrate this since none are really provided in this textbook.

[Muzza]

And when could these relations ever not have these 3 properties.


What are you asking? If there are equivalence relations not satisfying those properties? Obviously not, since then the relations wouldn't be equivalence relations.

Maybe you want an example of a relation that's not an equivalence relation. Cconsider the relation "less than" (<) on the real numbers. It is not symmetric, since for example, 3 < 4 doesn't imply 4 < 3.

[Ed Quanta]

What about reflexive

[matt grime]

it's not relflexive either, 3<3? Don't think so! But \leq is reflexive (and transitive) but not symmetirc again.

Equivalence relations are the generalization of the relation of being equal - whilst two elements are not the same, they may in share all the properties that you care about.

an equivalence realation on a set A is not a subset of A. It is just a relation, a rule for saying how/when two elements are related in some manner.

the equivalence class [x] of x in A is the subset of A of all elements that are 'related' to x. The rules for an equivalnce relation imply that if xRy, they [x]=[y] - ie equivalence classes are equal or disjoint.

Important examples are modulo arithmetic, conjugacy classes of groups, cosets of subgroups, defining quotient structures such as in the isomorphism theorems of algebra


here are several relations on Z

say xRy iff x=y+1

this not symmetric transitive or refelxive

xRy iff x<y this is only transitive


xRy iff x<=y is transitive and relfexive but not symmetric

xRy iff x is not equal to y is symmetric but neither reflexive nor transitive.

[Damned charming :)]

I think I have a really good way of explaining this so I would like comments.

My example of an equivalence relation is x and y have the same parity
in other words xRy is true when both x and y are odd. xRy is also true
when both x and y are even. If one of the variables x,y is odd or even then xRy false.

So xRy is true when x and y are the "same"(equivalent) in some respect. if xRy is true x and y have a specific common property.
Exactly what the common property is depends on the problem.
This explains all your rules.

symmetric
xRy => yRx
If x has a common property with y then y must have a common property with x.

reflexive
xRx
x and x must have a common propery!

transitive

xRy and xRz => yRz.
If x and y have a common property and x and z have a common property then y and z share a common property.

Now cleary an equivalence relation divides the set into distint subset where everything each subset has the same common property.

if you remember my original example where the equivalence relation is " both odd or both even" then two subsets are the even numbers and the odd numbers and xRy => x and y are in the same subset.

[Janitor]

In general, an n-ary relation (n a positive integer) R on a set A is a subset of the Cartesian product A x A x ... A (n times). Since the most commonly used relations are binary, we are usually dealing with relations that are a subset of A x A.

I just thought of a binary relation that is symmetric but not reflexive and not transitive: the relation "is perpendicular to" on the set of vectors in a real three-dimensional vector space.

[Janitor]

The binary relation "divides," on the set of positive integers (as in "5 divides 15, 5 does not divide 12") is reflexive and transitive, but not symmetric.

There are 8 possible "truth tables" (if I can use that terminology for this purpose) for a binary relation to fall into:

1) Reflexive, Symmetric, Transitive
2) Reflexive, Symmetric, not Transitive
...
8) not Reflexive, not Symmetric, not Transitive

We now have examples of some of those eight in this thread. Can anybody come up with examples of the others? I don't just mean ad hoc examples, such as: "A Bush-Kerry binary relation on the set (a, b, c) is given by the subset (<a,c>, <b,c>) (or in other terminology, aRc and bRc)" which is not reflexive, not symmetric, and not transitive. Here I am using < , > to mean ordered pair.

[Janitor]

The binary relation "is parallel to" on the set of vectors in a real three-dimensional vector space is reflexive, symmetric, and transitive.

[matt grime]

Let's do it on N. let R, S T be reflexive etc, and nR be the negations

(R)(S)(T):

x~y iff x=y


one negation:

(nR)(S)(T)
???


(R)(nS)(T)
x~y iff x<=y


(R)(S)(nT)
x~y iff x=y+1 or x=y-1 or x=y



two negations:

(nR)(nS)(T)
x~y iff x<y

(nR)(S)(nT)
x~y iff x is not equal to y.

(R)(nS)(nT)
x~y iff x=y or x=y+1

three negations:
(nR)(nS)(nT)
x~y iff x=y+1

[Janitor]

Now you've got me trying to come up with a relation (nR)(S)(T) on N.

By the way, if by N you mean the naturals, should we broaden it to the integers, to avoid lack-of-closure problems with x=y-1?

[matt grime]

fine, Z, N, whichever seems most appropriate to you it isn't important I don't beleive (I am not saying every possible relator of every number must exist)

[Hurkyl]

Well, if your relation is symmetric and transitive and you have x~y, then:

x~y
therefore y~x
therefore x~x

!

So in order for a relation to be symmetric, transitive, and not reflexive, you must have some element x that is not related to anything.

BTW, there are three classes for reflexivity and symmetry;

You have reflexive (\forall x:x\sim x), irreflexive (\forall x: \neg (x \sim x)), and neither.

You have symmetric (\forall x \forall y: x \sim y \Leftrightarrow y \sim x), antisymmetric (\forall x \forall y: x \sim y \wedge y \sim x \Rightarrow x = y), and neither.

[Janitor]

"I am not saying every possible relator of every number must exist."

Fair enough! I avoided zero in my "divides" example, but given your proviso, maybe I didn't need to. Thanks.

[Janitor]

Thanks Hurkyl for pointing out that "So in order for a relation to be symmetric, transitive, and not reflexive, you must have some element x that is not related to anything." I guess that is why it is hard to come up with an example that doesn't look ad hoc, for that particular case. And thanks for pointing out that one can usefully further subdivide some of my eight cases.

[Janitor]

As chance would have it, I came upon a definition today: A relation is total if for all x there exists a y such that xRy.

So my "divides" relation is a total relation on Z+ but not on Z.

[matt grime]

Is y allowed to be x? For then every reflexive relation is total.

[modmans2ndcoming]

Elements of the partition on A are subsets of A, and the Union of the partition is A and the intersection of the partition is NULL.

[Ed Quanta]

I have a question. For something like x=ymodn, how would you prove something which is intuitively obvious like for this relation, n distinct equivalence classes exist ([0],[1],...[n-1]).

[modmans2ndcoming]

you just need to show that if you have some Natural number x , that you infact have a partition.

so x can be in some set A and in some set B iff A = B.

how it is partitioned is not as important as showing that it is an equivilence relation because once you establish the EQ Relation on the set, you have no need to proove that a partition exists.

[Janitor]

"Is y allowed to be x? For then every reflexive relation is total." - Matt

Yes, I didn't see any restriction saying y had to be distinct from x. So you make a good point: every reflexive relation has to be a total relation.

[Janitor]

I am not sure if mathematicians use the term "antiparallel," but I think physicists do. I believe vectors A and B are said to be antiparallel by physicists if they point in opposite directions. So 'antiparallel' is a binary relation on a vector space which is not reflexive, is symmetric, is not transitive.

[modmans2ndcoming]

a reflexive relation is an equivilence relation because it is reflexive, and vaccuosly transative and vaccuosly symetric.

reflexivity is the only aspect that MUST have a component for all x in A.

[Janitor]

Modman, it almost sounds like you are claiming that all reflexive relations are equivalence relations, but we have given examples in this thread where that is not the case. I must be misunderstanding your point.

[matt grime]

a note for either ed or janitor, modman's replies seem eminently ignorable to be honest.

to show that the numbers 1,..n-1 form a complete set of equivalence classes mod n, one must only note that [p]=[q] iff n divides p-q, and if p an q are both less than n (and greater than zero) that that implies p=q

[modmans2ndcoming]

when I made the post, I had this type of reflexive set in mind:

{ (1,1) , (2,2) }

so I most certainly did not have all cases that are reflexive in mind.

I most certainly know that the class

{ (1,1), (2,2), (2,3) } is not an equivilence....but then if you read carfuly, you would see I used the term "vaccuos" in relation to symetric and transitive, meaning that no ordered pair (like the(2,3) I used above) exists in the set, so all elements are examples of reflexivity, nothing more.

reflexive is a bidirectional proposition, so you MUST have at least one ordered pair in the set, and it must represent for all x : (x,x)

but Symetric is an implication, so it the antecedent is false, it is symetric.

and Transitive is an implication so in the same way as symetric, it will be true.

[HallsofIvy]

Originally posted by modmans2ndcoming
when I made the post, I had this type of reflexive set in mind:

{ (1,1) , (2,2) }

so I most certainly did not have all cases that are reflexive in mind.

I most certainly know that the class

{ (1,1), (2,2), (2,3) } is not an equivilence....but then if you read carfuly, you would see I used the term "vaccuos" in relation to symetric and transitive, meaning that no ordered pair (like the(2,3) I used above) exists in the set, so all elements are examples of reflexivity, nothing more.

reflexive is a bidirectional proposition, so you MUST have at least one ordered pair in the set, and it must represent for all x : (x,x)

but Symetric is an implication, so it the antecedent is false, it is symetric.

and Transitive is an implication so in the same way as symetric, it will be true.

Then you should have said "identity relation" rather than "reflexive relation". What you orignally said was "a reflexive relation is an equivilence relation because it is reflexive, and vaccuosly transative and vaccuosly symetric."
The "vacuously" part did not clarify, it's just wrong: not all reflexive relations are transitive or symmetric.

[Janitor]

"Identity relation" sounds like a better term for what modman was talking about.

[HallsofIvy]

And, of course, the information that every "identity" relation (x is related to y if and only if x= y) is an equivalence relation is not news. Identity is the prototype of all equivalence relations.