Define a relation R on Z by xy e R if and only if x a Give f

Define a relation R on Z by (x,y) e R if and only if x a. Give five examples of elements of R. y. b. Is R reflexive? Anti-reflexive? c. Is R symmetric? Anti-symmetric? d. Is R transitive?

Solution

A relation R is an equivalence relation if and only if it is reflexive, symmetric and transitive.

Examples:

Let m and n be integers and let d be a positive integer. The notation

m = n (mod d)

is read \"m is congruent to n modulo d\".
The meaning is: the integer division of d into m gives the same remainder
as the integer division of d into n.

Consider the relation R = {(x,y)| x mod 3 = y mod 3}
For example, 4 mod 3 = 1, 7 mod 3 = 1, hence hence (4,7) Î R.

The relation is

reflexive: x mod 3 = x mod 3
symmetric: if x mod 3 = y mod 3, then y mod 3 = x mod 3
transitive: if x mod 3 = y mod 3, and y mod 3 = z mod 3, then x mod 3 = z mod 3

Consider the sets [x]= {y | yRx}, where x is an integer, and R is the relation above.

[0] = {0,3,6,9,12,….}
[1] = {1,4,7,10,13,….}
[2] = {2,5,8,11,14,…}

From the definition of [x] it follows that

[0] = [3] = [6] …
[1] = [4] =…
[2] = [5] = …

Thus the relation R produces three different sets [0], [1] and [2].

Each number is exactly in one of these sets.
The set {[0], [1], [2]} is a partition of the set of non-negative integers.

Theorem: Each equivalence relation on a set induces a partition of that set,
and each partition of a set induces an equivalent relation on the set.
The sets in the partition are called classes of equivalence.