Relations, Functions and Power Sets

Structure From Bare Collections

Sets alone have no structure, but structure can be built from them.

The ordered pair $(a, b)$ is the first step, and unlike a set it is sensitive to order: $(1, 2) \neq (2, 1)$. The Cartesian product $A \times B$ is the set of all ordered pairs with first element from $A$ and second from $B$, so $|A \times B| = |A| \cdot |B|$.

A relation from $A$ to $B$ is any subset of $A \times B$, nothing more. Relations on a single set are classified by three properties:

A relation with all three is an equivalence relation, and it partitions the set into disjoint equivalence classes. "Has the same birthday as" is an equivalence relation; "is taller than" is transitive but neither reflexive nor symmetric.

A function from $A$ to $B$ is a relation assigning exactly one element of $B$ to each element of $A$. It is injective if distinct inputs give distinct outputs, surjective if every element of $B$ is hit, and bijective if both.

Two counting results carry surprising weight. The power set $\mathcal{P}(A)$ is the set of all subsets of $A$, and

$$|\mathcal{P}(A)| = 2^{|A|}$$

because each element is independently in or out. A 3-element set has 8 subsets. And the number of functions from $A$ to $B$ is $|B|^{|A|}$, since each of the $|A|$ inputs independently gets one of $|B|$ outputs.

Cantor's theorem says $|\mathcal{P}(A)| > |A|$ for every set, finite or infinite. Since $2^n > n$ always, there is no largest set and no largest infinity, the power set of any infinity is a strictly bigger one. This is where set theory stops being bookkeeping and starts producing results nobody expected.

Common pitfall: thinking every relation is a function. A function must assign exactly one output to each input, no more, no fewer. "Is a parent of" relates one person to several children, so it is a perfectly good relation and not a function at all.