MathCS.org - Real Analysis: Example 1.3.4(a):

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

Check that this relation is an equivalence relation
Find the two equivalence classes, and name them appropriately.
How would you add these equivalence classes, if at all ?

Back

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.

If y was even, then y = 2m for some integer m, and x = 2m - 2n must also be even.
If y was odd, then y = 2m + 1 for some integer m, and x = 2m + 1 - 2n must also be odd

Therefore, there are two equivalence classes, and they are appropriately labeled:

E = even numbers: E = [(2)] contains all even numbers
O = odd numbers: O = [(3)] contains all odd numbers.

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

Then x' - x = 2m and y' - y = 2n for some integers n and m.
Then (x' + y') - (x + y) = x' - x + y' - y = 2m + 2n = 2 (m + n)

That means that (x' + y') and (x + y) are related if x ~ x' and y ~ y'. But then

[x] + [y] = [x + y] = [x' + y'] = [x'] + [y']

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:

all numbers divisible by 2 with no remainder are in class 0
all numbers divisible by 2 with remainder 1 are in class 1

Then add equivalence classes by adding numbers modulo 2.

Next | Previous | Glossary | Map | Discussion

Interactive Real Analysis - part of MathCS.org

Example 1.3.4(a):