PG6.1 Sets and set operations, proved

Simulate

Check the claim with numbers

Lesson 5.1.1 turned "or", "and" and "not" into union, intersection and complement. "Not ( $A$ or $B$ )" sounds like "not $A$ and not $B$ ". In symbols: is $(A \cup B)^c$ always $A^c \cap B^c$ ?

A small sample space can be checked completely. Take $\Omega = \{1, 2, 3, 4\}$ . It has 16 subsets, so 256 pairs $(A, B)$ , and the cell tries every pair.

from itertools import chain, combinations, product Omega = frozenset({1, 2, 3, 4}) subsets = [frozenset(c) for c in chain.from_iterable(combinations(sorted(Omega), r) for r in range(5))] pairs = list(product(subsets, repeat=2)) def comp(S): return Omega - S print(len(subsets), len(pairs)) print(all(comp(A | B) == comp(A) & comp(B) for A, B in pairs)) print(all(comp(A & B) == comp(A) | comp(B) for A, B in pairs)) print(sum(comp(A | B) != comp(A) | comp(B) for A, B in pairs))

⌘/Ctrl + Enter runs the cell

Both laws hold for all 256 pairs: the complement of a union is the intersection of the complements, and the other way round. The last line tries a careless version, with $\cup$ on both sides. It fails for 240 of the 256 pairs.

Conjecture

A

Every pair of subsets of one four-element set. A proof must cover every sample space, including infinite ones, where no computer can try every pair.

How to prove two sets are equal

$A \subseteq B$ , read " $A$ is a subset of $B$ ", means every element of $A$ is in $B$ . Two sets are equal when they have the same elements, which is the same as each being a subset of the other.

Rule: Proving two sets equal

\begin{gathered} A = B \iff A \subseteq B \text{ and } B \subseteq A \end{gathered}

To prove $A \subseteq B$ , take any element $x$ of $A$ , using nothing but $x \in A$ , and show that $x \in B$ . Then do the same the other way round.

This is called double inclusion. Each half is a short chain of "so", one membership at a time. Remember that $x \in A^c$ means $x \in \Omega$ and $x \notin A$ .

Format 1

Reorder the steps

Here is the proof of the first law, with its lines shuffled. Put them in order with the arrows, or drag a line by its handle.

So $x \in A^c$ and $x \in B^c$ , that is, $x \in A^c \cap B^c$ . This proves $(A \cup B)^c \subseteq A^c \cap B^c$ .
An element of $A \cup B$ is in $A$ or in $B$ , so $x \notin A \cup B$ , and $x \in (A \cup B)^c$ . This proves $A^c \cap B^c \subseteq (A \cup B)^c$ .
An element of $A$ or of $B$ would be in $A \cup B$ , so $x \notin A$ and $x \notin B$ .
First, take any $x \in (A \cup B)^c$ . Then $x \in \Omega$ and $x \notin A \cup B$ .
Next, take any $x \in A^c \cap B^c$ . Then $x \in \Omega$ , $x \notin A$ and $x \notin B$ .
Each set is a subset of the other, so $(A \cup B)^c = A^c \cap B^c$ .

The second law has the same shape, with "or" and "and" trading places. Lesson PG6.5 asks for a proof of the same shape.

Simulate

The probability rules

Lesson 5.1.1 stated two rules and said the Proof Gym proves them from the axioms: $P(A^c) = 1 - P(A)$ , and $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ . The proof splits a set into pieces that do not overlap.

Write $B \setminus A$ , read " $B$ minus $A$ ", for the outcomes of $B$ that are not in $A$ . The cell takes the loaded die of lesson 5.1.1 and tries all $64 \times 64$ pairs of events, with exact fractions.

from fractions import Fraction from itertools import chain, combinations, product p = {face: Fraction(1, 10) for face in range(1, 6)} p[6] = Fraction(1, 2) events = [frozenset(c) for c in chain.from_iterable(combinations(sorted(p), r) for r in range(7))] pairs = list(product(events, repeat=2)) def P(E): return sum((p[w] for w in E), Fraction(0)) print(len(events), len(pairs)) print(all(not (A & (B - A)) and A | (B - A) == A | B for A, B in pairs)) print(all(not ((A & B) & (B - A)) and (A & B) | (B - A) == B for A, B in pairs)) print(all(P(A | B) == P(A) + P(B) - P(A & B) for A, B in pairs))

⌘/Ctrl + Enter runs the cell

The second line confirms that $A$ and $B \setminus A$ never overlap and together make $A \cup B$ . The third does the same for $A \cap B$ and $B \setminus A$ , which make $B$ . The last line confirms the addition rule exactly, for all 4,096 pairs.

Conjecture

P

One probability on one die. The proof uses only the three axioms, so it works for every probability.

Format 2

Fill the gap

The proof from the axioms of lesson 5.1.1, with its key steps left out. Write $a = P(A)$ , $b = P(B)$ and $c = P(A \cap B)$ , and type each answer in those letters, such as a-2c, then check.

A

How to type answers

Powers with ^, brackets round a power that is a sum: r^k, r^(k+1).
Fractions with / and brackets: (1-r)/(1+r). Multiply with * or side by side: 2k+1.
Press Enter in any box to check them all.

Simulate

Can you cancel a set?

With numbers, $a + b = a + c$ means $b = c$ . Is the same true for sets: does $A \cap B = A \cap C$ force $B = C$ ? The cell tries all 512 triples of subsets of $\{1, 2, 3\}$ .

from itertools import chain, combinations, product U = {1, 2, 3} subsets = [frozenset(c) for c in chain.from_iterable(combinations(sorted(U), r) for r in range(4))] triples = list(product(subsets, repeat=3)) def show(S): return "{" + ", ".join(str(x) for x in sorted(S)) + "}" one = [(A, B, C) for A, B, C in triples if A & B == A & C and B != C] both = [(A, B, C) for A, B, C in triples if A & B == A & C and A | B == A | C and B != C] print(len(triples), len(one), len(both)) print([show(S) for S in one[0]])

⌘/Ctrl + Enter runs the cell

Of the 512 triples, 152 have $A \cap B = A \cap C$ but $B \ne C$ . The first is $A = \varnothing$ , $B = \varnothing$ , $C = \{1\}$ : both intersections are empty. When the unions agree as well, no triple has $B \ne C$ .

Conjecture

A \cap B = A \cap C

All 512 triples on a three-element set. One condition alone fails, so a proof must use both.

Format 3

Find the error

A proof of the conjecture with one faulty line. Notice which condition it never uses. Select the faulty line.

A \subseteq B

Sets and set operations, proved

Check the claim with numbers

How to prove two sets are equal

Rule: Proving two sets equal

Reorder the steps

The probability rules

Fill the gap

Can you cancel a set?

Find the error

Summary card

Free further reading