Page 635 - Discrete Mathematics and Its Applications

614 9 / Relations

Solution: The subsets in the partition are the equivalence classes of R. The pair (a, b) ∈ R if and
only if a and b are in the same subset of the partition. The pairs (1, 1), (1, 2), (1, 3), (2, 1), (2, 2),
(2, 3), (3, 1), (3, 2), and (3, 3) belong to R because A 1 ={1, 2, 3} is an equivalence class; the
pairs (4, 4), (4, 5), (5, 4), and (5, 5) belong to R because A 2 ={4, 5} is an equivalence class;
and finally the pair (6, 6) belongs to R because {6} is an equivalence class. No pair other than
those listed belongs to R. ▲

The congruence classes modulo m provide a useful illustration of Theorem 2. There
are m different congruence classes modulo m, corresponding to the m different remainders
possible when an integer is divided by m. These m congruence classes are denoted by
[0] m , [1] m ,..., [m − 1] m . They form a partition of the set of integers.
EXAMPLE 14 What are the sets in the partition of the integers arising from congruence modulo 4?

Solution: There are four congruence classes, corresponding to [0] 4 , [1] 4 , [2] 4 , and [3] 4 . They
are the sets
[0] 4 ={..., −8, −4, 0, 4, 8,... },
[1] 4 ={..., −7, −3, 1, 5, 9,... },
[2] 4 ={..., −6, −2, 2, 6, 10,... },
[3] 4 ={..., −5, −1, 3, 7, 11,... }.
These congruence classes are disjoint, and every integer is in exactly one of them. In other
words, as Theorem 2 says, these congruence classes form a partition. ▲

We now provide an example of a partition of the set of all strings arising from an equivalence
relation on this set.
EXAMPLE 15 Let R 3 be the relation from Example 5.What are the sets in the partition of the set of all bit strings
arising from the relation R 3 on the set of all bit strings? (Recall that sR 3 t, where s and t are bit
strings, if s = t or s and t are bit strings with at least three bits that agree in their first three bits.)

Solution: Note that every bit string of length less than three is equivalent only to itself.
={10}, and
Hence [λ] R 3 ={λ}, [0] R 3 ={0}, [1] R 3 ={1}, [00] R 3 ={00}, [01] R 3 ={01}, [10] R 3
={11}. Note that every bit string of length three or more is equivalent to one of the eight
[11] R 3
bit strings 000, 001, 010, 011, 100, 101, 110, and 111. We have
={000, 0000, 0001, 00000, 00001, 00010, 00011,...},
[000] R 3
={001, 0010, 0011, 00100, 00101, 00110, 00111,...},
[001] R 3

={010, 0100, 0101, 01000, 01001, 01010, 01011,...},
[010] R 3
={011, 0110, 0111, 01100, 01101, 01110, 01111,...},
[011] R 3

={100, 1000, 1001, 10000, 10001, 10010, 10011,...},
[100] R 3
={101, 1010, 1011, 10100, 10101, 10110, 10111,...},
[101] R 3

={110, 1100, 1101, 11000, 11001, 11010, 11011,...},
[110] R 3
={111, 1110, 1111, 11100, 11101, 11110, 11111,...}.
[111] R 3
These 15 equivalence classes are disjoint and every bit string is in exactly one of them. As
Theorem 2 tells us, these equivalence classes partition the set of all bit strings. ▲