文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-tzu Juan
Chapter 7 Relations: The Second
Time Around
§ Equivalence Relations and Partitions
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-tzu Juan 1
§ Equivalence Relations and Partitions
Note: 1) If A , R = the equality relation.
(A, R) is a equivalence relation.
 establishes the property of “sameness”on A.
2) If A = Z, R defined by xRy if 2 (x –y).
(Z, R) is a equivalence relation.
 splits Z into two subsets consisting of the odd and
even integers.
Def : A: set; I: index set; i I, Ai A
1) {Ai}iI is a partition of A if
(a) A = Ai and (b) i, j I where i j, A A = .
iI i j
2) Each Ai is called a cell (or block) of the partition.
(c) Spring 2007, Justie Su-tzu Juan 2
§ Equivalence Relations and Partitions
Ex : A = {1, 2, 3, …, 10}, each of (a), (b), (c) determines a
partition of A:
a) A1 = {1, 2, 3, 4, 5}, A2 = {6, 7, 8, 9, 10}.
b) A1 = {1, 2, 3}, A2 = {4, 6, 7, 9}, A3 = {5, 8, 10}.
c) Ai = {i, i + 5}, 1 i 5.
Note: Each element of A belongs to exactly one cell in each
partition.
(x A, ! i* I, . x Ai* for any partition {Ai}iI)
Ex : Let A = R, i Z, let Ai = [i, i+1)
{Ai}iZ is a partition of R
(c) Spring 2007, Justie Su-tzu Juan 3
§ Equivalence Relations and Partitions
Def : Let R be an equivalence relation on a set A. x A,
the equivalence class of x, denoted by [x] {y A yRx}
Ex : Define R on Z by xRy if 4 (x –y)
[0] = {…, –8, –4, 0, 4, 8, …} = {4k k Z}
[1] = {4k+1 k Z}; [2] = {4k+2 k Z}; [3] = {4k+3 k Z};
[4] = [0] = [8] = …; [5] = [1] = [9] = …;
[6] = [2] = [10] = …; …
.: [6] = [2] = [–2]; [51] = [3], …
{[0], [1], [2], [3]} provides a partition of Z.
Note: The index set for the partition is imp