← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 7

Infinite Sets

Taught 17 Aug 2026

Finite Sets

To count a herd is to pair its animals off against $0, 1, 2$ and so on, and to report the number we stopped at. Nothing in that procedure asks what the counting numbers are; it asks for a bijection between the herd and an opening stretch of them. Both are now built, so we can count, and the notion of the same size that counting rests on still makes sense for sets far too large to count.

Comparing Sets by Functions

Definition 7.1 (Equinumerous sets).

Sets $A$ and $B$ are equinumerous, written $A \approx B$ , if there is a bijection $f : A \to B$ . We also say that $A$ and $B$ have the same size.

The definition asks for one bijection and says nothing about how many there are; two sets of three elements are matched up in six different ways, and the definition is satisfied by any of them. It also does not mention counting, so it still makes sense for sets we cannot count.

Proposition 7.2 (Equinumerosity is reflexive, symmetric and transitive).

Let $A$ , $B$ and $C$ be sets.

$A \approx A$ .
If $A \approx B$ then $B \approx A$ .
If $A \approx B$ and $B \approx C$ then $A \approx C$ .

Discussion.

Each part is an existence claim about bijections, so each is proved by producing one, and in every case the bijection we need has already been built. For the first, the identity map on $A$ is its own inverse, and a map with an inverse is a bijection by the theorem on invertibility. The second and third are conditionals, so we start from the bijections the hypothesis gives: from one bijection, the theorem that the inverse is a bijection; from two, the theorem that bijections compose. No part uses anything about the elements of the sets.

Proof.

For the first, $\mathrm{id}_A \circ \mathrm{id}_A = \mathrm{id}_A$ , so $\mathrm{id}_A$ is invertible and hence a bijection from $A$ to $A$ .

For the second, let $f : A \to B$ be a bijection. Its inverse $f^{-1} : B \to A$ is a bijection, so $B \approx A$ .

For the third, let $f : A \to B$ and $g : B \to C$ be bijections. Then $g \circ f : A \to C$ is a bijection, so $A \approx C$ .

Remark.

Those are the three properties of an equivalence relation, and yet $\approx$ is not one, because it is not a relation at all in our sense: a relation on $S$ is a subset of $S \times S$ , and there is no set of all sets for $S$ to be. Fix a set $X$ , however, and $\approx$ restricted to $\mathcal{P}(X)$ is an honest equivalence relation on an honest set, so it partitions $\mathcal{P}(X)$ into classes of subsets of the same size. That is how the notion is used in practice, and the general statement is a convenience of language rather than a claim about a set of pairs.

Example 7.3.

Write $L_n$ for the cut $\{x \in \mathbb{N}_0 \mid x < n\}$ , so that $L_3 = \{0, 1, 2\}$ . If $a$ , $b$ and $c$ are distinct then $\{a, b, c\} \approx L_3$ , witnessed by $a \mapsto 0$ , $b \mapsto 1$ , $c \mapsto 2$ . Any other listing of the three letters gives another bijection, and the definition does not prefer one.

Problem 7.1.

Show that $A \times B \approx B \times A$ for all sets $A$ and $B$ , and that $(A \times B) \times C \approx A \times (B \times C)$ .

Problem 7.2.

Show that $A \approx B$ implies $\mathcal{P}(A) \approx \mathcal{P}(B)$ . Which of the theorems on images and preimages does your bijection rest on?

Counting

The cuts are the sets we count against: $L_n$ collects the $n$ numbers below $n$ . First we record how they grow, which every induction below uses.

Proposition 7.4 (The cuts grow by one point).

$L_0 = \emptyset$ , and for every $n \in \mathbb{N}_0$ ,

L_{s(n)} = L_n \cup \{n\}, \qquad n \notin L_n.

Discussion.

There are three assertions and each is a statement about which elements a cut holds, so each unfolds to a comparison with $n$ . That $L_0$ is empty is a negative claim, ruled out by the proposition that every natural number is at least zero together with trichotomy, which forbids $x < 0$ once $0 \leqslant x$ is known. The equation is an equality of sets, so it splits into two inclusions, and both come from asking where $x$ sits relative to $n$ : to the left, $x < s(n)$ leaves the alternatives $x < n$ and $x = n$ once the proposition that nothing lies strictly between $n$ and $s(n)$ has removed the third; to the right, $x < n$ or $x = n$ gives $x < s(n)$ because $n < s(n)$ and $<$ is transitive. The last assertion is anti-reflexivity read off the definition of the cut.

Proof.

An $x \in \mathbb{N}_0$ satisfies $0 \leqslant x$ , so $x < 0$ would violate trichotomy; hence $L_0 = \emptyset$ .

Let $x < s(n)$ . Trichotomy gives $x < n$ , $x = n$ or $n < x$ , and the last would place $x$ strictly between $n$ and $s(n)$ , which nothing does. So $x \in L_n \cup \{n\}$ . Conversely $n < s(n)$ by the corollary that adding a positive element moves you up, so $x = n$ gives $x < s(n)$ , and $x < n$ gives $x < s(n)$ by transitivity. Hence $L_{s(n)} = L_n \cup \{n\}$ .

Finally $\neg(n < n)$ , so $n \notin L_n$ .

Definition 7.5 (Finite and infinite sets).

A set $A$ is finite if $A \approx L_n$ for some $n \in \mathbb{N}_0$ , and infinite otherwise.

So $\emptyset$ is finite, since $L_0 = \emptyset$ , and each $L_n$ is finite by way of its identity map. The definition offers some $n$ , and to speak of the number of elements we must know that no two cuts are matched by a bijection. The next few results prove this. The main tool is the simplest rearrangement: a map exchanging two points and leaving the rest alone.

Definition 7.6 (Transposition).

Let $S$ be a set and let $a, b \in S$ . The transposition $\tau_{a,b} : S \to S$ is the function given by

\tau_{a,b}(a) \defeq b, \qquad \tau_{a,b}(b) \defeq a, \qquad \tau_{a,b}(x) \defeq x \ \text{ for every other } x \in S.

When $a = b$ the three clauses agree and $\tau_{a,b}$ is the identity map on $S$ .

Proposition 7.7 (A transposition is its own inverse).

Let $S$ be a set and let $a, b \in S$ . Then $\tau_{a,b} \circ \tau_{a,b} = \mathrm{id}_S$ , and $\tau_{a,b}$ is a bijection.

Discussion.

Two assertions, the second following from the first. The first is an equality of functions, so by equality of functions we compare values at an arbitrary point of $S$ , and the definition splits the points into three cases, each settled by reading the definition twice. The second is then the theorem on invertibility, which makes a map with a two-sided inverse a bijection; the first assertion offers $\tau_{a,b}$ itself as that inverse, so nothing further need be built.

Proof.

Write $\tau \defeq \tau_{a,b}$ and let $x \in S$ . If $x = a$ then $\tau(\tau(a)) = \tau(b) = a$ ; if $x = b$ then $\tau(\tau(b)) = \tau(a) = b$ ; and otherwise $\tau(\tau(x)) = \tau(x) = x$ . So $\tau \circ \tau = \mathrm{id}_S$ , and $\tau$ is invertible, hence a bijection from $S$ to $S$ .

Proposition 7.8 (Bijections remove points).

Let $f : A \to B$ be a bijection and let $a \in A$ . Then $A \setminus \{a\} \approx B \setminus \{f(a)\}$ .

Discussion.

We need a bijection between the two smaller sets, and the only map we have is $f$ , so we restrict it and check the two halves of bijectivity. Injectivity is inherited, since a restriction of an injective map is injective. For the values, injectivity is again what we use: a point other than $a$ cannot be sent to $f(a)$ , so the restriction does land in $B \setminus \{f(a)\}$ ; and surjectivity of $f$ supplies, for each $y$ in that set, a preimage, which cannot be $a$ because $y \neq f(a)$ .

Proof.

Let $g$ be the restriction of $f$ to $A \setminus \{a\}$ . If $x \neq a$ then $f(x) \neq f(a)$ by injectivity, so $g$ takes its values in $B \setminus \{f(a)\}$ , and $g$ is injective because $f$ is.

Let $y \in B \setminus \{f(a)\}$ . By surjectivity $y = f(x)$ for some $x \in A$ , and $x \neq a$ since $y \neq f(a)$ . So $y = g(x)$ , and $g$ is a bijection onto $B \setminus \{f(a)\}$ .

Proposition 7.9 (Removing a point from a cut).

Let $n \in \mathbb{N}_0$ and let $k \in L_{s(n)}$ . Then $L_{s(n)} \setminus \{k\} \approx L_n$ .

Discussion.

The previous proposition removes a point and its image under a bijection, so the plan is to build a bijection of $L_{s(n)}$ with itself that carries $k$ to $n$ and then remove $n$ , where the result is the cut $L_n$ by the proposition on how cuts grow. The transposition of $k$ and $n$ does exactly that, and it is a bijection by the proposition just proved, so nothing needs checking. The case $k = n$ is the growth proposition on its own, the transposition there being the identity.

Proof.

If $k = n$ then $L_{s(n)} \setminus \{n\} = L_n$ by the proposition on how cuts grow, and a set is equinumerous with itself.

Suppose $k \neq n$ and let $\tau \defeq \tau_{k,n}$ be the transposition of $k$ and $n$ on $L_{s(n)}$ , which is a bijection by the proposition above. Since $\tau(k) = n$ , the proposition on removing points gives

L_{s(n)} \setminus \{k\} \approx L_{s(n)} \setminus \{n\} = L_n.

Theorem 7.10 (No cut injects into a shorter one).

For every $n \in \mathbb{N}_0$ there is no injection $f : L_{s(n)} \to L_n$ .

Discussion.

The claim is a universally quantified non-existence statement, so we induct on $n$ and argue each case by contradiction. At $n = 0$ the target is empty while the source is not, and a function must name a value at every point of its domain, so there is no such function. For the step we assume no injection $L_{s(n)} \to L_n$ and suppose one is given from $L_{s(s(n))}$ to $L_{s(n)}$ . The extra point of the source is $s(n)$ , and by injectivity no other point is sent to its value $c$ , so removing both leaves an injection from $L_{s(n)}$ into $L_{s(n)} \setminus \{c\}$ . The previous proposition says that set is a copy of $L_n$ , and composing with a bijection onto $L_n$ gives an injection the inductive hypothesis forbids.

Proof.

We induct on $n$ . For $n = 0$ the cut $L_1$ is $\{0\}$ and $L_0$ is empty, so a function $L_1 \to L_0$ would have to give a value $f(0) \in \emptyset$ . There is none.

Suppose there is no injection $L_{s(n)} \to L_n$ , and let $f : L_{s(s(n))} \to L_{s(n)}$ be injective. Since $s(n) < s(s(n))$ , the value $c \defeq f(s(n))$ is defined. If $x < s(n)$ then $x \neq s(n)$ , so $f(x) \neq c$ by injectivity; hence the restriction of $f$ to $L_{s(n)}$ is an injection taking its values in $L_{s(n)} \setminus \{c\}$ . Composing it with a bijection from $L_{s(n)} \setminus \{c\}$ onto $L_n$ , which the previous proposition supplies, yields an injection $L_{s(n)} \to L_n$ , contrary to the hypothesis. So no such $f$ exists, and induction completes the proof.

Corollary 7.11 (Cuts of different length are not equinumerous).

If $L_m \approx L_n$ then $m = n$ .

Proof.

Suppose $m < n$ . Then $L_m \subset L_n$ by transitivity, and $m \in L_n$ , so $L_{s(m)} = L_m \cup \{m\} \subset L_n$ . A bijection $L_n \to L_m$ restricted to $L_{s(m)}$ is then an injection $L_{s(m)} \to L_m$ , which the theorem forbids. The same argument with $m$ and $n$ exchanged rules out $n < m$ , so trichotomy leaves $m = n$ .

Definition 7.12 (Cardinality of a finite set).

Let $A$ be finite. The unique $n \in \mathbb{N}_0$ with $A \approx L_n$ is the cardinality of $A$ , written $\#A$ , and we say $A$ has $n$ elements.

Uniqueness is the corollary, and without it the notation would not be well defined. Some authors write $|A|$ for the same number.

Corollary 7.13 (Cardinality classifies finite sets).

Let $A$ and $B$ be finite. Then $A \approx B$ if and only if $\#A = \#B$ .

Proof.

Write $m \defeq \#A$ and $n \defeq \#B$ , so $A \approx L_m$ and $B \approx L_n$ . If $A \approx B$ then $L_m \approx A \approx B \approx L_n$ by symmetry and transitivity, so $m = n$ by the previous corollary. Conversely if $m = n$ then $A \approx L_m = L_n \approx B$ .

Example 7.14.

$\#\emptyset = 0$ and $\#L_n = n$ . A finite set has cardinality $0$ exactly when it is empty, since a bijection onto $L_0 = \emptyset$ from a non-empty set would have to name an element of $\emptyset$ . If $a \neq b$ then $\#\{a\} = 1$ and $\#\{a, b\} = 2$ , since $L_1 = \{0\}$ and $L_2 = \{0, 1\}$ .

Proposition 7.15 (Adjoining a point).

Let $A$ be finite and let $b \notin A$ . Then $A \cup \{b\}$ is finite and $\#(A \cup \{b\}) = s(\#A)$ .

Discussion.

Both assertions come from one bijection, which we build and check. We hold a bijection $g$ from $A$ onto $L_n$ , and the set to be counted has exactly one extra point, while the cut $L_{s(n)}$ has exactly one point more than $L_n$ , namely $n$ itself. So we extend $g$ by sending $b$ to $n$ . That the extension is a function uses $b \notin A$ , which stops the two clauses from disagreeing anywhere; that it is injective uses $n \notin L_n$ , which stops the new value from repeating an old one; and that it is surjective is the growth proposition, which says $L_{s(n)}$ holds nothing beyond $L_n$ and $n$ .

Proof.

Put $n \defeq \#A$ and let $g : A \to L_n$ be a bijection. Define $g' : A \cup \{b\} \to L_{s(n)}$ by $g'(x) \defeq g(x)$ for $x \in A$ and $g'(b) \defeq n$ . Since $b \notin A$ , every point of the domain falls under exactly one clause, so $g'$ is a function, and its values lie in $L_{s(n)} = L_n \cup \{n\}$ .

For injectivity, two points of $A$ are separated by $g$ , and a point of $A$ is separated from $b$ because $g(x) \in L_n$ while $n \notin L_n$ . For surjectivity, an element of $L_{s(n)}$ is either $n$ , which is $g'(b)$ , or an element of $L_n$ , which is $g(x)$ for some $x \in A$ by surjectivity of $g$ . So $A \cup \{b\} \approx L_{s(n)}$ .

Corollary 7.16 (Removing a point).

Let $A$ be finite and non-empty and let $a \in A$ . Then $A \setminus \{a\}$ is finite and $\#A = s\bigl(\#(A \setminus \{a\})\bigr)$ .

Proof.

Let $f : A \to L_n$ be a bijection, where $n \defeq \#A$ . Since $A$ is non-empty, $n \neq 0$ , so the theorem on predecessors gives $n = s(k)$ for some $k$ . The proposition on removing points from bijections gives $A \setminus \{a\} \approx L_{s(k)} \setminus \{f(a)\}$ , and the proposition on removing a point from a cut gives $L_{s(k)} \setminus \{f(a)\} \approx L_k$ . So $A \setminus \{a\}$ is finite with cardinality $k$ , and $\#A = s(k)$ .

Subsets and Images

Theorem 7.17 (Subsets of a finite set).

Let $A$ be finite and let $B \subset A$ . Then $B$ is finite and $\#B \leqslant \#A$ . If moreover $B \subsetneq A$ then $\#B < \#A$ .

Discussion.

The first sentence quantifies over all subsets of all finite sets, so we induct on the cardinality, taking for the predicate at $n$ the statement that every subset of every set with $n$ elements is finite with cardinality at most $n$ . At $n = 0$ the ambient set is empty and so is the subset. For the step we peel off a point $a$ of the ambient set, leaving a set the hypothesis governs, and split on whether $a$ belongs to the subset: if not, the subset is already inside the smaller set; if so, we apply the hypothesis to the subset with $a$ removed and put $a$ back, which raises both cardinalities by one successor.

The second sentence uses properness. A point $a$ of $A$ outside $B$ can be adjoined to $B$ without leaving $A$ , so the first sentence applies to $B \cup \{a\}$ and yields $s(\#B) \leqslant \#A$ ; and $s(m) \leqslant n$ forces $m < n$ , since $s(m) + b = m + s(b)$ and $s(b)$ is positive.

Proof.

We first record two small facts about successors, both read off the clauses for addition. If $m \leqslant n$ then $n = m + b$ for some $b \in \mathbb{N}_0$ , so $s(n) = s(m + b) = s(m) + b$ by addition from the left, and hence $s(m) \leqslant s(n)$ . If $s(m) \leqslant n$ then $n = s(m) + b = s(m + b) = m + s(b)$ , and $s(b)$ is positive, so $m < n$ .

For the first assertion we induct on $n$ , proving that every subset of every set of cardinality $n$ is finite with cardinality at most $n$ . If $n = 0$ then the ambient set is empty, so $B = \emptyset$ and $\#B = 0$ .

Suppose the claim holds at $n$ , let $\#A = s(n)$ and let $B \subset A$ . Since $s(n) \neq 0$ , the set $A$ is non-empty; choose $a \in A$ and put $A' \defeq A \setminus \{a\}$ , which has cardinality $n$ by the corollary on removing a point. If $a \notin B$ then $B \subset A'$ , so the hypothesis makes $B$ finite with $\#B \leqslant n \leqslant s(n)$ . If $a \in B$ then $B \setminus \{a\} \subset A'$ , so $B \setminus \{a\}$ is finite with cardinality $m \leqslant n$ ; adjoining $a$ makes $B$ finite with $\#B = s(m) \leqslant s(n)$ .

For the second assertion, let $B \subsetneq A$ and choose $a \in A \setminus B$ . Then $B \cup \{a\} \subset A$ , so the first assertion gives $s(\#B) = \#(B \cup \{a\}) \leqslant \#A$ , and therefore $\#B < \#A$ .

Corollary 7.18 (No finite set is equinumerous with a proper subset).

Let $A$ be finite and $B \subsetneq A$ . Then $A \not\approx B$ .

Proof.

The theorem gives $\#B < \#A$ , so $\#B \neq \#A$ by anti-reflexivity, and finite sets of different cardinality are not equinumerous.

Proposition 7.19 (Images of a finite set).

Let $A$ be finite and let $f : A \to B$ be a function. Then the image $f(A)$ is finite with $\#f(A) \leqslant \#A$ , and $\#f(A) = \#A$ if and only if $f$ is injective.

Discussion.

The inequality is proved by induction on $\#A$ : remove a point $a$ from $A$ , apply the hypothesis to what remains, and observe that the image gains at most the single value $f(a)$ , so it grows by at most one successor.

The biconditional needs no second induction, because each direction is already available. If $f$ is injective it is a bijection onto its range, so the two cardinalities agree. If $f$ is not injective, two distinct points share a value, so deleting one of them changes nothing about the image; the inequality applied to the smaller set then gives a strict drop, since a proper subset of a finite set is strictly smaller. Those two together are the biconditional, the second read contrapositively.

Proof.

For the inequality we induct on $n = \#A$ . If $n = 0$ then $A = \emptyset$ and $f(A) = \emptyset$ .

Suppose the claim holds for sets of cardinality $n$ and let $\#A = s(n)$ . Choose $a \in A$ and put $A' \defeq A \setminus \{a\}$ , of cardinality $n$ . Since $A = A' \cup \{a\}$ we have $f(A) = f(A') \cup \{f(a)\}$ , and $f(A')$ is finite with $\#f(A') \leqslant n$ by hypothesis. If $f(a) \in f(A')$ then $f(A) = f(A')$ and $\#f(A) \leqslant n \leqslant s(n)$ . Otherwise adjoining the point gives $\#f(A) = s(\#f(A')) \leqslant s(n)$ .

If $f$ is injective then $f$ is a bijection from $A$ onto $f(A)$ , so $\#f(A) = \#A$ . If $f$ is not injective, choose $x \neq y$ in $A$ with $f(x) = f(y)$ . Every value of $f$ is then already taken on $A \setminus \{x\}$ , since $f(x) = f(y)$ and $y \neq x$ , so $f(A) = f(A \setminus \{x\})$ and

\#f(A) \leqslant \#(A \setminus \{x\}) < \#A,

the second inequality because $A \setminus \{x\}$ is a proper subset. So equality holds exactly when $f$ is injective.

The Pigeonhole Principle

Theorem 7.20 (Injections, surjections and size).

Let $A$ and $B$ be finite.

If there is an injection $f : A \to B$ then $\#A \leqslant \#B$ .
If there is a surjection $f : A \to B$ then $\#B \leqslant \#A$ .

Discussion.

Both parts turn the given function into a statement about the image, and then apply the two results just proved. An injection is a bijection onto its range, so $A$ and $f(A)$ have the same cardinality, and $f(A)$ is a subset of $B$ , which the theorem on subsets bounds by $\#B$ . A surjection has range all of $B$ , so $\#B$ is the cardinality of an image, which the proposition on images bounds by $\#A$ . Notice that no choice of preimages is made anywhere, so neither part appeals to the axiom of choice.

Proof.

For the first, $f$ is a bijection from $A$ onto $f(A)$ , so $\#A = \#f(A)$ ; and $f(A) \subset B$ , so $\#f(A) \leqslant \#B$ by the theorem on subsets.

For the second, surjectivity gives $f(A) = B$ , so $\#B = \#f(A) \leqslant \#A$ by the proposition on images.

Corollary 7.21 (Pigeonhole principle).

Let $A$ and $B$ be finite with $\#B < \#A$ . Then no function $A \to B$ is injective, and no function $B \to A$ is surjective.

Proof.

An injection $A \to B$ would give $\#A \leqslant \#B$ , and a surjection $B \to A$ would give $\#A \leqslant \#B$ as well; either contradicts $\#B < \#A$ by trichotomy.

Example 7.22.

Among thirteen people, two were born in the same month: the map sending each person to the month of their birth goes from a set of thirteen elements to one of twelve, so it cannot be injective, and two people share a value. The principle says the pair exists but gives no way to find it.

Theorem 7.23 (Injective, surjective and bijective agree on a finite set).

Let $A$ be finite and let $f : A \to A$ . Then $f$ is injective if and only if it is surjective, and either condition makes $f$ a bijection.

Discussion.

The statement is a biconditional between two conditions on the same map, so we prove each direction, and the last clause follows: a bijection is by definition an injection that is also a surjection, so once the two conditions are equivalent, each one gives both.

Going forwards, injectivity makes the image as large as the whole, and a subset of a finite set with the full cardinality cannot be proper, so the image is everything. Going backwards we argue by contradiction, because failure of injectivity is what we can compute with: a repeated value lets us delete a point without shrinking the image, so the image of a proper subset would have to be all of $A$ , and the proposition on images bounds it by something strictly smaller.

Proof.

Suppose $f$ is injective. Then $\#f(A) = \#A$ by the proposition on images, and $f(A) \subset A$ , so $f(A) = A$ by the theorem on subsets, since a proper subset would have strictly smaller cardinality. Hence $f$ is surjective.

Suppose $f$ is surjective and not injective, so $f(x) = f(y)$ for some $x \neq y$ . Then $f(A) = f(A \setminus \{x\})$ , and surjectivity makes this all of $A$ , so

\#A = \#f(A \setminus \{x\}) \leqslant \#(A \setminus \{x\}) < \#A,

which anti-reflexivity forbids. So $f$ is injective.

In either case $f$ is both injective and surjective, hence a bijection.

Remark.

Finiteness is needed. The successor map $s : \mathbb{N}_0 \to \mathbb{N}_0$ is injective by the third Peano condition and is not surjective, since $0$ is not a successor. So on $\mathbb{N}_0$ the two conditions come apart, and the theorem cannot be extended by weakening its hypothesis.

Problem 7.3.

Let $A$ and $B$ be finite with $\#A = \#B$ and let $f : A \to B$ be injective. Show that $f$ is a bijection.

Problem 7.4.

Let $A$ be finite and let $f : A \to A$ satisfy $f \circ f = f$ . Show that $f = \mathrm{id}_A$ if $f$ is injective, and describe what $f$ can be otherwise.

Sums and Products

Counting a union means laying one cut after another, so we first say how a cut breaks into an opening piece and a shifted one.

Proposition 7.24 (Splitting a cut).

Let $m, n \in \mathbb{N}_0$ and put $S \defeq \{m + i \mid i \in L_n\}$ . Then

L_{m+n} = L_m \cup S, \qquad L_m \cap S = \emptyset,

and $i \mapsto m + i$ is a bijection from $L_n$ onto $S$ .

Discussion.

Three assertions, each about the position of a number relative to $m$ . The equality is a set equality, hence two inclusions. From left to right, trichotomy puts $x$ either below $m$ , which is the first part, or at or above it, in which case $x = m + i$ for a difference $i$ , and the difference is below $n$ because subtracting $m$ from both sides of $x < m + n$ leaves $i < n$ . From right to left, both parts are checked against $m + n$ directly, using that adding a positive element moves you up. Disjointness is trichotomy once more, since the members of $S$ are at least $m$ and the members of $L_m$ are strictly below it. The last assertion is uniqueness of differences, which says $m + i = m + i'$ can happen only for $i = i'$ ; surjectivity holds because $S$ was defined as the set of such values.

Proof.

Let $x < m + n$ . If $x < m$ then $x \in L_m$ . Otherwise $m \leqslant x$ , so $x = m + i$ for some $i \in \mathbb{N}_0$ by the description of the associated order. From $m + i < m + n$ we get $m + n = (m + i) + b = m + (i + b)$ for some positive $b$ , by the laws of addition, so $n = i + b$ by uniqueness of differences and hence $i < n$ . Thus $x \in S$ .

Conversely, $m \leqslant m + n$ , so $x < m$ gives $x < m + n$ by mixed transitivity. And if $i < n$ then $n = i + b$ with $b$ positive, so $m + n = (m + i) + b$ and $m + i < m + n$ .

If $x \in L_m \cap S$ then $x < m$ and $m \leqslant x$ , which trichotomy forbids, so the intersection is empty.

Finally, $i \mapsto m + i$ is injective by uniqueness of differences and surjective onto $S$ by the definition of $S$ .

Theorem 7.25 (Cardinality of a disjoint union).

Let $A$ and $B$ be finite and disjoint. Then $A \cup B$ is finite and

\#(A \cup B) = \#A + \#B.

Discussion.

We must exhibit a bijection from $A \cup B$ onto the cut $L_{m+n}$ , and the splitting proposition cuts that target into the two pieces we need. So we define the map in two clauses, counting the points of $A$ by their own bijection and the points of $B$ by theirs, shifted up by $m$ so as to land in the second piece. Disjointness of $A$ and $B$ means each point falls under exactly one clause, so we have a function. Injectivity then has three cases, two inside a piece, which the two bijections handle, and one across the pieces, which the disjointness of the split handles. Surjectivity is the other half of the split.

Proof.

Put $m \defeq \#A$ and $n \defeq \#B$ , and let $g : A \to L_m$ and $h : B \to L_n$ be bijections. Define

k : A \cup B \to L_{m+n}, \qquad k(x) \defeq \begin{cases} g(x) & \text{if } x \in A, \\ m + h(x) & \text{if } x \in B. \end{cases}

Since $A \cap B = \emptyset$ , each point of the domain falls under exactly one clause, so $k$ is a function, and its values lie in $L_{m+n}$ by the splitting proposition.

For injectivity, two points of $A$ are separated by $g$ ; two points of $B$ are separated by $h$ together with the injectivity of $i \mapsto m + i$ ; and a point of $A$ cannot collide with a point of $B$ , since their values lie in the two disjoint pieces of the split. For surjectivity, an element of $L_{m+n}$ lies either in $L_m$ , hence is $g(x)$ for some $x \in A$ , or is $m + i$ with $i \in L_n$ , hence is $m + h(y) = k(y)$ for some $y \in B$ .

So $A \cup B \approx L_{m+n}$ , which is the assertion.

Corollary 7.26 (Cardinality of a union).

Let $A$ and $B$ be finite. Then $A \cup B$ is finite and

\#(A \cup B) + \#(A \cap B) = \#A + \#B.

Proof.

The sets $B \setminus A$ and $A \cap B$ are subsets of $B$ , hence finite. Now $A \cup B = A \cup (B \setminus A)$ with the two parts disjoint, so $\#(A \cup B) = \#A + \#(B \setminus A)$ ; and $B = (B \setminus A) \cup (A \cap B)$ with the two parts disjoint, so $\#B = \#(B \setminus A) + \#(A \cap B)$ . Adding $\#(A \cap B)$ to the first equation and substituting the second gives

\#(A \cup B) + \#(A \cap B) = \#A + \#(B \setminus A) + \#(A \cap B) = \#A + \#B,

by the laws of addition.

Remark.

The familiar form of that identity subtracts the overlap, and we have written it with everything on the right instead. Subtraction is available to us only when the answer stays in $\mathbb{N}_0$ , which it does here, but stating the law as an equation between sums spares us from checking that each time.

Problem 7.5.

Let $A$ , $B$ and $C$ be finite. Show that

\#(A \cup B \cup C) + \#(A \cap B) + \#(A \cap C) + \#(B \cap C) = \#A + \#B + \#C + \#(A \cap B \cap C).

Theorem 7.27 (Cardinality of a product).

Let $A$ and $B$ be finite. Then $A \times B$ is finite and $\#(A \times B) = \#A \cdot \#B$ , with multiplication as the problems of the natural-numbers chapter defined it.

Discussion.

Multiplication was defined by recursion on its second argument, with the clauses $x \cdot 0 = 0$ and $x \cdot s(n) = x \cdot n + x$ , so we induct on $\#B$ following them. At $0$ the set $B$ is empty and so is the product, since a pair needs a second coordinate. For the step we split $B$ into a smaller set and a single extra point $b$ , which splits $A \times B$ into two disjoint pieces, one governed by the inductive hypothesis and one a copy of $A$ . The theorem on disjoint unions adds the two cardinalities, and the resulting sum is the right-hand side of the second clause of the multiplication recursion.

Proof.

We induct on $n \defeq \#B$ . If $n = 0$ then $B = \emptyset$ , so $A \times B = \emptyset$ and $\#(A \times B) = 0 = \#A \cdot 0$ .

Suppose the claim holds for every $B$ of cardinality $n$ , and let $\#B = s(n)$ . Choose $b \in B$ and put $B' \defeq B \setminus \{b\}$ , of cardinality $n$ . A pair $(x, y)$ with $y \in B$ has either $y \in B'$ or $y = b$ , and not both, so

A \times B = (A \times B') \cup (A \times \{b\}), \qquad (A \times B') \cap (A \times \{b\}) = \emptyset,

using equality of ordered pairs to read off the second coordinate. The map $x \mapsto (x, b)$ is a bijection from $A$ onto $A \times \{b\}$ , again by equality of ordered pairs, so that piece has cardinality $\#A$ ; and $A \times B'$ has cardinality $\#A \cdot n$ by hypothesis. The theorem on disjoint unions gives

\#(A \times B) = \#A \cdot n + \#A = \#A \cdot s(n),

the last step being the second clause of the definition of multiplication.

Problem 7.6.

Show that a union of finitely many finite sets is finite. State the claim carefully first: it is an assertion about an indexed family whose index set is a cut.

Problem 7.7.

Let $A$ be finite with $\#A = n$ . Show that $\#\mathcal{P}(A) = 2^n$ , with powers as the problems of the natural-numbers chapter defined them.

Problem 7.8.

Let $A$ and $B$ be finite. Show that the Cartesian power $A^B$ , the set of functions from $B$ to $A$ , is finite with $\#(A^B) = (\#A)^{\#B}$ .

Extrema of Finite Sets

Proposition 7.28 (Finite subsets of an ordered set have extrema).

Let $M$ be a totally ordered set and let $S \subset M$ be finite and non-empty. Then $S$ has a minimum and a maximum.

Discussion.

The hypothesis is about an arbitrary finite non-empty set, so the induction runs on the cardinality and starts at $1$ rather than $0$ , which is allowed by induction from an arbitrary starting point. A set of cardinality $1$ has a single element, which is both extrema by reflexivity of the order. For the step we remove a point $a$ , apply the hypothesis to what remains, which is still non-empty, and then compare $a$ with the maximum found there: the two are comparable because the order is total, and whichever of the two is the larger is the maximum of the whole. Minima are the same argument with the inequalities reversed, so we write only one of them out.

Proof.

We induct on $n = \#S$ , beginning at $n = 1$ . Then $S \approx L_1 = \{0\}$ , so $S = \{a\}$ for a single $a$ , and $a \leqslant a$ makes it both the minimum and the maximum.

Suppose every subset of cardinality $n \geqslant 1$ has both extrema, and let $\#S = s(n)$ . Choose $a \in S$ and put $S' \defeq S \setminus \{a\}$ , which has cardinality $n \geqslant 1$ and so is non-empty. Let $M'$ be its maximum. Since $M$ is totally ordered, $a$ and $M'$ are comparable. If $a \leqslant M'$ then $M'$ is an upper bound of $S$ lying in $S$ , hence its maximum; if $M' \leqslant a$ then $a$ is such a bound, hence the maximum. The argument for the minimum reverses the inequalities.

Corollary 7.29 (The natural numbers are infinite).

$\mathbb{N}_0$ and $\mathbb{N}$ are infinite.

Proof.

The order on $\mathbb{N}_0$ is strict and linear, so the associated $\leqslant$ is a total order. Were $\mathbb{N}_0$ finite, it would be non-empty and so would have a maximum $M$ ; but $s(M) \in \mathbb{N}_0$ and $M < s(M)$ , contradicting that $M$ is an upper bound. The same argument applies to $\mathbb{N}$ , whose element $s(M)$ is positive because it is a successor.

Problem 7.9.

Show that a set with an infinite subset is infinite, and that the image of a finite set under any function is finite.

Comparing Sets

For an infinite set there is no $n \in \mathbb{N}_0$ counting it, so we cannot compare numbers. Injections and bijections still make sense, though, and for finite sets the next theorem matches each inequality with a condition on functions.

Comparing Finite Sets

Theorem 7.30 (Comparing finite sets).

Let $A$ and $B$ be finite sets. Then

$\#A \leqslant \#B$ if and only if there is an injection $A \to B$ ;
$\#A = \#B$ if and only if $A \approx B$ ;
$\#A < \#B$ if and only if there is an injection $A \to B$ but no bijection $A \to B$ .

Discussion.

Write $m \defeq \#A$ and $n \defeq \#B$ and fix bijections $f : L_m \to A$ and $g : L_n \to B$ ; every part is then a matter of conjugating a map between the cuts into a map between the sets, or the other way about.

For the first part, one direction is already the theorem on injections and size. The other builds the injection: $m \leqslant n$ gives $L_m \subset L_n$ , whose inclusion map is injective, and $g \circ \iota \circ f^{-1}$ is then an injection $A \to B$ , being a composite of injections. The second part is the corollary that cardinality classifies finite sets, read in both directions.

The third is the first two put together. If $m < n$ then the first part supplies an injection, and a bijection would force $m = n$ by the second, which trichotomy forbids. Conversely an injection gives $m \leqslant n$ and the absence of a bijection gives $m \neq n$ , and those two are what $m < n$ abbreviates.

Proof.

Write $m \defeq \#A$ and $n \defeq \#B$ , and fix bijections $f : L_m \to A$ and $g : L_n \to B$ .

For the first part, suppose $m \leqslant n$ . Then $L_m \subset L_n$ , since $x < m \leqslant n$ gives $x < n$ , and the inclusion $\iota : L_m \to L_n$ is injective. So $g \circ \iota \circ f^{-1} : A \to B$ is an injection. Conversely an injection $A \to B$ gives $\#A \leqslant \#B$ by the theorem on injections and size.

The second part is the corollary that cardinality classifies finite sets.

For the third, let $m < n$ . The first part gives an injection $A \to B$ , and a bijection would give $m = n$ by the second part, contradicting trichotomy. Conversely, an injection gives $m \leqslant n$ by the first part and the absence of a bijection gives $m \neq n$ by the second, so $m < n$ .

The three right-hand sides make sense whether or not the sets are finite, so they may be taken as definitions in general. By the theorem, the new definitions agree with the old ones for finite sets.

Definition 7.31 (Comparing sizes).

Let $A$ and $B$ be sets, finite or not. We write

$\#A \leqslant \#B$ if there is an injection $A \to B$ ;
$\#A = \#B$ if $A \approx B$ ;
$\#A < \#B$ if there is an injection $A \to B$ but no bijection $A \to B$ .

For finite sets these agree with the numerical readings, by the theorem. The symbol $\#A$ still names a natural number only when $A$ is finite; in general the three displays above are single assertions about functions, and it is the assertion, not the symbol $\#A$ standing alone, that has been defined. What $\#A$ may be taken to name in general is settled at the end of the chapter.

Read informally, $\#A < \#B$ says that $B$ is roomy enough to hold an injective copy of $A$ and still has something left over, in the strong sense that every injection misses something.

Proposition 7.32 (Reflexivity and transitivity).

For all sets $A$ , $B$ , $C$ :

$\#A \leqslant \#A$ ;
if $\#A \leqslant \#B$ and $\#B \leqslant \#C$ then $\#A \leqslant \#C$ .

Discussion.

Both parts unfold to claims about injections, and both follow from basic facts about injections. Reflexivity needs an injection $A \to A$ , and the identity map is one. Transitivity needs an injection $A \to C$ out of injections $A \to B$ and $B \to C$ , and their composite is injective: if the composite identifies two points, the outer map identifies their images and the inner map identifies them.

Proof.

The identity $\mathrm{id}_A$ is injective, so $\#A \leqslant \#A$ .

Let $f : A \to B$ and $g : B \to C$ be injections. If $g(f(x)) = g(f(y))$ then $f(x) = f(y)$ by injectivity of $g$ , and $x = y$ by injectivity of $f$ . So $g \circ f$ is an injection $A \to C$ and $\#A \leqslant \#C$ .

Problem 7.10.

Prove or refute each of the following, for arbitrary sets $A$ , $B$ and $C$ .

If $\#A \leqslant \#B$ then $\#(A \times C) \leqslant \#(B \times C)$ .
$\#(A \setminus B) \leqslant \#B$ .

Problem 7.11.

Let $B$ be non-empty. Show that $\#A \leqslant \#(A \times B)$ for every set $A$ .

The Schröder–Bernstein Theorem

The last proposition does not give antisymmetry. For finite sets it is immediate, since $m \leqslant n \leqslant m$ forces $m = n$ ; in general it is a harder theorem.

Theorem 7.33 (Schröder–Bernstein).

Let $A$ and $B$ be sets with $\#A \leqslant \#B$ and $\#B \leqslant \#A$ . Then $A \approx B$ .

Discussion.

We are given injections $f : A \to B$ and $g : B \to A$ and must build a bijection out of them. Neither alone will do: $f$ may miss part of $B$ and $g$ may miss part of $A$ . The idea is to use $f$ on some of $A$ and the inverse of $g$ on the rest, and the problem is to decide where the boundary falls. The points where we have no choice are those of $A \setminus g(B)$ , which have no $g$ -preimage at all, so $f$ must be used there; and then $f$ must be used at $g(f(x))$ for each such $x$ , since otherwise that point would be sent back to $f(x)$ , which is already taken. Iterating gives a family $A_0, A_1, A_2, \ldots$ built by the recursion theorem, and their union $C$ is the region where $f$ is used.

With the boundary fixed, three checks remain. The map is defined everywhere, because a point outside $C$ is in particular outside $A_0$ , hence has a $g$ -preimage, unique by injectivity. It is injective on each of the two regions separately, and the two cannot collide, because a collision would carry a point of $C$ one step further along the chain and so put an element of $C$ outside $C$ . It is surjective by chasing a given $b$ backwards: if $g(b)$ lies outside $C$ it is where $b$ comes from, and if it lies inside $C$ it lies in some $A_n$ with $n$ a successor, which exhibits $b$ as a value of $f$ .

Proof.

Let $f : A \to B$ and $g : B \to A$ be injections. The recursion theorem, applied in $\mathcal{P}(A)$ with the map $X \mapsto g(f(X))$ , gives exactly one family $\{A_n\}_{n \in \mathbb{N}_0}$ with

A_0 \defeq A \setminus g(B), \qquad A_{s(n)} \defeq g\bigl(f(A_n)\bigr),

and we put $C \defeq \bigcup_{n \in \mathbb{N}_0} A_n$ . The two injections run the pieces alternately into one another,

\begin{array}{ccccccc} A: & A_0 & & A_1 & & A_2 & \cdots \\ & \big\downarrow {\scriptstyle f} & \nearrow {\scriptstyle g} & \big\downarrow {\scriptstyle f} & \nearrow {\scriptstyle g} & \big\downarrow {\scriptstyle f} & \\ B: & f(A_0) & & f(A_1) & & f(A_2) & \cdots \end{array}

and $C$ is the whole of the top row. On it the bijection will follow the downward arrows; off it every point has a $g$ -preimage, and the bijection will run back up them. Define

h : A \to B, \qquad h(x) \defeq \begin{cases} f(x) & \text{if } x \in C, \\ \text{the unique } b \text{ with } g(b) = x & \text{if } x \notin C. \end{cases}

The second clause makes sense: $x \notin C$ gives $x \notin A_0$ , so $x \in g(B)$ , and the preimage is unique because $g$ is injective. So $h$ is a function.

For injectivity, suppose $h(x) = h(y)$ . If both points lie in $C$ then $f(x) = f(y)$ gives $x = y$ ; if neither does then applying $g$ to both sides gives $x = y$ . Suppose then $x \in C$ and $y \notin C$ , so $f(x) = h(y)$ and hence $y = g(f(x))$ . Since $x \in C$ we have $x \in A_n$ for some $n$ , so $y \in g(f(A_n)) = A_{s(n)} \subset C$ , contradicting $y \notin C$ .

For surjectivity, let $b \in B$ and put $x \defeq g(b)$ . If $x \notin C$ then $h(x) = b$ by the second clause. If $x \in C$ then $x \in A_n$ for some $n$ , and $n \neq 0$ because $x \in g(B)$ ; so $n = s(k)$ by the theorem on predecessors, and $x \in g(f(A_k))$ gives $x = g(f(z))$ for some $z \in A_k$ . Injectivity of $g$ gives $b = f(z)$ , and $z \in C$ , so $b = h(z)$ .

Hence $h$ is a bijection and $A \approx B$ .

The proof gives the bijection in two pieces, one for the chained points and one for the rest, rather than as a single formula. What the applications use is only that it exists.

Example 7.34 (Informal).

Assuming you know the real numbers, write $R$ for them and consider the closed interval $[0,1]$ and the open interval $(0,1)$ . The inclusion of $(0,1)$ in $[0,1]$ is an injection one way. In the other direction $x \mapsto \tfrac{x}{2} + \tfrac{1}{4}$ is injective and carries $[0,1]$ into $(0,1)$ , since $0$ goes to $\tfrac14$ and $1$ to $\tfrac34$ . Schröder–Bernstein therefore supplies a bijection between the two intervals, although neither of the injections we wrote is surjective.

Problem 7.12.

Schröder–Bernstein is sometimes read as saying that injections $f : A \to B$ and $g : B \to A$ are each bijections. Exhibit sets $A$ and $B$ with injections both ways, neither of which is surjective.

Theorem 7.35 (Transitivity for strict comparison).

Let $A$ , $B$ and $C$ be sets.

If $\#A < \#B$ and $\#B < \#C$ then $\#A < \#C$ .
If $\#A < \#B$ and $\#B \leqslant \#C$ then $\#A < \#C$ .
If $\#A \leqslant \#B$ and $\#B < \#C$ then $\#A < \#C$ .

Discussion.

Each part asserts the existence of an injection and the non-existence of a bijection, so each splits in two, and the first half is the previous proposition in every case, since a strict comparison contains a weak one. The second half is where Schröder–Bernstein is needed, and it is used contrapositively: a bijection $A \to C$ would let us pull an injection $B \to C$ back to an injection $B \to A$ , and with the injection $A \to B$ already in hand the theorem would return $A \approx B$ , which the strict hypothesis forbids. We write out the first part and leave the other two, which run the same way, to the problems.

Proof.

For the first part, the two hypotheses supply injections $A \to B$ and $B \to C$ , so $\#A \leqslant \#C$ by the previous proposition.

Suppose $A \approx C$ and let $\varphi : C \to A$ be a bijection. Composing $\varphi$ with an injection $B \to C$ gives an injection $B \to A$ , so $\#B \leqslant \#A$ . Since $\#A < \#B$ gives $\#A \leqslant \#B$ , Schröder–Bernstein yields $A \approx B$ , contradicting $\#A < \#B$ . So no bijection $A \to C$ exists and $\#A < \#C$ .

Comparability

Reflexive, transitive, antisymmetric: the comparison behaves like an order. What an order on the natural numbers also had was trichotomy, and for sizes that is a separate matter, since nothing so far rules out two sets neither of which injects into the other.

Theorem 7.36 (Comparability).

Let $A$ and $B$ be sets. Then $\#A \leqslant \#B$ or $\#B \leqslant \#A$ .

Discussion.

An injection defined on all of $A$ is what we want and cannot build directly, so we build the largest injection defined on part of $A$ and show that largest one leaves nothing out. The candidates are the injective functions whose domain is a subset of $A$ and whose values lie in $B$ ; each is a subset of $A \times B$ , so comprehension collects them into a set, which inclusion orders.

To apply Zorn’s lemma we must show every chain has an upper bound, and we take the union of the chain: it is a function because two pairs with the same first coordinate lie in a common member of the chain, since members of a chain are comparable, and it is injective for the same reason with the coordinates exchanged. The empty chain is covered by the empty function. Zorn then supplies a maximal element $p$ , and maximality is used contrapositively: if $p$ missed a point of $A$ and also missed a point of $B$ , the pair of them could be added to $p$ , giving a strictly larger candidate. So one of the two is not missed, and the two cases give the two halves of the conclusion, the second by inverting $p$ .

Proof.

Let $M$ be the set of $p \in \mathcal{P}(A \times B)$ that are injective functions whose domain is a subset of $A$ , ordered by inclusion. The empty function belongs to $M$ , and inclusion is a partial order.

Let $K \subset M$ be a chain and put $q \defeq \bigcup K$ , a subset of $A \times B$ . If $(x, b)$ and $(x, b')$ lie in $q$ , they lie in members $p$ and $p'$ of $K$ , which are comparable, so both pairs lie in the larger one; that member is a function, so $b = b'$ . Hence $q$ is a function, with domain the union of the domains. The same argument with the coordinates exchanged shows $q$ is injective. So $q \in M$ and $q$ is an upper bound of $K$ , and $M$ is inductively ordered.

Zorn’s lemma gives a maximal $p \in M$ . Suppose $\operatorname{dom} p \neq A$ and $\operatorname{im} p \neq B$ , and choose $a \in A \setminus \operatorname{dom} p$ and $b \in B \setminus \operatorname{im} p$ . Then $p \cup \{(a, b)\}$ is again an injective function with domain inside $A$ , and it properly contains $p$ , contradicting maximality.

So $\operatorname{dom} p = A$ , in which case $p$ is an injection $A \to B$ ; or $\operatorname{im} p = B$ , in which case the inverse of $p$ on its range is an injection $B \to A$ .

Corollary 7.37 (Trichotomy for sizes).

For any sets $A$ and $B$ , exactly one of $\#A < \#B$ , $\#A = \#B$ , $\#B < \#A$ holds.

Proof.

Comparability gives $\#A \leqslant \#B$ or $\#B \leqslant \#A$ . If both hold then $A \approx B$ by Schröder–Bernstein; if only the first holds then $\#A < \#B$ , and if only the second then $\#B < \#A$ . So at least one of the three holds. No two hold together: $A \approx B$ makes both strict comparisons fail by definition, and $\#A < \#B$ together with $\#B < \#A$ would give $A \approx B$ by Schröder–Bernstein, contradicting either.

Remark.

Comparability was proved from Zorn’s lemma, and it is in fact equivalent to the axiom of choice, so it is not a free consequence of the other axioms. Schröder–Bernstein, by contrast, used nothing but the recursion theorem. So comparability needs the axiom of choice, while Schröder–Bernstein does not.

Cantor’s Theorem

Theorem 7.38 (Cantor's theorem).

For every set $S$ we have $\#S < \#\mathcal{P}(S)$ .

Discussion.

By the definition the claim splits in two: an injection $S \to \mathcal{P}(S)$ , and no bijection. The injection is the map sending a point to the set holding just that point, and it is injective because a singleton determines its element.

For the second half we take an arbitrary $f : S \to \mathcal{P}(S)$ and produce a subset that is not one of its values, which denies surjectivity and so denies bijectivity. A set differs from $f(x)$ as soon as it disagrees with it at one element, and the element we use is $x$ itself, so we build the subset that disagrees with $f(x)$ at $x$ for every $x$ at once: take those $x$ that are outside their own value. Comprehension makes that a set and it is a subset of $S$ , so it is eligible to be a value. Supposing it is the value at $a$ , the question whether $a$ belongs to it has a membership criterion that turns each answer into the other, which is Russell’s argument again.

Proof.

The map $x \mapsto \{x\}$ sends $S$ into $\mathcal{P}(S)$ , and $\{x\} = \{y\}$ gives $x = y$ , so it is injective and $\#S \leqslant \#\mathcal{P}(S)$ .

Let $f : S \to \mathcal{P}(S)$ be any function and put

D \defeq \{x \in S \mid x \notin f(x)\},

a set by comprehension and a subset of $S$ , so $D \in \mathcal{P}(S)$ . Suppose $D = f(a)$ for some $a \in S$ . If $a \in D$ then the criterion gives $a \notin f(a) = D$ . If $a \notin D$ then, $a$ being an element of $S$ , the criterion gives $a \in f(a) = D$ . Both are contradictions, so $D$ is not a value of $f$ and $f$ is not surjective.

In particular no bijection $S \to \mathcal{P}(S)$ exists, so $\#S < \#\mathcal{P}(S)$ .

Remark.

The diagonal set is the construction that showed there is no set of all sets, used for a different purpose. There it produced a contradiction from an assumption we then dropped; here it produces one from the assumption that $D$ is a value, and what we drop is surjectivity. Nothing about $S$ was used, so the theorem applies to every set: iterating it gives

\#S < \#\mathcal{P}(S) < \#\mathcal{P}(\mathcal{P}(S)) < \cdots,

a strictly increasing chain with no top, by transitivity for strict comparison.

Problem 7.13.

Show that if $\#A \leqslant \#B$ and $A \approx A'$ and $B \approx B'$ , then $\#A' \leqslant \#B'$ . Transport the injection along the two bijections.

Problem 7.14.

Prove parts 2 and 3 of the theorem on transitivity for strict comparison.

Problem 7.15.

Use Schröder–Bernstein, rather than an explicit pairing, to show that $\#\mathbb{N}_0 = \#(\mathbb{N}_0 \times \mathbb{N}_0)$ once you have an injection each way.

Problem 7.16.

Show that $\#A \leqslant \#B$ implies $\#\mathcal{P}(A) \leqslant \#\mathcal{P}(B)$ .

Problem 7.17.

Deduce from Cantor’s theorem that $n < 2^n$ for every $n \in \mathbb{N}_0$ .

Infinite Sets

A set is infinite when it is not finite, which is a purely negative description: no cut matches it. Cantor found that infinite sets come in different sizes, and Cantor’s theorem above already gives a strictly increasing chain of them. We start with the smallest.

Countable Sets

Definition 7.39 (Countable and uncountable).

A set $A$ is countably infinite if $A \approx \mathbb{N}_0$ , countable if it is finite or countably infinite, and uncountable otherwise.

A bijection $f : \mathbb{N}_0 \to A$ is an infinite sequence in $A$ , so a countably infinite set is one whose elements can be written as a list

(a_0, a_1, a_2, \ldots)

in which every element appears exactly once. Such an $f$ is an enumeration of $A$ . The list is not part of the set, and a set usually admits many.

That the two cases of countability do not overlap is the corollary that $\mathbb{N}_0$ is infinite, since otherwise a finite set could be equinumerous with $\mathbb{N}_0$ .

Proposition 7.40 (Dropping zero).

$\mathbb{N} \approx \mathbb{N}_0$ , so $\mathbb{N}$ is countably infinite.

Discussion.

We must produce a bijection, and we use the successor map, checking three things against the Peano conditions. Its values are positive, since a successor is never $0$ , so it does map into $\mathbb{N}$ . It is injective, which is the third condition verbatim. It is surjective onto $\mathbb{N}$ , which is the theorem on predecessors: every element other than $0$ is a successor.

Proof.

Consider $s : \mathbb{N}_0 \to \mathbb{N}$ . Its values lie in $\mathbb{N}$ , since $s(n) \neq 0$ by the fourth Peano condition. It is injective by the third. It is surjective, since an element of $\mathbb{N}$ is not $0$ and is therefore $s(n)$ for some $n$ by the theorem on predecessors. So $s$ is a bijection and $\mathbb{N}_0 \approx \mathbb{N}$ .

Remark.

Since $\mathbb{N} \subsetneq \mathbb{N}_0$ , an infinite set can be equinumerous with a proper subset of itself, which the corollary of the last chapter shows no finite set can do. Dedekind turned the observation round and took it as the definition of infinite, and we prove below that his definition agrees with ours.

Subsets of the Natural Numbers

Theorem 7.41 (Infinite subsets of the natural numbers).

Every infinite subset $M \subset \mathbb{N}_0$ is countably infinite.

Discussion.

We must produce an enumeration of $M$ , and there is an obvious rule for one: list the smallest element first, then the smallest of those left, and so on. Two things must be checked before this is a definition. The rule at stage $n$ refers to everything listed before $n$ , not merely to the previous entry, so it is the general recursion theorem rather than the plain one that builds the function, taking for its rule the map sending a finite list to the least element of $M$ not on it. And that least element must exist: the elements listed so far form the image of a cut, hence a finite set, so they cannot exhaust the infinite $M$ , and well-ordering then supplies the minimum.

What remains is to check that the enumeration works. It is strictly increasing, because each entry is chosen from a smaller pool than the one before and differs from the entry just removed, and a strictly increasing map is injective by trichotomy. Surjectivity is a least-counterexample argument: if some $m \in M$ never appears, look at the first stage whose entry overshoots $m$ . Everything listed before that stage is below $m$ , so $m$ was still in the pool at that stage, and the minimum chosen there cannot have exceeded it.

Proof.

For a finite sequence $t$ in $\mathbb{N}_0$ , the range $\operatorname{im} t$ is finite, being the image of a cut. So $M \setminus \operatorname{im} t$ is non-empty: otherwise $M \subset \operatorname{im} t$ would make $M$ finite. Define

g : \operatorname{Seq}(\mathbb{N}_0) \to \mathbb{N}_0, \qquad g(t) \defeq \min\bigl(M \setminus \operatorname{im} t\bigr),

which exists by well-ordering. The general recursion theorem gives exactly one $f : \mathbb{N}_0 \to \mathbb{N}_0$ with $f(n) = g(f|_{L_n})$ for every $n$ , that is,

f(n) = \min\bigl(M \setminus \{f(i) \mid i < n\}\bigr).

Every value of $f$ lies in $M$ . The map is strictly increasing: the set from which $f(s(n))$ is chosen is contained in the set from which $f(n)$ is chosen, so $f(n) \leqslant f(s(n))$ by minimality, and $f(s(n)) \neq f(n)$ because $f(n)$ was removed at the later stage. Induction then gives $f(m) < f(n)$ whenever $m < n$ , and trichotomy makes $f$ injective.

Induction also gives $n \leqslant f(n)$ : this holds at $0$ , and if $n \leqslant f(n)$ then $n < f(s(n))$ , so $f(s(n)) < s(n)$ would place $f(s(n))$ strictly between $n$ and $s(n)$ , which nothing does; hence $s(n) \leqslant f(s(n))$ .

Suppose some $m \in M$ is not a value of $f$ . Since $m < s(m) \leqslant f(s(m))$ , the set of $n$ with $m < f(n)$ is non-empty, so well-ordering gives a least such $k$ . Every $i < k$ has $f(i) \leqslant m$ and $f(i) \neq m$ , so $f(i) < m$ ; hence $m$ belongs to $M \setminus \{f(i) \mid i < k\}$ , and minimality of $f(k)$ in that set gives $f(k) \leqslant m$ , contradicting $m < f(k)$ .

So $f$ is a bijection from $\mathbb{N}_0$ onto $M$ .

Characterising At Most Countable Sets

Theorem 7.42 (Characterising countable sets).

Let $M$ be a non-empty set. The following are equivalent.

$M$ is countable.
There is an injection $M \to \mathbb{N}_0$ .
There is a surjection $\mathbb{N}_0 \to M$ .

Discussion.

We prove the three conditions equivalent by a cycle of implications.

From the first to the third: a countably infinite $M$ has a bijection from $\mathbb{N}_0$ , which is a surjection; a finite non-empty $M$ has a bijection from a cut, which we extend to all of $\mathbb{N}_0$ by parking every later index on one fixed point, and parking spoils nothing because surjectivity asks only that every point be hit.

From the third to the second: a surjection has an injective right inverse, and here we can name one without appealing to choice. Each point of $M$ has a non-empty set of preimages inside $\mathbb{N}_0$ , so well-ordering picks out its least preimage, and a right inverse is injective because applying the surjection recovers the point.

From the second to the first: an injection makes $M$ equinumerous with its image, a subset of $\mathbb{N}_0$ , and a subset of $\mathbb{N}_0$ is finite or infinite; in the first case $M$ is finite, and in the second the theorem just proved makes it countably infinite.

Proof.

Suppose $M$ is countable. If $M \approx \mathbb{N}_0$ , a bijection is a surjection. If $M$ is finite and non-empty, let $f : L_n \to M$ be a bijection with $n \neq 0$ , and define $\beta : \mathbb{N}_0 \to M$ by $\beta(k) \defeq f(k)$ for $k < n$ and $\beta(k) \defeq f(0)$ for $k \geqslant n$ . Every point of $M$ is $f(k)$ for some $k < n$ , so $\beta$ is surjective.

Suppose $\beta : \mathbb{N}_0 \to M$ is surjective. For $x \in M$ the preimage $\beta^{-1}(\{x\})$ is a non-empty subset of $\mathbb{N}_0$ , so it has a least element; let $\alpha(x)$ be that element. Then $\beta(\alpha(x)) = x$ for every $x$ , so $\alpha(x) = \alpha(y)$ gives $x = y$ , and $\alpha : M \to \mathbb{N}_0$ is injective.

Suppose $\alpha : M \to \mathbb{N}_0$ is injective. Then $M \approx \alpha(M) \subset \mathbb{N}_0$ . If $\alpha(M)$ is finite then so is $M$ . If $\alpha(M)$ is infinite then $\alpha(M) \approx \mathbb{N}_0$ by the theorem on infinite subsets, so $M \approx \mathbb{N}_0$ by transitivity. Either way $M$ is countable.

Corollary 7.43 (Subsets of countable sets).

Every subset of a countable set is countable.

Proof.

Let $B \subset A$ with $A$ countable. If $B$ is empty it is finite. Otherwise $A$ is non-empty, so there is an injection $A \to \mathbb{N}_0$ by the theorem, and its restriction to $B$ is injective, so $B$ is countable by the theorem again.

Products and Unions

Theorem 7.44 (Pairs of natural numbers).

$\mathbb{N}_0 \times \mathbb{N}_0$ is countably infinite.

Discussion.

By the characterisation it is enough to find one injection into $\mathbb{N}_0$ , and then to observe that the set is not finite. For the injection we enumerate the pairs in diagonals: all pairs with $m + n = 0$ , then those with $m + n = 1$ , and so on. The $k$ th diagonal has $s(k)$ entries, so a pair $(m, n)$ on the diagonal $k = m + n$ should be given the position

j(m, n) \defeq T(k) + m, \qquad T(k) \defeq \sum_{i=1}^{k} i,

where the summation symbol is the one built by recursion in the last chapter but one. Injectivity then rests on the diagonals not overlapping, which is the inequality $T(k) + m < T(k')$ whenever $k < k'$ and $m \leqslant k$ ; it follows from the recursion clause $T(s(k)) = T(k) + s(k)$ . Once the diagonal is known, $m$ and then $n$ are determined by uniqueness of differences. Infinitude is easy: the pairs $(n, 0)$ form a copy of $\mathbb{N}_0$ inside, and a set with an infinite subset is infinite.

Proof.

Write $T(k) \defeq \sum_{i=1}^{k} i$ , so that $T(0) = 0$ and $T(s(k)) = T(k) + s(k)$ .

We first record that $T$ is non-decreasing: if $k \leqslant l$ then $l = k + b$ , and induction on $b$ gives the claim, since $T(k + s(b)) = T(s(k+b)) = T(k+b) + s(k+b)$ is at least $T(k + b)$ , which is at least $T(k)$ by the inductive hypothesis.

Define $j(m, n) \defeq T(m + n) + m$ . Laid out with $m$ down the side and $n$ across, the values run

\begin{array}{c|ccccc} & 0 & 1 & 2 & 3 & \cdots \\ \hline 0 & 0 & 1 & 3 & \boxed{6} & \cdots \\ 1 & 2 & 4 & \boxed{7} & & \\ 2 & 5 & \boxed{8} & & & \\ 3 & \boxed{9} & & & & \\ \vdots & \vdots & & & & \ddots \end{array}

The boxed entries are the pairs with $m + n = 3$ , and they fill the consecutive block from $T(3) = 6$ to $T(3) + 3 = 9$ . What follows is that observation for a general diagonal.

Suppose $j(m, n) = j(m', n')$ and put $k \defeq m + n$ , $k' \defeq m' + n'$ . If $k < k'$ then $k' = k + s(c)$ for some $c$ , so

T(k') = T(s(k + c)) = T(k + c) + k' \geqslant T(k) + k'.

Also $m \leqslant k < k'$ , so $k' = m + b$ for a positive $b$ and $T(k) + k' = (T(k) + m) + b$ , giving $T(k) + m < T(k) + k' \leqslant T(k')$ ; and $T(k') \leqslant T(k') + m'$ . Together these give $j(m, n) < j(m', n')$ , against the supposition. The same argument rules out $k' < k$ , so $k = k'$ by trichotomy. Then $T(k) + m = T(k) + m'$ gives $m = m'$ by uniqueness of differences, and $m + n = m + n'$ gives $n = n'$ likewise. So $j$ is injective and $\mathbb{N}_0 \times \mathbb{N}_0$ is countable.

Finally $n \mapsto (n, 0)$ is injective, so $\mathbb{N}_0 \times \mathbb{N}_0$ has an infinite subset and is therefore infinite.

Corollary 7.45 (Products of countable sets).

If $A$ and $B$ are countable then so is $A \times B$ .

Proof.

If either set is empty the product is empty. Otherwise let $u : A \to \mathbb{N}_0$ and $v : B \to \mathbb{N}_0$ be injections. Then $(x, y) \mapsto (u(x), v(y))$ is injective, by equality of ordered pairs, and composing it with the injection $j$ of the theorem gives an injection $A \times B \to \mathbb{N}_0$ .

Theorem 7.46 (Countable unions of countable sets).

Let $I$ be countable and let $\{A_i\}_{i \in I}$ be an indexed family of countable sets. Then $\bigcup_{i \in I} A_i$ is countable.

Discussion.

The characterisation lets us argue with surjections rather than injections, and a surjection onto the union is easy to describe: run over the indices with one surjection and over each set with another, so that the pair $(m, n)$ names the $n$ th element of the $m$ th set. Two points need care. Countability of $A_i$ says only that a surjection onto it exists, and we need one for every $i$ at once, and this needs the axiom of choice. And the domain of the resulting map is $\mathbb{N}_0 \times \mathbb{N}_0$ rather than $\mathbb{N}_0$ , which the previous theorem fixes, since a countably infinite set admits a bijection from $\mathbb{N}_0$ . Composing the two gives a surjection from $\mathbb{N}_0$ onto the union, which is then countable by the characterisation.

Proof.

Discard the indices with $A_i = \emptyset$ ; the union is unchanged and the smaller index set is still countable. If nothing is left the union is empty, hence countable, so suppose $I \neq \emptyset$ and every $A_i \neq \emptyset$ .

By the characterisation there is a surjection $\gamma : \mathbb{N}_0 \to I$ . For each $i$ the set $S_i$ of surjections $\mathbb{N}_0 \to A_i$ is a non-empty subset of $\mathcal{P}(\mathbb{N}_0 \times A_i)$ , again by the characterisation, so the axiom of choice applied to $\{S_i\}_{i \in I}$ gives a function $i \mapsto \beta_i$ with $\beta_i \in S_i$ for every $i$ .

The map $(m, n) \mapsto \beta_{\gamma(m)}(n)$ is a surjection from $\mathbb{N}_0 \times \mathbb{N}_0$ onto $\bigcup_{i \in I} A_i$ : a point $x$ of the union lies in some $A_i$ , and $i = \gamma(m)$ for some $m$ while $x = \beta_i(n)$ for some $n$ . Composing with a bijection $\mathbb{N}_0 \to \mathbb{N}_0 \times \mathbb{N}_0$ , which the previous theorem supplies, gives a surjection from $\mathbb{N}_0$ onto the union, which is therefore countable.

Remark (Hilbert's hotel).

A hotel with a room for every natural number, all of them occupied, can still take in a new guest: move the occupant of room $n$ to room $s(n)$ and give the newcomer room $0$ . It can take in countably many new guests at once: move the occupant of room $n$ to room $2 \cdot n$ and use the odd rooms, which the remainder classes say are exactly the rooms left free. It can even take in countably many coaches each carrying countably many guests, by the theorem on countable unions. Infinite sizes do not behave like finite ones, and here we have to rely on the propositions above rather than on intuition.

Remark (Informal).

Assuming you know the whole numbers and the fractions: the whole numbers are the union of the natural numbers, their negatives and zero, so the theorem on countable unions makes them countable. Every fraction is determined by a pair of whole numbers, so the corollary on products makes the fractions countable as well. Both arguments go through as soon as those systems are built.

Problem 7.18.

Let $A_1, \ldots, A_n$ be countable. Show that $A_1 \times \cdots \times A_n$ is countable, by induction on $n$ .

Problem 7.19.

Let $A$ be countable. Show that the set $\operatorname{Seq}(A)$ of finite sequences in $A$ is countable, and that the set of finite subsets of $A$ is countable.

Problem 7.20.

Show that the map $j$ of the theorem on pairs is a bijection onto $\mathbb{N}_0$ , not merely an injection. Well-ordering applied to the set of $k$ with $x < T(s(k))$ will locate the diagonal on which $x$ sits.

Problem 7.21.

Let $A$ be countably infinite and let $B$ be finite and non-empty. Show that $A \cup B$ and $A \times B$ are countably infinite.

Problem 7.22.

Write $\mathbb{N}_0 \times \mathbb{N}_0$ as the union of a countably infinite family of pairwise disjoint countably infinite sets.

Finite and Infinite

One question is still open. We defined infinite negatively, as the failure of finiteness, and observed that $\mathbb{N}_0$ has a proper subset of its own size. Whether every infinite set does is still open, and the answer needs the axiom of choice.

Theorem 7.47 (Every infinite set has a countably infinite subset).

Let $A$ be infinite. Then some subset $E \subset A$ is countably infinite.

Discussion.

The plan copies the enumeration of an infinite subset of $\mathbb{N}_0$ : pick an element, then an element not yet picked, and so on. Two things we had there are missing here. There is no order on $A$ , so nothing selects an element for us, and the axiom of choice gives a rule that selects one from every non-empty subset at once. And the rule at each stage refers to all the earlier picks, so it is the general recursion theorem that turns the rule into a function. The recursion never stalls, because the elements picked so far form a finite set and $A$ is infinite, so something is always left. Injectivity is immediate from the construction, since each value is chosen outside the earlier ones, and an injective map from $\mathbb{N}_0$ has range a countably infinite subset.

Proof.

Since $A$ is infinite it is non-empty. Apply the axiom of choice to the family of non-empty subsets of $A$ , indexed by itself, to obtain a function $c$ with $c(X) \in X$ for every non-empty $X \subset A$ .

For a finite sequence $t$ in $A$ the range $\operatorname{im} t$ is finite, so $A \setminus \operatorname{im} t$ is non-empty, since otherwise $A$ would be a subset of a finite set. Define

g : \operatorname{Seq}(A) \to A, \qquad g(t) \defeq c\bigl(A \setminus \operatorname{im} t\bigr),

and let $f : \mathbb{N}_0 \to A$ be the map the general recursion theorem produces, so that

f(n) = c\bigl(A \setminus \{f(i) \mid i < n\}\bigr)

for every $n$ . If $m < n$ then $f(m)$ is one of the elements excluded at stage $n$ , so $f(n) \neq f(m)$ ; with trichotomy this makes $f$ injective. Hence $E \defeq \operatorname{im} f$ satisfies $\mathbb{N}_0 \approx E$ and $E \subset A$ .

Theorem 7.48 (Characterising finite sets).

Let $M$ be a non-empty set. The following are equivalent.

$M$ is finite.
There is a surjection $L_n \to M$ for some $n \in \mathbb{N}$ .
There is an injection $M \to L_n$ for some $n \in \mathbb{N}$ .
There is no injection $\mathbb{N}_0 \to M$ .

When they hold, $\#M$ is the least $n$ of the second kind and equally the least $n$ of the third.

Discussion.

We run a cycle again. From the first to the second, a counting of $M$ is itself a surjection from a cut. From the second to the third, a surjection has an injective right inverse, obtained as before by sending each point to its least preimage, which well-ordering supplies inside the cut. From the third to the fourth, an injection $\mathbb{N}_0 \to M$ followed by an injection $M \to L_n$ would inject $\mathbb{N}_0$ into $L_n$ , and restricting to $L_{s(n)}$ would inject a cut into a shorter one. The last step is the theorem just proved, read contrapositively: an infinite $M$ carries a copy of $\mathbb{N}_0$ , hence an injection $\mathbb{N}_0 \to M$ .

The minimality clause is the two size theorems. A surjection $L_n \to M$ gives $\#M \leqslant n$ by the proposition on images, an injection $M \to L_n$ gives $\#M \leqslant n$ by the theorem on injections and size, and $n = \#M$ is achieved in both cases by a counting of $M$ and its inverse.

Proof.

Suppose $M$ is finite. Being non-empty, $\#M = n$ for some $n \in \mathbb{N}$ , and a bijection $L_n \to M$ is a surjection.

Suppose $\sigma : L_n \to M$ is surjective. For $x \in M$ the preimage $\sigma^{-1}(\{x\})$ is a non-empty subset of $\mathbb{N}_0$ , so it has a least element; sending $x$ to it defines $\iota : M \to L_n$ with $\sigma \circ \iota = \mathrm{id}_M$ , and $\iota$ is injective.

Suppose $\iota : M \to L_n$ is injective and let $\gamma : \mathbb{N}_0 \to M$ be injective. Then $\iota \circ \gamma : \mathbb{N}_0 \to L_n$ is injective, and its restriction to $L_{s(n)}$ is an injection $L_{s(n)} \to L_n$ , which no cut admits. So no such $\gamma$ exists.

Suppose finally that $M$ is not finite. The previous theorem gives a subset $E \subset M$ equinumerous with $\mathbb{N}_0$ , hence a bijection $\mathbb{N}_0 \to E$ , which composed with the inclusion of $E$ in $M$ is an injection $\mathbb{N}_0 \to M$ . That is the fourth condition denied, which completes the cycle.

For the last claim, a surjection $L_n \to M$ gives $\#M = \#\sigma(L_n) \leqslant \#L_n = n$ , and an injection $M \to L_n$ gives $\#M \leqslant n$ ; both bounds are attained by a counting of $M$ , which is a surjection $L_{\#M} \to M$ , and by its inverse.

Theorem 7.49 (Dedekind's characterisation of finiteness).

A set is finite if and only if it is not equinumerous with any proper subset of itself.

Discussion.

One direction is much easier than the other. One of them is the corollary of the first chapter, which said that a finite set is strictly larger than each of its proper subsets, so no bijection is available.

The other is best proved contrapositively: given an infinite $A$ , we produce a proper subset equinumerous with it. The theorem above puts a copy of $\mathbb{N}_0$ inside $A$ , and inside it we can shift along successors, as in $\mathbb{N}_0$ . So we shift inside the copy and do nothing outside it: the points of $A$ off the copy are left where they are, and the $n$ th point of the copy is sent to the $s(n)$ th. The result misses the initial point of the copy and nothing else, which is the proper subset we wanted.

Proof.

If $A$ is finite and $B \subsetneq A$ then $A \not\approx B$ , by the corollary on proper subsets.

Suppose $A$ is infinite. The theorem on countably infinite subsets gives an injection $f : \mathbb{N}_0 \to A$ ; write $E \defeq \operatorname{im} f$ and define

h : A \to A \setminus \{f(0)\}, \qquad h(x) \defeq \begin{cases} f(s(n)) & \text{if } x = f(n), \\ x & \text{if } x \notin E. \end{cases}

Each $x \in E$ is $f(n)$ for exactly one $n$ , since $f$ is injective, so $h$ is a function; and its values avoid $f(0)$ , since $f(s(n)) \neq f(0)$ by injectivity and $x \notin E$ gives $x \neq f(0)$ .

For injectivity, two points of $E$ are separated because $f$ and $s$ are injective, two points outside $E$ are unchanged, and a point of $E$ cannot collide with one outside $E$ because its value lies in $E$ . For surjectivity, a point $x \in A \setminus \{f(0)\}$ outside $E$ is $h(x)$ ; and a point $f(m)$ with $m \neq 0$ is $f(s(k))$ for the predecessor $k$ of $m$ , hence $h(f(k))$ .

So $A \approx A \setminus \{f(0)\}$ , a proper subset of $A$ .

Corollary 7.50 (Finiteness by self-maps).

A set $M$ is finite if and only if every injection $M \to M$ is surjective, and if and only if every surjection $M \to M$ is injective.

Proof.

If $M$ is finite, the theorem on finite self-maps gives both conditions. If $M$ is infinite, the map $h$ built in the last proof is an injection $M \to M$ whose range omits $f(0)$ , so it is injective and not surjective; and its inverse on that range, extended by sending $f(0)$ to itself, is a surjection $M \to M$ that is not injective.

Remark.

Only the second direction of the theorem used the axiom of choice, and used it twice, once to select elements and once through the recursion that strung the selections together. Dedekind took the property in the theorem as his definition of infinite, and without choice his definition and ours are not known to agree: there is no contradiction in a set that is infinite in our sense and yet admits no bijection with a proper subset. We accept choice, so for us the two notions are one.

Problem 7.23.

Show that a set $A$ is infinite if and only if for every $n \in \mathbb{N}_0$ there is an injection $L_n \to A$ .

Problem 7.24.

Let $A$ be infinite and $B$ countable. Show that $A \cup B \approx A$ .

Uncountable Sets

Every infinite set met so far has turned out to be countable, and the closure properties above keep it that way: subsets, products and countable unions of countable sets are all countable. Cantor’s theorem already gives sets that are not, and the same diagonal argument gives an explicit one.

Theorem 7.51 (Cantor's diagonal argument).

Let $A$ be a set with at least two elements. Then the Cartesian power $A^{\mathbb{N}_0}$ , the set of infinite sequences in $A$ , is uncountable.

Discussion.

Uncountable means neither finite nor countably infinite, and the characterisation of countable sets turns that into one statement: no surjection $\mathbb{N}_0 \to A^{\mathbb{N}_0}$ exists. So we assume a surjection, write $a^{(j)}$ for the sequence it puts at $j$ , and build a sequence it has missed.

The sequences are laid out as an infinite array whose $j$ th row is $a^{(j)}$ , and a sequence differs from the $j$ th row as soon as it differs from it in one place. The place we can always name is the $j$ th, on the diagonal of the array, so we build $\alpha$ by walking down the diagonal and disagreeing at every step. Disagreement is possible because $A$ has a second element, and we fix two elements of $A$ once and for all rather than choosing at each step, so the axiom of choice is not needed. Then $\alpha$ differs from every row, so it is not a value of the surjection.

Proof.

Fix $p, q \in A$ with $p \neq q$ , and suppose $\beta : \mathbb{N}_0 \to A^{\mathbb{N}_0}$ is a surjection. Write $a^{(j)} \defeq \beta(j)$ and $a^{(j)}_i \defeq a^{(j)}(i)$ , so the values are laid out as

\begin{array}{c|cccc} & 0 & 1 & 2 & \cdots \\ \hline a^{(0)} & \boxed{a^{(0)}_0} & a^{(0)}_1 & a^{(0)}_2 & \cdots \\ a^{(1)} & a^{(1)}_0 & \boxed{a^{(1)}_1} & a^{(1)}_2 & \cdots \\ a^{(2)} & a^{(2)}_0 & a^{(2)}_1 & \boxed{a^{(2)}_2} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

Define $\alpha : \mathbb{N}_0 \to A$ by $\alpha(j) \defeq p$ if $a^{(j)}_j \neq p$ , and $\alpha(j) \defeq q$ otherwise. Then $\alpha(j) \neq a^{(j)}_j$ for every $j$ , since in the second case $a^{(j)}_j = p \neq q$ .

Now $\alpha \in A^{\mathbb{N}_0}$ , so surjectivity gives $\alpha = a^{(j)}$ for some $j$ , and reading both sides at $j$ gives $\alpha(j) = a^{(j)}_j$ , which is false. So no surjection exists, and $A^{\mathbb{N}_0}$ is neither finite nor countably infinite by the characterisation of countable sets.

The same diagonal argument works for an arbitrary index set.

Theorem 7.52 (A set is smaller than its sequences).

Let $M$ be non-empty and let $A$ have at least two elements. Then $\#M < \#(A^M)$ .

Discussion.

The claim splits into an injection $M \to A^M$ and the absence of a bijection. For the injection we must attach to each point of $M$ a function on $M$ , and we use the point itself: send $m$ to the function that takes one fixed value at $m$ and the other everywhere else. Two distinct points give functions that disagree at either of them, so the assignment is injective.

For the second half the diagonal argument runs verbatim, with $M$ in place of $\mathbb{N}_0$ : given $f : M \to A^M$ , the function that disagrees with $f(m)$ at $m$ , for every $m$ , cannot be a value of $f$ . Nothing in that used the order or the countability of the index set, so only the two fixed elements of $A$ are needed.

Proof.

Fix $p, q \in A$ with $p \neq q$ . For $m \in M$ let $\chi_m : M \to A$ take the value $p$ at $m$ and $q$ elsewhere. If $m_1 \neq m_2$ then $\chi_{m_1}(m_1) = p$ while $\chi_{m_2}(m_1) = q$ , so $\chi_{m_1} \neq \chi_{m_2}$ ; hence $m \mapsto \chi_m$ is an injection $M \to A^M$ and $\#M \leqslant \#(A^M)$ .

Let $f : M \to A^M$ be any function and define $\varphi : M \to A$ by $\varphi(m) \defeq p$ if $f(m)(m) \neq p$ , and $\varphi(m) \defeq q$ otherwise, so that $\varphi(m) \neq f(m)(m)$ for every $m$ . If $\varphi = f(m)$ for some $m$ , reading both sides at $m$ gives $\varphi(m) = f(m)(m)$ , which is false. So $\varphi$ is not a value of $f$ , no $f$ is surjective, and no bijection exists.

Corollary 7.53 (Power sets as sequences).

For every set $M$ we have $\mathcal{P}(M) \approx L_2^{\,M}$ .

Proof.

Send $S \subset M$ to its characteristic function $\chi_S : M \to L_2$ , taking the value $1$ on $S$ and $0$ off it. Distinct subsets differ at some point, where their characteristic functions differ, so the map is injective; and any $\varphi : M \to L_2$ is the characteristic function of $\{x \in M \mid \varphi(x) = 1\}$ , so it is surjective.

So Cantor’s theorem is the previous theorem read at $A = L_2$ , and the diagonal argument that rules out surjections onto $L_2^{\,M}$ is the one that rules out surjections onto $\mathcal{P}(M)$ .

Corollary 7.54 (An uncountable set).

$\mathcal{P}(\mathbb{N}_0)$ is uncountable, and so is $L_2^{\,\mathbb{N}_0}$ .

Proof.

$L_2$ has two elements, so $L_2^{\,\mathbb{N}_0}$ is uncountable by the diagonal argument, and $\mathcal{P}(\mathbb{N}_0)$ is equinumerous with it by the corollary above; a set equinumerous with an uncountable set is uncountable, since countability is defined by the existence of a bijection.

Remark (Informal).

Assuming you know the real numbers, the same argument shows there are uncountably many. List candidate decimal expansions of the numbers between $0$ and $1$ and build a new expansion differing from the $j$ th in its $j$ th digit, avoiding the digit $9$ so as not to fall foul of the two expansions some numbers have; the number it names is missing from the list. Since the fractions are countable, the numbers that are not fractions must be uncountable, for otherwise the reals would be a union of two countable sets.

The same counting argument shows something less expected. The polynomials with fractional coefficients are countable, being determined by finite lists of fractions, and each has finitely many roots, so the numbers that are roots of such a polynomial form a countable set. Uncountably many real numbers are therefore roots of no such polynomial at all, although exhibiting even one takes real work.

Problem 7.25.

Let $A$ be uncountable and let $B \subset A$ be countable. Show that $A \setminus B$ is uncountable.

Problem 7.26.

Deduce from Cantor’s theorem that there is no surjection $M \to \mathcal{P}(M)$ , for any set $M$ .

Cardinal Numbers

We have been writing $\#A \leqslant \#B$ for arbitrary sets without saying what $\#A$ names when $A$ is infinite, and so far we have not needed to: the three relations were defined as statements about functions, and the symbol never occurred alone. It can be given a meaning, using the equivalence classes from the remark of the first section.

Definition 7.55 (Cardinal number).

Fix a set $X$ . The cardinal number of a subset $A \subset X$ is its equivalence class $\#A \in \mathcal{P}(X)/{\approx}$ under equinumerosity. Two subsets of $X$ have the same cardinal number exactly when they are equinumerous.

Remark.

The restriction to a fixed $X$ is needed, since the sets equinumerous with a given one do not form a set. For finite $A$ nothing is lost by reading $\#A$ as the natural number counting it, because the cardinal numbers of finite subsets of $X$ correspond to the cuts, one class for each $n$ with $L_n \subset X$ . A definition free of the ambient $X$ needs the ordinal numbers, which we have not built.

The order has the properties the notation suggests. Reflexivity and transitivity were proved directly, Schröder–Bernstein gives antisymmetry, since two subsets each injecting into the other are equinumerous and so name one class, and comparability makes any two classes comparable. So on $\mathcal{P}(X)/{\approx}$ the relation $\leqslant$ is a total order, with the strict comparison as its strict part.

Definition 7.56 (Arithmetic of cardinal numbers).

For sets $A$ and $B$ define

\#A + \#B \defeq \#\bigl((A \times \{0\}) \cup (B \times \{1\})\bigr), \qquad \#A \cdot \#B \defeq \#(A \times B),

(\#A)^{\#B} \defeq \#(A^B).

The tagged copies in the sum are there because $A$ and $B$ may share elements, and tagging makes disjoint copies of both without disturbing their sizes. That the three operations depend only on the classes and not on the sets chosen to represent them is the transport problem set above. On finite sets they agree with the arithmetic of the first chapter, by the theorems on disjoint unions and products and by the problem on $A^B$ .

Since $\mathcal{P}(M) \approx L_2^{\,M}$ and $\#L_2 = 2$ , the power set records an exponential:

2^{\#M} = \#\mathcal{P}(M),

and Cantor’s theorem reads $\#M < 2^{\#M}$ . Writing $\aleph_0 \defeq \#\mathbb{N}_0$ for the smallest infinite cardinal number, the chain

\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots

climbs for ever, so there is no largest size.

Remark (The continuum hypothesis).

Nothing proved here says whether anything sits between two consecutive terms of that chain. The continuum hypothesis asserts that nothing sits between the first two: there is no set $M$ with $\aleph_0 < \#M < 2^{\aleph_0}$ . Gödel showed in 1938 that it cannot be refuted from the axioms we have listed, choice included, and Cohen showed in 1963 that it cannot be proved from them either, so long as those axioms are consistent at all. It is independent, in the sense the axiom of choice was said to be independent, and one may add it or its negation without introducing a contradiction that was not already there.

Remark.

Cantor’s theorem also settles again a question from the naive chapter. Were there a set $\mathfrak{M}$ holding every set, then $\mathcal{P}(\mathfrak{M})$ would be one of its subsets, so

\#\mathcal{P}(\mathfrak{M}) \leqslant \#\mathfrak{M} < \#\mathcal{P}(\mathfrak{M}),

which trichotomy forbids. That is Cantor’s own argument, and it reaches the conclusion of the proposition on no set of all sets by counting rather than by self-membership.

Problem 7.27.

Show that cardinal addition and multiplication are commutative and associative, and that $\#A \cdot (\#B + \#C) = \#A \cdot \#B + \#A \cdot \#C$ . Each identity is a bijection between the sets involved.

Problem 7.28.

Show that $\aleph_0 + \aleph_0 = \aleph_0$ and $\aleph_0 \cdot \aleph_0 = \aleph_0$ , and explain which theorems of this chapter each one is.

Problem 7.29.

Show that $A \approx B$ and $C \approx D$ imply $A^C \approx B^D$ .

Problem 7.30.

Show that $(A \times B)^C \approx A^C \times B^C$ for all sets $A$ , $B$ and $C$ .

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

The last sheet gave the checker the order on the carrier and the sets separation carves out. This chapter counts, and counting needs two things the checker has not had: a map read between two sets rather than across the whole universe, and the natural numbers as objects of that universe, so that the cuts have something to hold.

Maps between two sets

A map has so far been an arrow f : Obj → Obj on everything at once, and Injective f and Surjective f asked their conditions everywhere. A map of this chapter has a domain and a codomain, so the same conditions are written on the sets they are asserted of, and each is the statement the definitions of a surjection and an injection make it:

MapsTo f A B   is   ∀ x, x ∈ A → f x ∈ B
InjOn f A      is   ∀ x y, x ∈ A → y ∈ A → f x = f y → x = y
SurjOn f A B   is   ∀ y, y ∈ B → ∃ x, x ∈ A ∧ f x = y
BijOn f A B    is   MapsTo f A B ∧ InjOn f A ∧ SurjOn f A B

Being those statements and not merely equivalent to them, they are opened with intro and used by applying them, in the way A ⊆ B has been since the sets sheet. A BijOn splits three ways at once, so obtain ⟨hm, hi, hs⟩ takes one apart and refine ⟨?_, ?_, ?_⟩ puts one together.

Example.

A map injective everywhere is injective on any set. The converse fails, which is why the two conditions are kept apart.

Example.

The values of $f$ on $A$ lie in $B$ , which is where $g$ is known to do its work.

Exercise 7.10.

A restriction of an injection is an injection.

Exercise 7.11.

The codomain may be enlarged freely.

Exercise 7.12.

The first part of the theorem that bijections compose, read on two sets.

Exercise 7.13.

Its second part.

Exercise 7.14.

Only the first map need be injective for the composite to be.

Exercise 7.15.

The inverse of a bijection is a bijection. The checker cannot choose preimages, so the inverse arrives as a hypothesis rather than being built; what is left is the second part of Proposition 7.2 .

Comparing sizes

Two sets are compared by the functions running between them, which is what Definition 7.1 and Definition 7.31 say, so the two comparisons are typed as the existence statements they are:

A ≈ B   is   ∃ f : Obj → Obj, BijOn f A B
A ≼ B   is   ∃ f : Obj → Obj, MapsTo f A B ∧ InjOn f A

typed \approx and \preceq. The second is $\#A \leqslant \#B$ ; the strict comparison is not notation of its own, being the second together with the denial of the first. A witness is supplied by use or as the first component of refine ⟨_, ?_, ?_⟩, and it is written as a function, fun x => x for the identity.

Example.

The first part of Proposition 7.2 . Each of the three conditions is read at a point, and the identity satisfies all three without any work.

Exercise 7.16.

The empty function.

Exercise 7.17.

A subset is no larger than the set it sits in.

Exercise 7.18.

A bijection is in particular an injection.

Exercise 7.19.

The second part of Proposition 7.32 .

Exercise 7.20.

The third part of Proposition 7.2 .

Exercise 7.21.

Problem 7.13 : a comparison transported along two bijections.

Exercise 7.22.

Proposition 7.8 .

Exercise 7.23.

Problem 7.16 . The map sends a subset of $A$ to its image. (Harder.)

Cantor’s theorem

Exercise 7.24.

The first half of Cantor’s theorem.

Exercise 7.25.

And the second, which is Problem 7.26 . The diagonal set is {x ∈ S | x ∉ f x}, and it is a subset of $S$ before it is anything else.

The natural numbers as objects

The carrier ℕ of the Peano sheet is a type of its own, and the cuts are sets, so the two have to be brought together before a cut can be written down. ↑n, typed \up, is the object the number n names; ω is the set of all of them, which is $\mathbb{N}_0$ ; and L n is the cut. Their criteria are the definitions:

x ∈ ω     is   ∃ k : ℕ, x = ↑k
x ∈ L n   is   ∃ k : ℕ, k < n ∧ x = ↑k

so a membership is built with use or ⟨_, _, _⟩ and taken apart with obtain ⟨k, hk, he⟩. That distinct numbers name distinct objects is Num.inj, and Finite A is ∃ n : ℕ, A ≈ L n, which is Definition 7.5 verbatim.

Example.

The witness is the number itself, and the equation it has to satisfy is an identity.

Example.

A strict inequality is a positive difference, and no positive difference reaches $0$ . It is listed below as Nat.not_lt_zero, so the exercises may lean on it.

Exercise 7.26.

The first part of Proposition 7.4 .

Exercise 7.27.

Its last part.

Exercise 7.28.

Every cut sits inside $\mathbb{N}_0$ .

Exercise 7.29.

And the cuts grow with their index.

Exercise 7.30.

The middle part of Proposition 7.4 , which every induction of this chapter turns on.

Exercise 7.31.

A cut counts itself.

Exercise 7.32.

And the empty set is counted by the cut that holds nothing.

Exercise 7.33.

A set with one point in it. (Harder.)

Exercise 7.34.

A finite set injects into $\mathbb{N}_0$ , which is the easy half of the characterisation of countability.

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name
refine e	give the proof with holes left in it
have h : p := …	record an intermediate result
show p	restate the goal in an equal form
use w	give a witness for ∃
specialize h a	instantiate a ∀ hypothesis
rw [h]	rewrite with an equation, ← to go backwards
rfl	both sides compute to the same thing
decide / norm_num	settle a closed computation
tauto	close a goal that is true by pure logic
induction n with k ih	the fifth Peano condition: prove the goal at 0, then at succ k from ih

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a
Set.ext	∀ {A B : Obj}, (∀ x : Obj, x ∈ A ↔ x ∈ B) → A = B — extensionality: sets with the same elements are equal
Set.ext_iff	∀ {A B : Obj}, A = B ↔ (∀ x : Obj, x ∈ A ↔ x ∈ B) — extensionality and substitution, in one biconditional
Set.subset_antisymm	∀ {A B : Obj}, A ⊆ B → B ⊆ A → A = B — mutual inclusion is equality
Set.empty_subset	∀ {A : Obj}, ∅ ⊆ A — the empty set is a subset of every set
Set.pair_eq	∀ {a b c d : Obj}, ((a, b) = (c, d)) ↔ (a = c ∧ b = d) — two ordered pairs are equal exactly when their coordinates are
Nat.succ_inj	∀ {m n : ℕ}, succ m = succ n → m = n — the third Peano condition: the successor is injective
Nat.succ_ne_zero	∀ (n : ℕ), succ n ≠ 0 — the fourth: zero is nobody's successor
Nat.pred	∀ {n : ℕ}, n ≠ 0 → ∃ m : ℕ, n = succ m — predecessors: everything but zero is a successor
Nat.add_zero	∀ (m : ℕ), m + 0 = m — the first clause of addition
Nat.add_succ	∀ (m n : ℕ), m + succ n = succ (m + n) — the second clause of addition
Nat.zero_add	∀ (n : ℕ), 0 + n = n — addition from the left
Nat.succ_add	∀ (m n : ℕ), succ m + n = succ (m + n) — addition from the left, at a successor
Nat.add_assoc	∀ (m n p : ℕ), (m + n) + p = m + (n + p) — addition is associative
Nat.add_comm	∀ (m n : ℕ), m + n = n + m — addition is commutative
Nat.add_ne_zero	∀ {a : ℕ} (b : ℕ), a ≠ 0 → a + b ≠ 0 — positivity is absorbing
Nat.mul_zero	∀ (m : ℕ), m * 0 = 0 — the first clause of multiplication
Nat.mul_succ	∀ (m n : ℕ), m * succ n = m * n + m — the second clause of multiplication
Nat.zero_mul	∀ (m : ℕ), 0 * m = 0 — multiplication from the left
Nat.succ_mul	∀ (m n : ℕ), succ m * n = m * n + n — multiplication from the left, at a successor
Nat.add_right_cancel	∀ {m n k : ℕ}, m + k = n + k → m = n — cancellation, from the last sheet
Nat.add_eq_zero	∀ {m n : ℕ}, m + n = 0 → m = 0 ∧ n = 0 — a sum is zero only when both parts are, from the last sheet
Nat.mul_comm	∀ (m n : ℕ), m * n = n * m — multiplication is commutative, from the last sheet
Nat.mul_add	∀ (m n p : ℕ), m * (n + p) = m * n + m * p — multiplication distributes over addition, from the last sheet
Nat.mul_assoc	∀ (m n p : ℕ), (m * n) * p = m * (n * p) — multiplication associates, from the problems of the last chapter
Nat.add_mul	∀ (m n p : ℕ), (m + n) * p = m * p + n * p — distributivity on the other side
Nat.add_left_cancel	∀ {a m n : ℕ}, a + m = a + n → m = n — uniqueness of differences
Nat.lt_trichotomy	∀ (m n : ℕ), m < n ∨ m = n ∨ n < m — trichotomy, from the theorem that ℕ is strictly ordered
Nat.lt_irrefl	∀ (n : ℕ), ¬(n < n) — anti-reflexivity, from the last sheet
Nat.lt_trans	∀ {m n p : ℕ}, m < n → n < p → m < p — transitivity of the strict order, from the last sheet
Nat.lt_succ_self	∀ (n : ℕ), n < succ n — every number is below its successor, from the last sheet
Nat.not_lt_zero	∀ {n : ℕ}, ¬(n < 0) — nothing lies below zero
Nat.lt_succ_iff	∀ {m n : ℕ}, m < succ n ↔ m < n ∨ m = n — nothing lies strictly between n and succ n
Num.inj	∀ {m n : ℕ}, ↑m = ↑n → m = n — distinct numbers name distinct objects of ω

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b