Relation question PLEASE HELP!!

[frazza999]

I am really confused on what im asked for this question. A little bit of help would be great!

Question 1. Prove that the relation \(\displaystyle \sim\), given by \(\displaystyle x\, \sim\, y\) if and only if \(\displaystyle 4\) divides \(\displaystyle (x\, -\, y)\), is an equivalence relation on the set \(\displaystyle A\, =\, {0,\, 1,\, 2,\, ...,\, 20}\), and list the equivalence classes.

Thank you so much in advance!!

 

[Ishuda]

Let's do an example and see if that helps. You have a relation x^y if and only \(\displaystyle \lvert x \rvert=\lvert y \rvert\) on the set S = {-3, -2, -1, 0, 1, 2, 3, 4}.
Looking at this we see that -3^3, i.e. \(\displaystyle \lvert -3 \rvert=\lvert 3 \rvert\), -2^2, -1^1, 0^0, and 4^4 so the sets of elements which satisfy x^y are the elements of the set U={(-3, 3), (-2, 2), (-1, 1), (0), (4)}. Now notice that every element of S appears in a set of U only once (the intersection of any two sets of U is empty) and that the union of all the sets in U is the set S. Those two facts make the set U the set of equivalence classes under the relation ^ and show that ^ is an equivalence relationship. [Also note that formally, you must also prove ^ is a binary relationship satisfying reflexive, symmetric and transitive properties, see below]

Hint: Now 4 divides 20 - 16, 16 - 12, 12 - 8, 19 - 15, 18 - 14 and other pairs. What are those pairs? Does ~ satisfy the reflexive, symmetric and transitive properties.

A formal definition of an equivalence relationship is given at
http://en.wikipedia.org/wiki/Equivalence_relation

A given binary relation ~ on a set X is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive. Equivalently, for all a, b and c in X:

• a ~ a. (Reflexivity)
• if a ~ b then b ~ a. (Symmetry)
• if a ~ b and b ~ c then a ~ c. (Transitivity)

X together with the relation ~ is called a setoid. The equivalence class of a under ~, denoted [a], is defined as

.

 

[HallsofIvy]

You give just the statement of the problem with no attempt of your own to do it so it is impossible to see what you do understand about this problem or what hints might help. Do you understand what any of the words you use here mean? Do you know what a "relation" is? Do you know what an "equivalence relation" is? Do you know what "equivalence classes" are?

A relation on a given set is a collection of ordered pairs of elements of that set. We say that "x is related to y" or "xRy" if and only if (x, y) is in that collection. A relation is an "equivalence relation" if and only if it satisfies three properties:
1) It is "reflexive"- every element of the set is related to itself: we always have xRx. If x is in the set then (x, x) is in the collection of ordered pairs.
2) It is "symmetric". If (x, y) is in the collection so is (y, x): if xRy then yRx.
3) It is "transitive". If (x, y) and (y, z) are in the collection, so is (x, z): if xRy and yRz then xRz.

Here your set is {0, 1, 2, ..., 20} and the xRy if and only if x- y is divisible by 4.

1) Reflexive: for all x, x- x= 0. Is 0 divisible by 4? (Is 0= 4n for some integer, n?)
2) Symmetric: if xRy then y- x is divisible by 4 (y- x= 4n for some integer n). What can you say about x- y?
3) Transitive: if xRy then y- x is divisible by 4 (y- x= 4n for some integer n). If yRz then z- y is divisible by 4 (z- y= 4m for some integer m). What can you say about z- x? (Notice that (z- y)- (y- x)= z- x.)

"Equivalence classes" are subsets of the original set, all member of which are equivalent to one another. It can be shown that each member of the original set is in one and only one "equivalence class". 0 is in the original set. What other members of {1, 2, ..., 20} are equivalent to 0? (x is equivalent to 0 if and only if x- 0= x is divisible by 4.). 1 is in the original set. What other members of {0, 2, ..., 20} are equivalent to 1? (x is equivalent to 1 if and only if x- 1 is divisible by 4.)