Cantor's theorem

Theorem

Cantor's theorem

T-007Home MU-101Threads logic · structure

Statement

Let \( A \) be a set (an object of the universe of ZF set theory, not a proper class), and let \( \mathcal{P}(A) = \{ X : X \subseteq A \} \) be its power set, which exists by the Power Set axiom. Then there is an injection \( A \to \mathcal{P}(A) \), but there is no surjection \( f : A \to \mathcal{P}(A) \); in particular there is no bijection between \( A \) and \( \mathcal{P}(A) \). In the language of cardinality: \( |A| \lt |\mathcal{P}(A)| \), where \( |A| \le |B| \) means "an injection \( A \to B \) exists" and \( |A| \lt |B| \) means "\( |A| \le |B| \) and no bijection \( A \to B \) exists". The theorem holds for every set: empty, finite, countable, or of arbitrarily large infinite cardinality, and its proof uses only Power Set, Separation and Extensionality — no Choice.

Why it matters

Cantor's theorem is the engine that generates the entire hierarchy of infinities. Before it, "infinite" was a single undifferentiated notion; after it, one has \( |\mathbb{N}| \lt |\mathcal{P}(\mathbb{N})| \lt |\mathcal{P}(\mathcal{P}(\mathbb{N}))| \lt \cdots \), an endless strictly increasing tower of infinite cardinalities. It shows there is no largest set and no "set of all sets", and its diagonal method — producing an object that differs from the \(a\)-th listed object at position \(a\) — became one of the most reused proof templates in mathematics: uncountability of \( \mathbb{R} \), the halting problem, Gödel incompleteness, and Tarski's undefinability of truth are all diagonal arguments at heart.

Within a first course on proof, it is also the cleanest nontrivial example of a proof by contradiction driven by a self-referential definition, and of the discipline needed to handle the definitions of injection, surjection and cardinal comparison precisely.

Hypotheses

Hypothesis.\( A \) is a set, not a proper class. Apply the argument to the class \( V \) of all sets and the "power class" is \( V \) itself (every set of sets is a set), so one would conclude \( |V| \lt |V| \) — this is Cantor's paradox, and it is precisely the observation that forces \( V \) to be a proper class, not a counterexample-free zone where the theorem quietly holds.

Hypothesis.The full power set \( \mathcal{P}(A) \) is the codomain. Replace \( \mathcal{P}(A) \) by the set \( [A]^{\lt\omega} \) of merely finite subsets of \( A \): for \( A = \mathbb{N} \) the finite subsets are countable (code a finite set by \( \sum_{n \in X} 2^n \)), so \( |[\mathbb{N}]^{\lt\omega}| = |\mathbb{N}| \) and the strict inequality fails.

Hypothesis.Separation (restricted comprehension) is available, to form \( B = \{ a \in A : a \notin f(a) \} \). In set theories where comprehension is restricted differently the proof can break: in Quine's NF the diagonal formula \( a \notin f(a) \) is not stratified for the relevant maps, the theorem fails in its naive form, and indeed NF proves a universal set \( V \) exists with \( \mathcal{P}(V) \subseteq V \).

Hypothesis.Power Set axiom holds, so that \( \mathcal{P}(A) \) is a set at all. In ZF minus Power Set (a theory in which, e.g., the hereditarily countable sets form a model), \( \mathcal{P}(\mathbb{N}) \) need not exist as a set, and the statement \( |A| \lt |\mathcal{P}(A)| \) cannot even be formulated for such \( A \). The surjection form — no \( f : A \to \mathcal{P}(A) \) is onto — survives as a schema about class functions, which is why the surjection form is the more robust statement.

Proof

We prove two things: (i) an injection \( A \to \mathcal{P}(A) \) exists, giving \( |A| \le |\mathcal{P}(A)| \); (ii) no surjection \( A \to \mathcal{P}(A) \) exists, which rules out any bijection and upgrades \( \le \) to \( \lt \).

\[ s : A \to \mathcal{P}(A), \qquad s(a) = \{a\} \]

The singleton map is well defined: \( \{a\} \subseteq A \) for each \( a \in A \) (Pairing gives \( \{a\} \) as a set; it is a subset of \( A \) by definition), so \( \{a\} \in \mathcal{P}(A) \). A

\( s \) is injective, hence \( |A| \le |\mathcal{P}(A)| \).

If \( s(a) = s(a') \) then \( \{a\} = \{a'\} \), and by Extensionality \( a \in \{a'\} \), i.e. \( a = a' \). The inequality \( |A| \le |\mathcal{P}(A)| \) is then exactly the definition of cardinal comparison by injections. A

Let \( f : A \to \mathcal{P}(A) \) be an arbitrary function. Define \[ B = \{ a \in A : a \notin f(a) \}. \]

Key idea — the diagonal set. \( B \) is a set by the Separation axiom applied to the formula \( \varphi(a) \equiv a \notin f(a) \) with parameter \( f \), carving \( B \) out of the existing set \( A \). Note \( B \subseteq A \), so \( B \in \mathcal{P}(A) \). B

Claim: \( B \notin \operatorname{ran}(f) \). Suppose for contradiction \( B = f(b) \) for some \( b \in A \).

Proof by contradiction; \( b \) is a fixed witness from the assumed membership of \( B \) in the range. Everything now hinges on asking whether \( b \in B \). B

\[ b \in B \iff b \notin f(b) \iff b \notin B \]

The first equivalence is the defining property of \( B \) (Separation guarantees \( a \in B \leftrightarrow (a \in A \wedge a \notin f(a)) \), and \( b \in A \) holds). The second substitutes \( f(b) = B \), legal by Extensionality: equal sets have the same members. The biconditional \( b \in B \leftrightarrow b \notin B \) is a propositional contradiction \( p \leftrightarrow \neg p \). C

Hence no \( b \in A \) has \( f(b) = B \); \( f \) is not surjective.

Steps 4–5 refuted the assumption \( B \in \operatorname{ran}(f) \). Since \( f \) was arbitrary, no function \( A \to \mathcal{P}(A) \) is surjective. (The argument is uniform in \( f \): given \( f \), it exhibits a concrete missed subset.) A

\[ |A| \lt |\mathcal{P}(A)| \]

A bijection is in particular a surjection, so by Step 6 no bijection \( A \to \mathcal{P}(A) \) exists; combined with the injection from Step 2 this is precisely the definition of strict cardinal inequality. No use of the Axiom of Choice was made anywhere. A

Result

\[ \forall A \ \text{(set)}: \quad |A| \lt |\mathcal{P}(A)|, \quad \text{i.e. no } f : A \to \mathcal{P}(A) \text{ is surjective.} \]

Reading. However you try to label the subsets of \( A \) by elements of \( A \), some subset is always missed — the set of labels that don't belong to the subset they label is itself unlabeled. Collections of things always outnumber the things.

Scope. Every set in ZF: empty (\( 0 \lt 1 \)), finite (\( n \lt 2^n \)), countable, and every infinite cardinality; the proof is Choice-free and intuitionistically valid (the surjection form needs no excluded middle). It does not apply to proper classes, and it can fail in set theories without full Separation (e.g. NF) or be unformulable without Power Set.

Corollaries & converses

Endless tower of infinities. \( |\mathbb{N}| \lt |\mathcal{P}(\mathbb{N})| \lt |\mathcal{P}(\mathcal{P}(\mathbb{N}))| \lt \cdots \): there are infinitely many distinct infinite cardinalities, and no largest cardinal.
Uncountability of \( \mathbb{R} \). \( |\mathcal{P}(\mathbb{N})| = |\{0,1\}^{\mathbb{N}}| \le |\mathbb{R}| \) (binary expansions / Cantor set), so \( \mathbb{R} \) is uncountable — Cantor's 1874 result recovered from the 1891 diagonal.
Cantor's paradox. There is no set of all sets: if \( V \) were a set then \( \mathcal{P}(V) \subseteq V \) would give \( |\mathcal{P}(V)| \le |V| \), contradicting the theorem. Hence "the universe" is a proper class.
No injection the other way. There is no injection \( \mathcal{P}(A) \to A \) either (Problem 3): an injection backwards would manufacture a surjection forwards, without Choice.
Converse fails. The converse would say every strict cardinal gap "is" a power-set gap: false. \( |\mathbb{N}| \lt |\mathbb{N} \cup \{\text{one new point}\}| \) is not even strict (they are equinumerous), and more seriously, whether any cardinal lies strictly between \( |\mathbb{N}| \) and \( |\mathcal{P}(\mathbb{N})| \) is the Continuum Hypothesis, independent of ZFC (Gödel 1940, Cohen 1963) — so the pattern of gaps between \( |A| \) and \( |\mathcal{P}(A)| \) is not decided by the theorem.
Generalization (Lawvere). If a surjection \( A \to B^{A} \) exists, then every map \( B \to B \) has a fixed point; Cantor is the case \( B = \{0,1\} \) with the fixed-point-free swap. See Discussion.

Fails without

Drop "\( A \) is a set" (allow the universal class). In NF (New Foundations), a universal set \( V \) genuinely exists and \( \mathcal{P}(V) \subseteq V \), so \( |\mathcal{P}(V)| \le |V| \): the naive statement of Cantor's theorem is false there. The diagonal proof is blocked because \( \{ a : a \notin f(a) \} \) is not a stratified definition, so NF's comprehension scheme refuses to build \( B \). In ZF the same pressure is resolved the other way: \( V \) is banished to proper-class status.
Replace \( \mathcal{P}(A) \) by a restricted family of subsets. The finite subsets of \( \mathbb{N} \) form a countable set: \( X \mapsto \sum_{n \in X} 2^n \) is a bijection \( [\mathbb{N}]^{\lt\omega} \to \mathbb{N} \). Likewise the computable subsets of \( \mathbb{N} \) are countable. The theorem needs every subset — including the diagonal set \( B \), which is defined from \( f \) and may be wildly non-constructive relative to any given listing.
Drop Separation. Without the ability to form \( B = \{ a \in A : a \notin f(a) \} \) the proof does not start; this is not a mere formality, since (as the NF example shows) consistent set theories exist in which exactly this instance of comprehension is unavailable and the conclusion fails.

Common errors

Proving only half the strict inequality. Showing "no bijection" gives \( |A| \ne |\mathcal{P}(A)| \); without the singleton injection (Step 1–2) you have not shown \( |A| \lt |\mathcal{P}(A)| \) under the definition of \( \lt \). Both halves are required.
Assuming \( f \) is a bijection at the outset. The proof must take an arbitrary function \( f \) and show it is not surjective. Starting from "suppose \( f \) is a bijection" proves the weaker statement "no bijection", and hides the stronger, more useful surjection form.
Worrying that \( B \) might be empty or all of \( A \). Students often feel the argument is fishy when \( B = \emptyset \) (e.g. if every \( a \in f(a) \)). But \( \emptyset \in \mathcal{P}(A) \) is a perfectly good element for \( f \) to miss; the contradiction in Step 5 never uses nonemptiness of \( B \).
Applying the theorem to a proper class. "Let \( A \) be the set of all sets, then \( |A| \lt |\mathcal{P}(A)| \), contradiction, so mathematics is inconsistent" — the correct conclusion is that no such set exists; the theorem's hypothesis does the work.
Believing Choice is needed. The proof is entirely Choice-free; even converting "no injection \( \mathcal{P}(A) \to A \)" out of the theorem needs no Choice (Problem 3). Cardinal comparability of arbitrary sets needs Choice; Cantor's theorem does not.
Confusing \( \mathcal{P}(A) \) with \( 2^{|A|} \) arithmetic for finite sets only. The identity \( |\mathcal{P}(A)| = |\{0,1\}^{A}| \) via characteristic functions holds for all sets, and the theorem is about all sets — it is not "just \( n \lt 2^n \) extended by analogy".

Discussion

Cantor published the diagonal argument in 1891 (Über eine elementare Frage der Mannigfaltigkeitslehre), seventeen years after his first, topological proof that \( \mathbb{R} \) is uncountable. The 1891 paper is a landmark of compression: two pages, no analysis, no completeness of \( \mathbb{R} \) — pure logic and the power set. Russell discovered his paradox in 1901 while dissecting exactly this proof: apply the diagonal construction to the "set" of all sets with \( f = \) identity-like assignments and \( B \) becomes \( \{ x : x \notin x \} \). Russell's paradox is Cantor's diagonal with the safety guard (a bounding set \( A \)) removed — which is why ZF's Separation axiom, which insists every comprehension be bounded by an existing set, dissolves the paradox while preserving the theorem.

The theorem is best remembered in its surjection form: no map \( A \to \mathcal{P}(A) \) hits everything. That form transfers by pure translation to computability — no program enumerates all sets of naturals, and the halting set is a diagonal \( B \) for the listing of computable functions — and to logic, where Gödel's incompleteness and Tarski's undefinability theorems diagonalize against "definable" playing the role of "listed". The recurring pattern: any system that tries to internalize a complete catalogue of its own subsets/predicates/functions can be defeated by the object that disagrees with the \( a \)-th catalogue entry about \( a \).

Lawvere (1969) isolated the algebra of the argument: in any cartesian closed category, if \( \varphi : A \to B^{A} \) is surjective on points (weakly point-surjective suffices), then every endomorphism \( \sigma : B \to B \) has a fixed point. Proof in one line: the map \( a \mapsto \sigma(\varphi(a)(a)) \) equals \( \varphi(a_0) \) for some \( a_0 \), and evaluating at \( a_0 \) gives \( \varphi(a_0)(a_0) = \sigma(\varphi(a_0)(a_0)) \). Cantor's theorem is the contrapositive with \( B = \{0,1\} \) and \( \sigma \) the swap \( 0 \leftrightarrow 1 \), which has no fixed point; the same contrapositive with other choices of \( B, \sigma \) yields Russell, Gödel's diagonal lemma, Tarski, and the recursion-theoretic fixed-point theorems as one family. Note also that the surjection form of Cantor is intuitionistically valid, and the diagonal set \( B \) can be replaced by subtler diagonals to get constructive refinements.

Common misconceptions. The theorem does not say \( \mathcal{P}(A) \) is "the next size up": whether anything sits strictly between \( |A| \) and \( |\mathcal{P}(A)| \) is (for \( A = \mathbb{N} \)) the Continuum Hypothesis, independent of ZFC. It also does not say infinities are "unknowable" — it gives a precise, positive comparison. And the diagonal argument is not "a trick about decimal expansions"; expansions are one concrete costume for the abstract set-theoretic argument above, and the costume introduces irrelevant complications (non-unique expansions) that the pure version avoids.

Worked examples

Example 1. The set \( \{0,1\}^{\mathbb{N}} \) of infinite binary sequences is uncountable.

Define \( \chi : \mathcal{P}(\mathbb{N}) \to \{0,1\}^{\mathbb{N}} \) by \( \chi(X) = (\mathbf{1}_{X}(0), \mathbf{1}_{X}(1), \dots) \), where \( \mathbf{1}_X(n) = 1 \) if \( n \in X \), else \( 0 \).

The characteristic-function map; well defined for every subset \( X \subseteq \mathbb{N} \). A

\( \chi \) is a bijection, so \( |\mathcal{P}(\mathbb{N})| = |\{0,1\}^{\mathbb{N}}| \).

Injective: \( \chi(X) = \chi(Y) \) forces \( \mathbf{1}_X = \mathbf{1}_Y \), hence \( X = Y \) by Extensionality. Surjective: a sequence \( (b_n) \) is hit by \( X = \{ n : b_n = 1 \} \), a set by Separation. A

Suppose \( \{0,1\}^{\mathbb{N}} \) were countable: then there is a surjection \( g : \mathbb{N} \to \{0,1\}^{\mathbb{N}} \).

Definition of countable: a set is countable iff it is empty or admits a surjection from \( \mathbb{N} \); \( \{0,1\}^{\mathbb{N}} \) is nonempty (it contains the constant sequences), so countability would supply such a \( g \). A

Then \( \chi^{-1} \circ g : \mathbb{N} \to \mathcal{P}(\mathbb{N}) \) is a surjection.

Composition of a surjection with a bijection is a surjection — direct from the definitions. B

Contradiction with Cantor's theorem applied to \( A = \mathbb{N} \).

The theorem says no surjection \( \mathbb{N} \to \mathcal{P}(\mathbb{N}) \) exists. (Unwinding the diagonal here literally produces the classic "flip the \( n \)-th bit of the \( n \)-th sequence" sequence.) B

\[ \{0,1\}^{\mathbb{N}} \ \text{is uncountable; hence } \mathbb{R} \supseteq \text{(Cantor set)} \text{ is uncountable too.} \]

Reading. Binary sequences cannot be listed; the diagonal flip defeats every proposed list.

Scope. The same argument gives \( |B^{A}| \gt |A| \) whenever \( |B| \ge 2 \) (Problem 5).

Example 2. Cantor's paradox: there is no set of all sets.

Suppose \( V \) is a set with \( \forall x \, (x \in V) \), i.e. every set belongs to \( V \).

Assumption for contradiction; \( V \) is the hypothetical universal set. A

\[ \mathcal{P}(V) \subseteq V \]

Every element of \( \mathcal{P}(V) \) is a set (Power Set gives sets as elements), and by Step 1 every set is in \( V \). B

The inclusion map \( \iota : \mathcal{P}(V) \to V,\ \iota(X) = X, \) is injective, so \( |\mathcal{P}(V)| \le |V| \).

Inclusions are injective trivially; cardinal comparison is by definition via injections. A

From an injection \( \iota : \mathcal{P}(V) \to V \), build a surjection \( h : V \to \mathcal{P}(V) \): set \( h(v) = X \) if \( v = \iota(X) \) for the (unique) such \( X \), and \( h(v) = \emptyset \) otherwise.

Well defined because \( \iota \) is injective (uniqueness of \( X \)); surjective because every \( X \in \mathcal{P}(V) \) is \( h(\iota(X)) \). No Choice used — the inverse is taken only on the range, where it is single-valued. C

Contradiction: Cantor's theorem forbids any surjection \( V \to \mathcal{P}(V) \).

Apply the theorem with \( A = V \) (legitimate under the assumption that \( V \) is a set). Hence the assumption fails. B

\[ \text{No set contains all sets: the universe } V \text{ is a proper class.} \]

Reading. A universal set would have to be at least as big as its own power set, which Cantor forbids.

Scope. A theorem of ZF; in NF the argument is blocked at the diagonal (comprehension), and a universal set exists there.

Problems

Let \( A = \{1, 2\} \) and let \( f : A \to \mathcal{P}(A) \) be defined by \( f(1) = \{1,2\} \), \( f(2) = \emptyset \). Compute the diagonal set \( B = \{ a \in A : a \notin f(a) \} \) and verify directly that \( B \notin \operatorname{ran}(f) \). Then count how many functions \( A \to \mathcal{P}(A) \) exist and how many would be needed for a surjection.
Solution
Check each element: \( 1 \in f(1) = \{1,2\} \), so \( 1 \notin B \); \( 2 \notin f(2) = \emptyset \), so \( 2 \in B \). Hence \( B = \{2\} \). The range of \( f \) is \( \{ \{1,2\}, \emptyset \} \), which indeed does not contain \( \{2\} \). Counting: \( |\mathcal{P}(A)| = 4 \), so there are \( 4^2 = 16 \) functions \( A \to \mathcal{P}(A) \); a surjection onto a 4-element set from a 2-element set is impossible since \( |\operatorname{ran}(f)| \le 2 \lt 4 \). This confirms the theorem in the finite case \( 2 \lt 2^2 \), and illustrates that the diagonal recipe finds a concrete missed subset for each specific \( f \).
Show that only countably many subsets of \( \mathbb{N} \) are computable (decidable by some Turing machine / program), and deduce from Cantor's theorem that non-computable subsets of \( \mathbb{N} \) exist — indeed, uncountably many.
Solution
Every program is a finite string over a finite alphabet \( \Sigma \). The set \( \Sigma^{*} \) of finite strings is countable: list strings by length and, within each length, lexicographically (\( |\Sigma^{n}| = |\Sigma|^{n} \) is finite for each \( n \), and a countable union of finite sets, here indexed explicitly by length, is countable — no Choice needed since the enumerations are canonical). The map sending each program to the subset it decides is a surjection from a subset of \( \Sigma^{*} \) onto the family \( \mathcal{C} \) of computable sets, so \( \mathcal{C} \) is countable. By Example 1, \( \mathcal{P}(\mathbb{N}) \) is uncountable. If every subset were computable, \( \mathcal{P}(\mathbb{N}) = \mathcal{C} \) would be countable — contradiction. Moreover \( \mathcal{P}(\mathbb{N}) \setminus \mathcal{C} \) is uncountable: if it were countable, then \( \mathcal{P}(\mathbb{N}) = \mathcal{C} \cup (\mathcal{P}(\mathbb{N}) \setminus \mathcal{C}) \) would be a union of two countable sets, hence countable (interleave the two explicit enumerations), contradiction.
Prove, without using the Axiom of Choice, that there is no injection \( g : \mathcal{P}(A) \to A \) for any set \( A \).
Solution
Suppose \( g : \mathcal{P}(A) \to A \) is injective. Define \( f : A \to \mathcal{P}(A) \) by: \( f(a) = X \) if \( a = g(X) \) for some (necessarily unique, by injectivity of \( g \)) \( X \in \mathcal{P}(A) \), and \( f(a) = \emptyset \) if \( a \notin \operatorname{ran}(g) \). This is well defined without Choice: on \( \operatorname{ran}(g) \) the preimage is a single set, picked out by the formula \( a = g(X) \), and Replacement/Separation suffice to realize \( f \) as a set of pairs. Then \( f \) is surjective: for any \( X \in \mathcal{P}(A) \), \( f(g(X)) = X \). This contradicts Cantor's theorem (no surjection \( A \to \mathcal{P}(A) \)). Hence no injection \( \mathcal{P}(A) \to A \) exists. Remark: this is exactly the maneuver used in Worked Example 2, Step 4; it shows the theorem also yields \( |\mathcal{P}(A)| \not\le |A| \), which together with \( |A| \le |\mathcal{P}(A)| \) gives the strict inequality even under the injection-based ordering without appealing to Cantor–Schröder–Bernstein.
(Fixed-point form.) Let \( A \) be a set and suppose \( \varphi : A \to \{0,1\}^{A} \) is any function. Construct explicitly a function \( d \in \{0,1\}^{A} \) not in the range of \( \varphi \), and explain where the fixed-point-free map \( \sigma : \{0,1\} \to \{0,1\} \), \( \sigma(x) = 1 - x \), enters.
Solution
Define \( d : A \to \{0,1\} \) by \( d(a) = \sigma\big(\varphi(a)(a)\big) = 1 - \varphi(a)(a) \). Suppose \( d = \varphi(a_0) \) for some \( a_0 \in A \). Evaluate both sides at \( a_0 \): \( \varphi(a_0)(a_0) = d(a_0) = 1 - \varphi(a_0)(a_0) \), so \( 2\,\varphi(a_0)(a_0) = 1 \), impossible for a value in \( \{0,1\} \). Hence \( d \notin \operatorname{ran}(\varphi) \). The role of \( \sigma \): the contradiction is exactly the statement that \( \varphi(a_0)(a_0) \) would be a fixed point of \( \sigma \), but \( \sigma(x) = 1 - x \) has none on \( \{0,1\} \). This is Lawvere's formulation: a surjection \( A \to B^{A} \) would force every \( \sigma : B \to B \) to have a fixed point. Translating via characteristic functions, \( d \) corresponds to the diagonal set \( B = \{ a : a \notin f(a) \} \) of the main proof, with \( \sigma \) implementing "flip membership".
Let \( B \) be a set with \( |B| \ge 2 \). Prove that there is no surjection \( A \to B^{A} \) for any set \( A \). Then explain precisely why the hypothesis \( |B| \ge 2 \) is necessary, exhibiting the failure for \( |B| = 1 \) and \( |B| = 0 \) (careful: the case \( A = \emptyset \), \( B = \emptyset \) needs separate thought).
Solution
Since \( |B| \ge 2 \), fix distinct \( b_0, b_1 \in B \) and define \( \sigma : B \to B \) by \( \sigma(b_0) = b_1 \) and \( \sigma(x) = b_0 \) for all \( x \ne b_0 \); then \( \sigma \) has no fixed point (\( \sigma(b_0) = b_1 \ne b_0 \); for \( x \ne b_0 \), \( \sigma(x) = b_0 \ne x \)). Now suppose \( \varphi : A \to B^{A} \) is surjective. Define \( d(a) = \sigma\big(\varphi(a)(a)\big) \); this is an element of \( B^{A} \), so \( d = \varphi(a_0) \) for some \( a_0 \). Evaluating at \( a_0 \): \( \varphi(a_0)(a_0) = \sigma\big(\varphi(a_0)(a_0)\big) \), a fixed point of \( \sigma \) — contradiction. (Only two specific elements were chosen, so no Choice is used.) Necessity of \( |B| \ge 2 \): the statement genuinely fails exactly when \( |B| = 1 \) and \( A \ne \emptyset \). Indeed, if \( B = \{b\} \) is a singleton then \( B^{A} \) is a singleton (its only element is the constant function \( a \mapsto b \)), and for nonempty \( A \) the map \( \varphi \) sending every \( a \in A \) to that constant function is a surjection \( A \to B^{A} \). The remaining small cases do not produce failures, only vacuous truths: (i) \( |B| = 1 \), \( A = \emptyset \): here \( B^{\emptyset} = \{\emptyset\} \) (the empty function) is nonempty, and no function from \( \emptyset \) has nonempty range, so no surjection exists and the conclusion holds. (ii) \( B = \emptyset \), \( A = \emptyset \): again \( B^{A} = \{\emptyset\} \) is nonempty and there is no surjection \( \emptyset \to \{\emptyset\} \). (iii) \( B = \emptyset \), \( A \ne \emptyset \): now \( B^{A} = \emptyset \), and no function \( A \to \emptyset \) exists at all when \( A \ne \emptyset \), so in particular no surjection — the conclusion holds vacuously. This case analysis matches Lawvere's dichotomy precisely: \( |B| = 1 \) is exactly the case in which every map \( \sigma : B \to B \) has a fixed point, so the fixed-point obstruction evaporates and a surjection becomes possible.