Equivalence Classes

Return to List of Lectures

Previous Lecture

• Misc
  • Final
    • Noon - 2:30, Wednesday December 14
    • Regular room
    • Comprehensive, but emphasizing material since 2nd hour exam (e.g., sets, functions, relations, infinite sets, etc.)
    • Designed for 2 hours (or less), you’ll have 2 1/2
    • Style and rules otherwise similar to hour exams, especially open references
    • ca 6 - 8 questions, including some proofs
    • Maybe review session (preferably after 3:00)
      • News: on the way out of class I scheduled a review session from 3:00 - 4:30 on study day, in our regular room
    • Donuts and cider
  • SOFIs
    • 6 responses (31.58%) as of this morning
• Questions?
  • Problem set 12 question 3?
    • Start with x ∈ f(f^-1(C)) and show x ∈ C
    • x ∈ f( A ) means that there exists y ∈ A such that x = f(y)
    • y ∈ f^-1(C) means there exists z ∈ C such that f^-1(z) = y
    • f^-1(z) = y means f(y) = z
• Equivalence Classes
  • Section 7.3
  • Recall the family relationships
    • Henry VII married Elizabeth of York, and had children
      • Arthur
      • Margaret
      • Henry VIII
    • Arthur married Katherine of Aragon
    • Henry VIII married Katherine of Aragon, and had child
      • Mary
    • Henry VIII married Anne Boleyn, and had child
      • Elizabeth I
    • Henry VIII married Jane Seymour, and had child
      • Edward VI
    • Henry VIII married Anne of Cleves
    • Henry VIII married Katherine Howard
    • Henry VIII married Katherine Parr
  • Consider a “same father” relation F, i.e., x F y iff x and y have the same father
    
    • Is it an equivalence relation?
      • Yes, arrows from each person to self show it is reflexive, double arrows show it is symmetric, arrows between all members of triangles of children of same father show transitivity
    • If so, what are its equivalence classes?
    • Properties of equivalence classes?
      • Everyone is in their own equivalence class
        • But note that “their own equivalence class” doesn’t mean they are necessarily the only member
      • Equivalence classes don’t overlap, i.e., they are disjoint
    • Equivalence classes partition the set of people
      • “Partition” means a set of subsets that between them contain all members of set A
      • But note that not all such collections of subsets are partitions: the subsets also have to be disjoint
        
  • Let x ∼ y for real numbers x and y iff x² = y². Prove that ∼ is an equivalence relation and give examples of its equivalence classes.
    • Equivalence relation
      • Reflexive: let x be any real number, x² = x²
      • Transitive: suppose x ∼ y and y ∼ z
        • Then x² = y² and y² = z² so x² = z²
        • Therefore x ∼ z
      • Symmetric: suppose x ∼ y
        • Then x² = y² so y² = x²
        • So y ∼ x
    • Equivalence classes
      • For example, [2] = { 2, -2 }
      • Generally, [x] = { x, -x }
      • But [0] = { 0 }
• Next
  • Finite sets and cardinality
  • Read section 9.1

Next Lecture