First PrinciplesStart anywhere. Prove it, then move on.

Rung 17

Sets

Union, intersection, complement — and the language everything else is written in.

Best attempted after 14. Proof technique. Nothing stops you trying this now — the gate will tell you if you were right.

The gate

Prove one of De Morgan's laws twice: once by element-chasing, taking an arbitrary element and arguing both directions, and once by truth table. Then say why those are the same argument in two notations.

Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.

A set is a collection with no order and no repeats. That is nearly the whole definition, and its plainness is the point: sets are the notation everything above this rung is written in.

Three operations do most of the work. Union: in either. Intersection: in both. Complement: not in it. If those feel familiar from rung 15, they should — they are OR, AND and NOT with different symbols and a different picture.

Why this is on the ladder

Because the vocabulary is unavoidable from here up. A probability at rung 38 is defined on sets of outcomes. A vector space at rung 28 is a set with structure added. A Python set and dict at rung 18 are this idea made executable, and their speed comes directly from the fact that membership is the only question they answer.

Do this

Prove (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ — "not in either" is the same as "in neither".

First by element-chasing. Take an arbitrary x in the left side and argue it must be in the right; then take an arbitrary x in the right and argue it must be in the left. Two directions, because set equality means mutual containment. Skipping one direction is the standard error and it does not prove equality.

Then by truth table. Two sets give four cases — in both, in A only, in B only, in neither. Fill in each side for each case and compare columns.

Finally, say why they are the same proof. Element-chasing walks the cases one at a time in words; the table lays them out at once. Rung 15 built that table; this rung gives it a second reading.

Where people get stuck

Proving one containment and stopping. ⊆ in one direction is genuinely weaker than =, and the missing half is where counterexamples live.

The other trap is arguing from a Venn diagram. A diagram is a fine way to see what is true and not a proof that it is — the same objection rung 13 raised about Euclid's circles, arriving in new clothes.

Reading