Stage review: sets, maps and sizes

This review asks for three proofs: one about sets, one about maps and one about sizes. The first is a law that lets you multiply out set expressions, as with numbers.

The cell tries all 512 triples of subsets of $\{1, 2, 3\}$. It also tries a careless version, with the second $A$ left out.

The law holds for all 512 triples. The careless version, $(A \cap B) \cup C$, fails for 296 of them.

Lesson PG6.2 showed that a chain of injective maps is injective, and that $g \circ f$ can be injective when $g$ is not. What about the inner map $f$? The cell tries every $f$ from a 2-element set to a 3-element set, with every $g$ from there to a 3-element set.

In all 243 pairs, $f$ is injective whenever $g \circ f$ is. The outer map $g$ need not be: in 72 pairs, $g \circ f$ is injective but $g$ is not.

A subset $S$ of $\mathbb{N}$ can be written as a toss sequence: toss $n$ is H when $n \in S$ and T when $n \notin S$. For subsets of $\{1, 2, 3, 4\}$ the sequences have 4 tosses, and the cell checks that this pairs the subsets off with the sequences.

The 16 subsets give 16 different sequences, all 16 there are: $\{1, 3\}$ becomes HTHT, and the empty set TTTT. A set of $k$ elements has $2^k$ subsets, far more than $k$: 1,048,576 for $k = 20$.