Set Algebra

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Set Algebra

Based on section 5.3 in the textbook and the set algebra discussion.

Some Distributive Rules

(From the discussion.) Does set difference distribute over intersection and union from the right, i.e., is it or is it not true that

• (A ∩ B) - C = (A - C) ∩ (B - C), and
• (A ∪ B) - C = (A - C) ∪ (B - C)?

Some thoughts on how to think about a question like this one:

• If you have some intuition for why it might not work, try to expand that intuition into a specific counter-example. For instance, someone thought that (A - C) ∩ (B - C) might “double count” elements of C relative to (A ∩ B) - C, so maybe there’s a counter-example in which A and B both share some element with C….
• If you suspect that it does work, you might try looking at examples to check that intuition. In the case of sets, Venn diagrams make good examples, because they are far more general than an example involving specific sets could be (but Venn diagrams are still intuitive or examples, not proofs). In this case a Venn diagram suggests that at least the first equality does hold:

Ultimately though, you need an actual rigorous proof to show that a suspicion is correct. We wrote one for subtraction distributing from the right over intersection as a formal proof in LaTeX. We chose to use set algebra as the main way of reasoning, although element chasing such as we did on Wednesday would also work. The source file and PDF output are available from Canvas (in the same files as the element-chasing proof from Wednesday, to make comparisons between the two styles easier).

Some key things I pointed out in the proof include…

• The overall equational style of the reasoning, encouraged by the fact that algebraic rules give you ways of transforming one expression into another, equal, one, which is in turn transformed by other rules, until hopefully arriving at the expected final expression. Note that in a well-written proof, such reasoning is written as a series of equalities that follow this flow, i.e., from one expression to the next (and in particular it is not written as a series of versions of the final, expected, equation, with one side or the other progressively transformed until both sides end up equal in a sort of “meet in the middle” style).
• As with most proofs, the introductory sentence or paragraph mentions how the proof will be done, in this case “…by using set algebra.” Other signaling language is used to help readers get started on and follow the block of equations that present the main logic.

I also introduced LaTeX’s \mathrm command, which lets you write non-italic text (in this case, the superscript “C” that denotes set complement) while in math mode.

We also outlined the proof about union, namely that (A ∪ B) - C = (A - C) ∪ (B - C). This proof is also mainly a series of equalities:

(A ∪ B) - C

= (A ∪ B) ∩ C^C 

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

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

“Exclusive Or”

Prove that A ∪ B - A ∩ B = (A-B) ∪ (B-A)

We thought a little bit about this, and decided that rewriting the difference on the lefthand side as an intersection would be a good start. Here’s how the proof could proceed from there:

A ∪ B - A ∩ B

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

= (A ∪ B) ∩ (A^C ∪ B^C) (by DeMorgan’s law)

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

= (A ∩ A^C) ∪ (A ∩ B^C) ∪ (B ∩ A^C) ∪ (B ∩ B^C) (distributive property again)

= ∅ ∪ (A ∩ B^C) ∪ (B ∩ A^C) ∪ ∅ (the intersection of a set with its complement is empty)

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

= (A - B)  ∪ (B - A)

Problem Set

Problem set 9 is ready if you want to see it early (it “officially” starts Monday).

Next

Another, probably less familiar, set operation: Cartesian product.

Please read section 5.4 of the textbook.

Please also contribute to this Cartesian product discussion.

Next Lecture