1.3. Equivalence Relations and Classes

Example 1.3.4(a):

Consider the set Z of all integers. Define a relation r by saying that x and y are related if their difference y - x is divisible by 2. Then
  1. Check that this relation is an equivalence relation
  2. Find the two equivalence classes, and name them appropriately.
  3. How would you add these equivalence classes, if at all ?
1. Equivalence Relation
reflexive:
x - x is equal to zero, which is divisible by two. Hence, every element is related to itself.
symmetry:
if x ~ y, then y - x is divisible by 2. But then - (y - x) = x - y is divisible by two. Hence, y ~ x
transitivity:
  • if x ~ y then y - x = 2n for some integer n
  • if y ~ z then z - y = 2m for some integer m
But then z - x = (2m + y) - (y - 2n) = 2 (m + n), so that z - x is divisible by 2. In other words, x and z are related.
2. Equivalence Classes

Two elements are in the same equivalence class if and only if they are related. If x and y are in the same class, then y - x = 2n for some integer n.

Therefore, there are two equivalence classes, and they are appropriately labeled: 3. Adding Equivalence Classes

Define [x] + [y] = [x + y]. We need to show that this is well-defined, i.e. independent of the particular representative of the equivalence classes of [x] and [y]. Take x ~ x' and y ~ y'.

That means that (x' + y') and (x + y) are related if x ~ x' and y ~ y'. But then Hence, addition does not depend on the particular representative from a class, so that addition as defined above is indeed a well-defined operation.

A better method would be the following: Define two classes 0 and 1 by saying:

Then add equivalence classes by adding numbers modulo 2.
Next | Previous | Glossary | Map