Report

Equivalence Relations MSU CSE 260 Outline • Introduction • Equivalence Relations – Definition, Examples • Equivalence Classes – Definition • Equivalence Classes and Partitions – Theorems – Example Introduction • Consider the relation R on the set of MSU students: a R b a and b are in the same graduating class. – R is reflexive, symmetric and transitive. • Relations which are reflexive, symmetric and transitive on a set S, are of special interest because they partition the set S into disjoint subsets, within each of which, all elements are all related to each other (or equivalent.) Equivalence Relations • Definition. A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. • Two elements related by an equivalence relation are called equivalent. Example • Consider the Congruence modulo m relation R = {(a, b) Z | a b (mod m)}. – Reflexive. a Z a R a since a - a = 0 = 0 m – Symmetric. a, b Z If a R b then a - b = km. So b - a = (-k) m. Therefore, b R a. – Transitive. a, b, c Z If a R b b R c then a - b = km and b - c = lm. So (a-b)+(b-c) = a-c = (k+l)m. So a R c. R is then an equivalence relation. Equivalence Classes • Definition. Let R be an equivalence relation on a set A. The set of all elements related to an element a of A is called the equivalence class of a, and is denoted by [a]R. • [a]R = {xA | (a, x) R} • Elements of an equivalence class are called its representatives. Example • What are the equivalence classes of 0, 1, 2, 3… for congruence modulo 4? – – – – [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, …} The other equivalence classes are identical to one of the above. [a]m is called the congruence class of a modulo m. Equivalence Classes & Partitions • Theorem. Let R be an equivalence relation on a set S. The following statements are logically equivalent: –aRb – [a] = [b] – [a][b] Equiv. Classes & Partitions - cont • Definition. A partition of a set S is a collection {Ai | i I} of pairwise disjoint nonempty subsets that have S as their union. – i,jI Ai Aj = , and iI Ai = S. • Theorem. Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition of S. Conversely, for any partition {Ai | i I} of S there is an equivalence relation that has the sets Ai as its equivalence classes. Example • Every integer belongs to exactly one of the four equivalence classes of congruence modulo 4: – – – – [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, …} • Those equivalence classes form a partition of Z. – [0]4 [1]4 [2]4 [3]4 = Z – [0]4, [1]4, [2]4 and [3]4 are pairwise disjoint.