s14-15

Page 1: Class Plan

• Sections 14, 15: Relations and Equivalence Relations

• Course: Discrete Mathematics

• Instructor: Professor Chikhany

Page 2: Class Objectives

• Define a relation.

• Discuss properties of relations.

• Identify an equivalence relation and its equivalence classes.

• Prove a relation is an equivalence relation.

Page 3: Relation Definition

• Definition: Suppose A and B are sets, relation R is on A and B if R ⊆ A × B.

• Notation: arb (means a is related to b) implies (a, b) ∈ R.

• Relation exists if aR b and (a, b) ∈ R, suggesting that R is a relation on A.

Page 4: Examples of Relations

• Example sets:

  • Let A = {1, 2, 3}, B = {2, 4, 6}.

  • Let A = {1, 2, 3, 4}, B = {1, 3, 2, 7}.

• Relation R: R = {(x, y) ∈ Z : y = 2x + 1}.

• Defined example relations:

  • R = {(1, 2), (4, 2), (3, 1)} – valid relation.

  • R defined as 1, 4, 2, 6 – shows valid pairs.

  • Example of invalid relation: R = {(1, 7)}.

Page 5: Categorizing Relations

• Categorize the following relations based on properties:

  • Equality (=), Less than (<), Some other relations (not specified), and S = {(1,1),(2,2),(1,2),(2,1),(3,3)} on {1,2,3}.

  • Relation R = {(1,3),(4,3),(1,1),(2,4),(2,3),(2,5)} on {1,2,3,4,5}.

• Categories include: Reflexive, Irreflexive, Symmetric, Antisymmetric, Transitive.

Page 6: Properties of Relations

• Definitions: For relation R defined on set A:

  • R is reflexive if aRa for all a ∈ A.

  • R is irreflexive if no a ∈ A satisfies aRa.

  • R is symmetric if aRb implies bRa.

  • R is antisymmetric if aRb and bRa implies a = b.

  • R is transitive if aRb and bRc implies aRc.

Page 7: Visualization with Graphs

• Example relation: R = {(1,3),(4,3),(1,1),(2,4),(2,3),(2,5)}.

• Reflexive graph representation: Indicates if loops exist.

• Symmetric representation: Indicates bidirectional edges between related pairs.

Page 8: Summary of Relation Properties

• Assisted review of categorizing relations:

  • S, R put under Reflexive, Irreflexive, Symmetric, Antisymmetric, Transitive categories.

Page 9: Operations on Relations

• Set Operations:

  • Union, Intersection, Set Difference, Symmetric Difference.

• Inverse Definition:

  • The inverse of R, denoted by R⁻¹, is formed by reversing ordered pairs in R.

Page 10: Equivalence Relations Definition

• Definition: A relation R on set A is an equivalence relation if it is reflexive, symmetric, and transitive.

• Non-examples: Inequality (≠) and divisibility (|) on integers.

• Examples: Equality (=), "Has the same birthday as" among people, congruence (≅) among triangles.

Page 11: Proving Equivalence Relation

• Theorem: To prove R is an equivalence relation, one must show:

  • R is reflexive.

  • R is symmetric.

  • R is transitive.

Page 12: Example of Equivalence Relation Proof

• Show relation: M = {(x, y) ∈ R | x² - y² = 2(y - x)} is an equivalence relation.

Page 13: Continued Example of Equivalence Relation

• Proving M is an equivalence relation by showing reflexivity and symmetry.

Page 14: Congruence Modulo Definition

• Definition of congruence modulo n: x ≡ y (mod n) if n divides (x - y).

• Examples: Calculating congruences using mod 2, 5, 13.

Page 15: Theorem on Congruence Relation

• Prove congruence modulo n is an equivalence relation. Prove reflexivity, symmetry, and transitivity.

Page 16: Equivalence Classes Definition

• An equivalence class [a] is the set of all elements related to a by R.

• Examples: Using congruence modulo n to define equivalence classes.

Page 17: Examples of Equivalence Classes

• Elaborated examples of equivalence classes based on earlier definitions.

Page 18: More Examples of Equivalence Classes

• Analysis of even and odd integer equivalence classes.

Page 19: Further Example of Equivalence Relation

• M = {(a, b) ∈ R | a² + a = b² + b} verified as an equivalence relation.

Page 20: Finding Equivalence Classes

• Examples showing equivalence classes derived from given relations.

Page 21: Proposition on Equivalence Relations

• If x, y ∈ [a], then xRy.

Page 22: Self-inclusion in Equivalence Classes

• Every element a ∈ A belongs to its equivalence class [a].

Page 23: Relationship Between Equivalence Classes

• aRb iff [a] = [b].

Page 24: Disjoint and Nonempty Equivalence Classes

• Equivalence classes are nonempty, pairwise disjoint subsets of A whose union is A.

Page 25: Class Summary

• Important definitions and methods for verifying relations and equivalence classes.