An Algebra for Sets

Misc

Exam 2 is next Wednesday (April 3).

Covers proof techniques and possibly quantifiers (e.g., for all, there exists, contrapositive, biconditionals, contradiction, cases, induction — problem sets 4 through 6).

Rules and format will be similar to exam 1, particularly open-references rule. But there may be slightly fewer questions, because more of the questions will ask you to write proofs.

Sample questions are now available in Canvas.

Questions?

Set Algebra

Section 5.3

Distributivity and Difference

Do union and intersection distribute over set difference? In other words, is it or is it not true that

• A ∪ (B - C) = (A ∪ B) - (A ∪ C)
• A ∩ (B - C) = (A ∩ B) - (A ∩ C)

Ways of exploring a question:

• Examples
• Venn diagrams (for questions about sets)
• Insight into operations

Based on doing some of these things, we suspect that union doesn’t distribute over difference, i.e., A ∪ (B - C) ≠ (A ∪ B) - (A ∪ C), but intersection does, i.e., A ∩ (B - C) = (A ∩ B) - (A ∩ C)

Union

Consider union first, i.e., is A ∪ (B - C) = (A ∪ B) - (A ∪ C).

Counter-example: let A = {a}, B={b}, C={b}

{a} ∪ ( {b} - {b} ) = {a} vs ({a} ∪ {b}) - ({a} ∪ {b}) = ∅

Intersection

To see that intersection does distribute over difference, use algebraic rules to rewrite the left hand side, A ∩ (B - C), into the right, (A ∩ B) - (A ∩ C). (But it’s probably easier to see what to do if you rewrite the right into the left. Logically both approaches are equivalent.)

A ∩ (B - C) = A ∩ (B ∩ C^C)

= (A ∩ B) ∩ C^C

= ∅ ∪ (A ∩ B) ∩ C^C

= (A ∩ A^C) ∪ (A ∩ B) ∩ C^C

= (A ∩ B ∩ A^C) ∪ (A ∩ B) ∩ C^C

= (A ∩ B) ∩ (A^C ∪ C^C )

= (A ∩ B) ∩ (A ∩ C )^C

= (A ∩ B) - (A ∩ C )

Key Point

Algebra as a proof technique

Next

Another set operation: Cartesian products and ordered pairs.

Read section 5.4