Set Algebra, Part 2

Return to List of Lectures

Previous Lecture

Questions?

Set Algebra

Friday’s Lemma

Recall the assumption we used in Friday’s proof: If P is a subset of some universal set U, then P ∪ P^C = U

Prove this (since you can’t just assume new laws when doing proofs without proving the new laws in turn).

Tactic: prove that x ∈ P ∪ P^C if and only if x ∈ U.

Proof. First direction, prove that if x is in P ∪ P^C then x is in U. By definition of union, P ∪ P^C means { y ∈ U | y ∈ P or y ∈ P^C }, therefore every x in P ∪ P^C is in U. Second direction, prove that if x ∈ U then x ∈ P ∪ P^C. Let x be an element of U, then either x is in P or x is not in P. In the second case, x is in P^C. Thus we have x ∈ P or x ∈ P^C, i.e., x ∈ P ∪ P^C. QED.

Distributive Laws for Difference

Does set difference distribute over union from the right? How about from the left? In other words, is (A∪B) - C = (A-C) ∪ (B-C)? Is C - (A∪B) = (C-A) ∪ (C-B)?

Conjecture: If A, B, and C are subsets of some universal set U, then (A∪B) - C = (A-C) ∪ (B-C).

Proof. (A∪B) - C = (A∪B) ∩ C^C = (A ∩ C^C) ∪ (B ∩ C^C) = (A-C) ∪ (B-C). QED.

Conjecture: If A, B, and C are subsets of some universal set U, then C - (A∪B) = (C-A) ∪ (C-B).

This is false!

Counterexample: suppose C = {1,2}, A={1}, B{2}. A∪B = {1,2}, C - (A∪B) = {}. C-A = {2}, C-B = {1}, (C-A) ∪ (C-B) = {1,2} = C

Comments

One of the key things about the reading was already said in your summary: section 5.3 is where you can find lots of algebraic laws about set operations.

These laws are useful when proving that expressions involving those operations are equal. You can generally prove such equalities by translating the set operations into their logical definitions, doing the proof in terms of logical equivalences, and then translating back to set operations. But doing it all in terms of set operations may be slightly shorter and easier.

Some of the laws that I find most useful are the (many) distributive laws, the laws that parallel De Morgan’s laws for logic, and the ability to convert A - B into A ∩ B^C and vice versa.

Next

Cartesian products of sets

Read textbook section 5.4

Next Lecture