The Algebra of Sets

Return to List of Lectures

Previous Lecture

• Questions?
  • If …conditions… then B = C in problem set?
    • “Treat equality as biconditional” means x ∈ B iff x ∈ C
    • For proof: assume …conditions… and then show x ∈ B iff x ∈ C in 2 parts
• Algebra of Set Operations
  • Section 5.3
  • Does difference distribute over intersection, i.e., is (A ∩ B) - C = (A-C) ∩ (B-C)?
    • Probably not because it’s not one of the theorems in reading?
    • Actually it does: consider…
      • (A ∩ B) - C = (A ∩ B) ∩ C^C [ X-Y = X ∩ Y^C ]
      • = (A ∩ B) ∩ (C^C ∩ C^C) [ X ∩ X = X ]
      • = ( A ∩ C^C ) ∩ (B ∩ C^C) [ assoc & comm ]
      • = (A-C) ∩ (B-C) [ X-Y = X ∩ Y^C ]
    • Or via Boolean algebra
      • x ∈ (A ∩ B) - C
      • ≡ x ∈ A ∧ x ∈ B ∧ x ∈ C^C
      • ≡ x ∈ A ∧ x ∈ B ∧ x ∈ C^C ∧ x ∈ C^C [ P ≡ P ∧ P ]
      • ≡ x ∈ A ∧ x ∈ C^C ∧ x ∈ B ∧ x ∈ C^C [assoc, comm]
      • ≡ x ∈ (A-C) ∧ x ∈ (B-C) [ def set -]
      • ≡ x ∈ (A-C) ∩ (B-C) [ def ∩]
  • When are union and difference inverses of each other, i.e., when is it true that (A ∪ B) - B = A?
    • Conjecture: if A and B disjoint, then A ∪ B - B = A
    • Proof using set algebra:
      • Let A and B be disjoint subsets of some universal set
      • (A ∪ B) - B = (A ∪ B) ∩ B^C
      • = B^C ∩ (A ∪ B)
      • = (B^C ∩ A) ∪ (B^C ∩ B) [∩ distributes over ∪]
      • = A ∪ (B^C ∩ B) [A and B disjoint means A ⊆ B^C]
      • = A ∪ ∅
      • = A
  • Problem set
• Next
  • Cartesian products
  • Read section 5.4

Next Lecture