# Equivalence relations

1. Feb 4, 2006

### kingerd

ok i don't know why i can't grasp this and i feel so stupid...

here's an example in the book which i do get...
Let S denote the set of all nonempty subsets of {1, 2, 3, 4, 5}, and define a R b to mean that a $$\cap$$ b not equal to $$\emptyset$$. The R is clearly reflexive and symmetric. Howerver, R is not transitive since {1, 2} R {2, 3} and {2, 3} R {3, 4} are true, but {1, 2] R {3, 4} is false

but here's two problems that i don't get where i have to state what the special propert(y/ies) are and state whether R is an equivalence relation on S

S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd
S = {1,2,3,4,5,6,7,8} and x R y means that |4 - x| = |4 - y|

2. Feb 4, 2006

### EnumaElish

You have to figure whether each of the properties you described in the "nonempty intersection" example holds for the new examples.

How do you/your textbook define an equivalence rel.?

3. Feb 4, 2006

### kingerd

for the two problems i don't have to determine if it's a nonempty intersction, i have to...

Determine which of the reflexive, symmetric, and transitive properties are satisfied by the given relation R defined on set S, and state whether R is an equivalence relation on S

S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd
S = {1,2,3,4,5,6,7,8} and x R y means that |4 - x| = |4 - y|

4. Feb 4, 2006

### HallsofIvy

Staff Emeritus
Reflexive: is x R x ? What is x- x?
Symmetric: if x R y is y R x? If x- y is odd, what is y- x?
Transitive: if x R y and y R z is x R z? If x- y and y- z are both odd, what can you say about x- z?

x R x?
if x R y is y R x? In other words, if you swap x and y in the formula above, is it still true?
if x R y and y R z, is x R z?

5. Feb 4, 2006

### kingerd

ok i think i understand that better. it would be symmetric because i can get an odd number, but reflexive and transitive don't always yield an odd number

6. Feb 7, 2006

### kingerd

ok i'm still having problems with this and i know i'm making it way harder then it needs to be

for instance here is a problem that's in the book and the solutions manual with the answer

S is the set of all real numbers and xRy means that $$x^2=y^2$$

The solution manual says that it's reflexive, symmetric and transitive,
but what makes it that and how do you find it?

7. Feb 7, 2006

### VietDao29

First, I suggest you should go back to your book, and look up the definitions for reflexive, symmetric and transitive, try to remember it, and try to understand some examples the book provides.
S is the set of all real numbers, and x R y means that : x2 = y2
---------------
1. Is it reflexive? Is x R x? Or in other word, is x2 = x2
2. Is it symmetric?
If x R y, then is y R x? Or in other word, if x2 = y2, is y2 = x2?
3. Is it transitive?
If x R y, and y R z, then is x R z? Or in other word, if x2 = y2, and y2 = z2, is x2 = z2?
------------
Can you get it now? :) Or are you still have some problem with it?

Last edited: Feb 7, 2006
8. Feb 7, 2006

### kingerd

ok let me ask this, i'm completely making this up so that i can get this... i mean what you posted helps, anyway...

if i have something like the following and i think this is where my misunderstanding of this is, because i've read the definitions of reflexive, symmetric, and transitive over and over, but i think the following is what i'm not grasping

if i have the following...
S={1, 2, 3, 4, 5, 6}

whate would be the x, y, and for transitive the z
1=x
2=y
3=z
????

9. Feb 7, 2006

### HallsofIvy

Staff Emeritus
Same thing as before:
Reflexive: xRx. Is x2= x2? Of course, it is! The relation is reflexive.

Symmetric: if xRy then yRx: If x2= y2 is y2= x2? Of course, it is!

Transitive: if xRy and yRz then xRz: If x2= y2 and y2= z2, is x2= z2? Of course, it is.

In fact, this just say "xRy if and only if some function of x equals some function of y" so it is really based on the fact that "= " (the prototypical "equivalence relation") is reflexive, symmetric and transitive.

10. Feb 7, 2006

### VietDao29

You forgot the relation, what's your relation?
Okay, lets have another example: let R be a relation on the real number set.
x R y means that: x > y.
Now:
Reflexive: Is x R x? Is x > x? (No, right?, 3 > 3 is false)
Symmetric: If x R y, then is y R x? Say x = 3, y = 2 (3 > 2 => 2 > 3, again wrong)
Transitive: If x R y, and y R z, then is x R z?
x > y, and y > z, we have:
x > y > z, so it implies that: x > z.
You can test it with x = 3, y = 2, z = -1.5
So it's transitive, right?
Overall, The relation ">" between real numbers is not an equivalence relation. Because it's transitive, but not symmetric, and reflexive.
Can you understand this?

Last edited: Feb 7, 2006
11. Feb 7, 2006

### kingerd

ok i see how that work, now if i use what i stated before
S={1, 2, 3, 4, 5, 6}

in what order would i plug in the values to x, y, and z?

would i just go from one to the other meaning
1 would be x
2 would be y
3 would be z

this is where i'm running into the confusion for some reason.

i understand what you posted with no problem it just in what order i guess that i'm having the problem with.

also thank you so much for helping me

12. Feb 7, 2006

### HallsofIvy

Staff Emeritus
What relation are you talking about? "Transitive", "symmetric", and "reflexive" are possible properties of a relation, not a set or members of that set.

A relation must say "xRy if and only if" some formula or other property involving x and y.
The relation is "reflexive" if and only if xRx for all x in the set: replace both x and y in the formula with x (or some other single letter representing any member of the set)- is the formula true?

The relation is "symmetric" if whenever xRy, also yRx: Assume the formula is true with x and y, swap x and y in the formula. Is it still true?

The relation is "transitive" if whenever xRy and yRz, also xRz. Assume that the formula is true with x and y and also true if y and z in place of x and y. Can you use those to prove that the formula is still true with x and z in place of x and y?

13. Feb 7, 2006

### kingerd

i'm talking about any relation. i understand what you are saying about the definitions to the 3 properties, but for instance the one problem i had posted a few posts ago

S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd

i realize that xRx isn't going to get me an odd number so i know it's not going to be reflexive

here's where i'm confused if i do xRy and the yRx if i'm only doing something like 2-3 or 3-2 i will get an odd number, but if i were to do 2-4 or 4-2 of course i'm not going to have an odd number. this is what i'm asking about with pluging in the values into x, y, and z, is there a specific order in which i plug in a value? i hope i'm making better sense

14. Feb 7, 2006

### HallsofIvy

Staff Emeritus
Okay since deciding if this relation is reflexive, symmetric, and transitive is still your homework problem, not mine, lets look at a slightly different example: xRy if and only if x- y is an even number.

Reflexive: xRx for all numbers.
Proof: x- x= 0 which is an even number. Yes, this relation is reflexive.

Symmetric: if xRy, then yRx
Proof: IF xRy, then x-y is even. yRx becomes y- x (since y and x have swapped places in yRx, they swap places in the definition of the relation).
Of course, y- x= -(x- y) and the negative of an even number is even. Yes, that's a symmetric relation.

Transitive: if xRy and yRz then xRz
Proof: If xRy, then x- y is even. If yRz, then y- z is even. To decide if xRz, we need to look at x-z. x- z= (x- y)+ (y- z) and so is the sum of two even numbers. Yes, the sum of two even numbers is even. The relation is transitive.

15. Feb 7, 2006

### kingerd

OMG thank you the light bulb finally went on... i'm soooo sorry for being a complete idiot, but thank you so much for helping... i understand it now:surprised