# Equivalence Relations

1. ### Ed Quanta

297
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.

2. ### Muzza

695
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.

Last edited: Feb 29, 2004

297

4. ### matt grime

9,396
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.

5. ### Damned charming :)

63
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.

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.

6. ### Janitor

1,189
Hope this helps

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.

7. ### Janitor

1,189
Examples of binary relations

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.

Last edited: Mar 7, 2004
8. ### Janitor

1,189
Another binary relation

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

Last edited: Mar 12, 2004
9. ### matt grime

9,396
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

10. ### Janitor

1,189
Thanks Matt.

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?

Last edited: Mar 7, 2004
11. ### matt grime

9,396
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)

12. ### Hurkyl

16,090
Staff Emeritus
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.

Last edited: Mar 7, 2004
13. ### Janitor

1,189
"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.

Last edited: Mar 7, 2004
14. ### Janitor

1,189
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.

15. ### Janitor

1,189
Amplifying on something Matt said-

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.

16. ### matt grime

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

17. ### modmans2ndcoming

150
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.

18. ### Ed Quanta

297
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]).

19. ### modmans2ndcoming

150
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.

20. ### Janitor

1,189
"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.