Equipotence and subpotence

In the Dialogues Concerning Two New Sciences (1638), Galileo observes that every integer is the root of exactly one square and every square has exactly one root, so that there should be as many squares as integers; yet the squares form a proper part of the integers, so that there should be fewer of them. He concludes that the attributes “equal”, “greater” and “smaller” do not apply to infinite quantities.

Cantor kept the first intuition as a definition: two sets have the same size when their elements can be matched one-to-one. The second intuition, that a proper part is smaller than the whole, is then a theorem about finite sets which fails for infinite ones. This lesson sets up the definitions and proves the facts about finite sets that the comparison relies on.

1.1 Functions and inverses

All functions in this course are total: a function $f : A \to B$ assigns to every $a \in A$ an element $f(a) \in B$. For $X \subseteq A$, the image of $X$ is $f(X) = \{f(a) : a \in X\}$, and for $Y \subseteq B$ the preimage of $Y$ is $f^{-1}(Y) = \{a \in A : f(a) \in Y\}$. The identity function of $A$ is written $\mathrm{id}_A$.

Definition 1.1.#

A function $f : A \to B$ is

1. injective if for all $a, a' \in A$, $a \neq a'$ implies $f(a) \neq f(a')$;
2. surjective if $f(A) = B$, that is, every $b \in B$ is of the form $f(a)$;
3. bijective if it is both injective and surjective.

A composition of injections is an injection, and a composition of surjections is a surjection: if $f : A \to B$ and $g : B \to C$ are surjective and $c \in C$, pick $b$ with $g(b) = c$, then $a$ with $f(a) = b$. Hence a composition of bijections is a bijection.

Lemma 1.2.#

Let $f : A \to B$.

1. If $A \neq \emptyset$, then $f$ is injective if and only if there is $g : B \to A$ with $g \circ f = \mathrm{id}_A$ (a left inverse).
2. If there is $g : B \to A$ with $f \circ g = \mathrm{id}_B$ (a right inverse), then $f$ is surjective.
3. $f$ is bijective if and only if there is $g : B \to A$ with $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$. Such a $g$ is unique; it is written $f^{-1}$ and is itself a bijection.

Proof of Lemma 1.2.

1. Suppose $f$ injective, and fix $a_0 \in A$. For $b \in f(A)$ there is exactly one $a$ with $f(a) = b$, by injectivity; let $g(b)$ be this $a$. For $b \notin f(A)$, let $g(b) = a_0$. Then $g(f(a)) = a$ for every $a \in A$. Conversely, if $g \circ f = \mathrm{id}_A$ and $f(a) = f(a')$, then $a = g(f(a)) = g(f(a')) = a'$.
2. Every $b \in B$ equals $f(g(b))$, so it lies in $f(A)$.
3. If $f$ is bijective, define $g(b)$ as the unique $a$ with $f(a) = b$; both identities hold. Conversely, the first identity gives injectivity, as in item 1, and the second gives surjectivity, by item 2. If $g$ and $g'$ both satisfy the two identities, then $g = g \circ (f \circ g') = (g \circ f) \circ g' = g'$. Finally $f^{-1}$ has $f$ as a two-sided inverse, so it is bijective.

Remark 1.3.#

The converse of item 2 — every surjection $f : A \to B$ has a right inverse — requires choosing, for each $b \in B$, one element of the non-empty set $f^{-1}(\{b\})$. For arbitrary sets, this is exactly the axiom of choice. No choice is needed when $A \subseteq \nat$: take $g(b)$ to be the least element of $f^{-1}(\{b\})$. This device, replacing an arbitrary choice by a least element, is used repeatedly in this course.

1.2 Equipotence

Definition 1.4.#

Two sets $A$ and $B$ are equipotent if there is a bijection from $A$ to $B$. We then write $|A| = |B|$.

Proposition 1.5.#

For all sets $A$, $B$, $C$: $|A| = |A|$; if $|A| = |B|$ then $|B| = |A|$; if $|A| = |B|$ and $|B| = |C|$ then $|A| = |C|$.

Proof of Proposition 1.5.

The identity $\mathrm{id}_A$ is a bijection. If $f : A \to B$ is a bijection, so is $f^{-1} : B \to A$, by Lemma 1.2. A composition of bijections is a bijection.

Example 1.6.#

1. $\nat$ and the set of squares $\{n^2 : n \in \nat\}$ are equipotent, via $n \mapsto n^2$, which is injective on $\nat$ since squaring is strictly increasing on non-negative numbers.
2. $\nat$ and $\nat \setminus \{0\}$ are equipotent, via $n \mapsto n + 1$; more generally, $\nat$ and $\nat \setminus \{0, \dots, k-1\}$ via $n \mapsto n + k$.
3. $\nat$ and the set $E$ of even numbers are equipotent, via $n \mapsto 2n$.
4. The open interval $(-1, 1)$ and $\mathbb R$ are equipotent, via $x \mapsto x / (1 - |x|)$. Its inverse is $y \mapsto y / (1 + |y|)$: if $y = x/(1-|x|)$, then $y$ has the sign of $x$ and $|y| = |x|/(1 - |x|)$, so that $|x| = |y|/(1 + |y|)$ and $x = y/(1+|y|)$. Since every non-empty open interval $(a, b)$ is equipotent to $(-1, 1)$ by an affine map, all non-empty open intervals are equipotent to $\mathbb R$.

In each of the first three examples, a set is equipotent to a proper subset of itself. This is the phenomenon Galileo found paradoxical, and the next section shows that it cannot happen for finite sets.

Remark 1.7.

The notation $|A| = |B|$ suggests an equality between two objects, the cardinalities of $A$ and $B$. A cardinality can be defined as a set (in ZFC, the least ordinal equipotent to $A$), but this course does not need it: the relation $|A| = |B|$ is defined directly, and $|A|$ on its own is only a notation.

1.3 Finite sets

For $n \in \nat$, write $\underline n = \{0, 1, \dots, n - 1\}$, so that $\underline 0 = \emptyset$.

Definition 1.8.#

A set $A$ is finite if $|A| = |\underline n|$ for some $n \in \nat$, and infinite otherwise.

That $n$ is determined by $A$ — the number of elements of $A$ — is a consequence of the following principle.

Lemma 1.9 (Pigeonhole principle).#

For all $m > n$, there is no injection from $\underline m$ into $\underline n$.

Proof of Lemma 1.9.

By induction on $n$. For $n = 0$: since $m > 0$, the set $\underline m$ contains $0$, and there is no function at all from a non-empty set into $\underline 0 = \emptyset$.

Suppose the statement holds for $n$, and let $f : \underline m \to \underline{n+1}$ be injective, with $m > n + 1$. If $n \notin f(\underline m)$, then $f$ maps $\underline m$ injectively into $\underline n$, which contradicts the induction hypothesis since $m > n$. Otherwise $n = f(k)$ for a unique $k < m$. Let $\tau : \underline m \to \underline m$ exchange $k$ and $m - 1$ and fix every other element. Then $f \circ \tau$ is injective and sends $m - 1$ to $n$; by injectivity, it sends no element of $\underline{m-1}$ to $n$. So its restriction to $\underline{m-1}$ is an injection into $\underline n$, with $m - 1 > n$, which contradicts the induction hypothesis.

Corollary 1.10.#

1. If $|\underline m| = |\underline n|$, then $m = n$.
2. If $A$ is finite, $A$ is not equipotent to any proper subset $B \subsetneq A$.
3. $\nat$ is infinite.

Proof of Corollary 1.10.

1. If $m \neq n$, say $m > n$, a bijection $\underline m \to \underline n$ would be an injection, contradicting Lemma 1.9.
2. Let $\beta : A \to \underline n$ be a bijection, and suppose $h : A \to B$ is a bijection onto $B \subsetneq A$. Pick $a \in A \setminus B$. Then $n \geq 1$; let $\sigma$ be the permutation of $\underline n$ exchanging $\beta(a)$ and $n - 1$. The map $\sigma \circ \beta$ is a bijection $A \to \underline n$ sending $a$ to $n - 1$, so it sends $B \subseteq A \setminus \{a\}$ into $\underline{n-1}$. Then $\sigma \circ \beta \circ h \circ \beta^{-1} \circ \sigma^{-1}$ is an injection from $\underline n$ into $\underline{n-1}$, a contradiction.
3. By item 2, since $\nat$ is equipotent to its proper subset $\nat \setminus \{0\}$.

So a finite set has a well-defined number of elements, and Galileo’s matching is a property of infinite sets only. Dedekind took the converse as a definition: a set is Dedekind-infinite if it is equipotent to a proper subset. That every infinite set is Dedekind-infinite uses the axiom of choice (in a weak form); see Exercise 3.16 in the lesson on countable sets.

1.4 Subpotence

Intuitively, $B$ is at least as large as $A$ if every element of $A$ can be given its own representative in $B$.

Definition 1.11.#

A set $A$ is subpotent to a set $B$ if there is an injection from $A$ into $B$. We then write $|A| \leq |B|$, and $|A| \nleq |B|$ otherwise. We write $|A| < |B|$ if $|A| \leq |B|$ and $|A| \neq |B|$.

If $A \subseteq B$, the inclusion map shows $|A| \leq |B|$. By Lemma 1.9, $|\underline n| < |\underline m|$ whenever $n < m$.

Proposition 1.12.#

The relation $\leq$ is reflexive and transitive: $|A| \leq |A|$, and if $|A| \leq |B|$ and $|B| \leq |C|$, then $|A| \leq |C|$. Moreover, it is compatible with equipotence: if $|A| = |A'|$ and $|B| = |B'|$, then $|A| \leq |B|$ if and only if $|A'| \leq |B'|$.

Proof of Proposition 1.12.

The identity is an injection. If $f : A \to B$ and $g : B \to C$ are injections and $x \neq y$ in $A$, then $f(x) \neq f(y)$ by injectivity of $f$, hence $g(f(x)) \neq g(f(y))$ by injectivity of $g$; so $g \circ f$ is an injection. For the last statement, if $\alpha : A' \to A$ and $\beta : B \to B'$ are bijections and $f : A \to B$ is an injection, then $\beta \circ f \circ \alpha : A' \to B'$ is an injection; the converse is symmetric.

Surjections compare sets in the opposite direction, at least when the domain is a set of integers.

Proposition 1.13.#

If $A \subseteq \nat$ and $f : A \to B$ is surjective, then $|B| \leq |A|$.

Proof of Proposition 1.13.

For $b \in B$, the set $f^{-1}(\{b\})$ is a non-empty set of integers; let $g(b)$ be its least element. Then $f(g(b)) = b$, so $g$ has a left inverse and is injective by Lemma 1.2.

For arbitrary $A$, the same statement holds under the axiom of choice (Remark 1.3). Two questions remain. Is $\leq$ antisymmetric, that is, do $|A| \leq |B|$ and $|B| \leq |A|$ imply $|A| = |B|$? This is the Cantor–Bernstein theorem of the next lesson. Is there a pair of infinite sets with $|A| < |B|$? This is Cantor’s diagonal argument, three lessons ahead.

1.5 Exercises

Exercise 1.14 ★.#

Let $b \notin A$. Show that if $|\nat| \leq |A|$, then $|A \cup \{b\}| = |A|$.

Solution

Let $i : \nat \to A$ be an injection. Define $h : A \cup \{b\} \to A$ by $h(b) = i(0)$, $h(i(n)) = i(n+1)$ for $n \in \nat$, and $h(x) = x$ for $x \in A \setminus i(\nat)$. This is well defined since $i$ is injective. It is injective, since it is injective on each of the three pieces $\{b\}$, $i(\nat)$ and $A \setminus i(\nat)$, whose images $\{i(0)\}$, $i(\nat \setminus \{0\})$ and $A \setminus i(\nat)$ are disjoint. It is surjective, since these three images cover $A$.

Exercise 1.15 ★.#

Show that every subset of a finite set is finite.

Solution

It suffices to treat subsets $S \subseteq \underline m$, by transporting through a bijection. By induction on $m$: for $m = 0$, $S = \emptyset = \underline 0$. If $S \subseteq \underline{m+1}$, then $S' = S \setminus \{m\} \subseteq \underline m$ is in bijection with some $\underline k$ via some $\beta$, by the induction hypothesis. If $m \notin S$, then $S = S'$. Otherwise, extend $\beta$ by $m \mapsto k$; this is a bijection from $S$ to $\underline{k+1}$.

Exercise 1.16 ★★.

Show that if $A$ is finite and $f : A \to A$ is injective, then $f$ is surjective. Show that this fails for $A = \nat$.

Solution

If $f$ were injective and not surjective, then $f$ would be a bijection from $A$ onto the proper subset $f(A) \subsetneq A$, which contradicts Corollary 1.10. For $A = \nat$, the successor $n \mapsto n + 1$ is injective and not surjective.

1.6 Notes and references

The passage on squares and roots is in the First Day of Galileo’s Discorsi (1638). Cantor introduced the comparison of sets by one-to-one correspondences in his papers of 1874 and 1878, under the name Mächtigkeit (power); the term “equipotent” derives from it. Dedekind defined infinite sets as those equipotent to a proper subset in Was sind und was sollen die Zahlen? (1888). For a systematic treatment of cardinality in axiomatic set theory, see Hrbacek and Jech.

• G. Galilei, Discorsi e dimostrazioni matematiche intorno a due nuove scienze, Leiden, 1638.
• G. Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, Journal für die reine und angewandte Mathematik 84 (1878), 242–258.
• R. Dedekind, Was sind und was sollen die Zahlen?, Vieweg, Braunschweig, 1888.
• K. Hrbacek and T. Jech, Introduction to Set Theory, 3rd edition, Marcel Dekker, 1999.