In this chapter, the following content will be discussed: Equivalence classes, equivalence classes of congruence modulo 3, equivalence of congruence modulo n, properties of congruence modulo n, modular arithmetic, partial order relations, hasse diagram. | (CSC 102) Lecture 18 Discrete Structures Previous Lectures Summary Transitive closure of a relations Combining Relations The Relation Induced by a Partition Equivalence Relations Equivalence classes Relations Today’s Lecture Equivalence classes Equivalence Classes of Congruence Modulo 3 Equivalence of Congruence Modulo n Properties of Congruence Modulo n Modular Arithmetic Partial Order Relations Hasse Diagram Suppose A is a set, R is an equivalence relation on A, and a and b are elements of A. If a R b, then [a] = [b]. Let A be a set, let R be an equivalence relation on A, and suppose a and b are elements of A such that a R b. [We must show that [a] = [b].] Proof that [a] ⊆ [b]: Let x ∈ [a]. [We must show that x ∈ [b]]. Since x ∈ [a] then x R a by definition of class. But a R b by hypothesis. Thus, by transitivity of R, x R b. Hence x ∈ [b], by definition of class. [a] ⊆ [b] An Equivalence Relation on a Set of Subsets Proof that [b] ⊆ [a]: Let x ∈ [b]. [We must show that x ∈ [a]]. Since x ∈ [b], then x R b by definition of class. Now a R b by hypothesis. Thus, since R is symmetric, b R a also. Then, since R is transitive and x R b and b R a, x R a. Hence, x ∈ [a] by definition of class. [This is what was to be shown]. Thus [b] ⊆ [a]. Since [a] ⊆ [b] and [b] ⊆ [a], it follows that [a] = [b] by definition of set equality. An Equivalence Relation on a Set of Subsets Theorem: If A is a set, R is an equivalence relation on A, and a and b are elements of A, then either [a] ∩ [b] = ∅ or [a] = [b]. The statement of the theorem has the form if p then (q or r ). where p is the statement “A is a set, R is an equivalence relation on A, and a and b are elements of A,” q is the statement “[a] ∩ [b] = ∅,” and r is the statement “[a] = [b].” To prove the theorem, we will prove the logically equivalent statement if (p and not q) then r. That is, we will prove the following: If A is a set, R is an equivalence relation on A, a and b are elements of A, and [a] ∩ [b] ≠ ∅, then [a] = . | (CSC 102) Lecture 18 Discrete Structures Previous Lectures Summary Transitive closure of a relations Combining Relations The Relation Induced by a Partition Equivalence Relations Equivalence classes Relations Today’s Lecture Equivalence classes Equivalence Classes of Congruence Modulo 3 Equivalence of Congruence Modulo n Properties of Congruence Modulo n Modular Arithmetic Partial Order Relations Hasse Diagram Suppose A is a set, R is an equivalence relation on A, and a and b are elements of A. If a R b, then [a] = [b]. Let A be a set, let R be an equivalence relation on A, and suppose a and b are elements of A such that a R b. [We must show that [a] = [b].] Proof that [a] ⊆ [b]: Let x ∈ [a]. [We must show that x ∈ [b]]. Since x ∈ [a] then x R a by definition of class. But a R b by hypothesis. Thus, by transitivity of R, x R b. Hence x ∈ [b], by definition of class. [a] ⊆ [b] An Equivalence Relation on a Set of Subsets Proof that [b] ⊆ [a]: Let x ∈ [b]. [We must show that x ∈ [a]]. .
