Motivation
Counting a finite set assigns it a natural number. For infinite sets, a more robust starting point is comparison by maps: two sets have the same size when their elements can be paired bijectively. A proper subset can have the same size as its containing set, so finite rules about size must be re-examined rather than assumed.
The axioms also matter. Constructing a displayed enumeration is different from asserting that every member of a family admits some enumeration and then selecting one for each. The latter may need a choice principle. This chapter proves its main comparison results in ZF and identifies where extra choices would enter common countability arguments.
Definitions
Definition 2.1.1
(Comparison of size and countability)
Write if there is a bijection , and if there is an injection . Write if but . These are statements about sets; the notation can be read as their size under this comparison without assuming that every set has a least equinumerous ordinal.
A set is at most countable if it injects into , and countably infinite if it is bijective with . A nonempty at most countable set is the range of a sequence: given an injection into , use its inverse on the image, and fill unused indices with one fixed element. Conversely, from a surjection , assign each element the least index where it occurs to obtain an injection into . Repetitions in an enumeration are harmless.
For well-orderable sets, the least equinumerous ordinal is an initial ordinal, also called a cardinal. Thus is the first infinite cardinal, written . Without choice, not every set need be well-orderable, so the initial-ordinal convention must not be silently imposed on arbitrary sets.
Proposition 2.1.2
(Basic laws of comparison)
For all sets :
- is reflexive, symmetric and transitive, and is reflexive and transitive.
- If , then . If and , then exactly when .
- If and , there is a surjection .
- If and , then .
Proof
(Compose, restrict and fill in with one fixed point)
Identity maps give reflexivity. The inverse of a bijection is a bijection, and composites of injections, or of bijections, are again injections, or bijections. This proves part 1. For part 2, the inclusion map is injective. If and are bijections and is injective, then is injective; the converse direction is symmetric.
For part 3, fix an injection and one element . Fixing one element of one nonempty set is a single existential instantiation, not a use of choice. Define by letting be the unique with when , and otherwise. Its graph is separated from , and , so is onto.
For part 4, transitivity gives . If we had , then together with would give by the Cantor–Schröder–Bernstein theorem below, contrary to .
The converse of part 3 can fail without choice; see the common mistake on reversing a surjection. Two further cautions apply. First, is antisymmetric up to only because of the Cantor–Schröder–Bernstein theorem, which needs a proof. Second, ZF does not prove that any two sets are comparable. In fact, the statement that or for all sets is equivalent to the axiom of choice; this is proved in the choice chapter by comparing a set with its Hartogs ordinal.
Theorem/proposition
Theorem 2.1.3
(Cantor–Schröder–Bernstein theorem)
If and are injections, then . No axiom of choice is required.
Theorem 2.1.4
(Cantor's theorem)
For every set , there is no surjection . Hence .
Concept lensCombinatorial
Cantor’s diagonal as a table
Under the bijection of the second exercise, a map is a table with a row for each , a column for each , and entry . The indicator of the diagonal set is obtained by reading the diagonal entries and flipping each one. This new row differs from row in column , so it is no row of the table. For it is the familiar picture of a list of binary sequences.
Theorem 2.1.5
(Explicitly enumerated unions)
Suppose is nonempty and functions are supplied simultaneously for all , each surjective. Then is at most countable. In ZF, the weaker assumption “each is at most countable” does not by itself supply the sequence of enumerations used in this proof.
Proof sketch or proof idea
Proof
(Partition by chains from )
Put and recursively . Let . Define
The second branch is defined because and the injection has a unique inverse value on its range. Each branch is injective. Their images cannot overlap: if with , applying gives , contrary to its branch. To prove surjectivity, take . If , its second-branch image is . If , it cannot lie in , so it lies in some . Injectivity of gives for some , so the first branch reaches it. Thus is bijective.
Proof X-ray
Where the chains start and why the inverse branch is defined
The set collects every point reached from by repeatedly applying . Three properties of carry the proof. First, , so every point outside lies in and the branch is defined there. Second, is closed under ; this is exactly what keeps the two branches from colliding, since a collision would put a point outside into . Third, every point of has the form with , which is what surjectivity needs.
Only injectivity of and , ordinary recursion on and separation are used. Each is uniquely determined, so no choice is made. In the edge case where is already onto, , and .
Proof
(The diagonal set)
Given a putative surjection , separation forms
Surjectivity would give for some , yielding . Therefore no such exists. The map is injective, and a bijection would in particular be a forbidden surjection. The proof includes .
Proof
(Pairing the enumerations)
The map surjects from onto the union. The pairing function
is a bijection to : each diagonal receives a consecutive block of integers. Compose its inverse with the displayed surjection, and take least occurrence indices. If empty are allowed, enumerate the nonempty-index subset in its natural order; if there are none the union is empty. The essential hypothesis is the available family of enumerations, not nonemptiness.
Worked examples
Worked example 2.1.6
(The rationals can be listed)
Each rational has a unique reduced expression with and positive integer . The map explicitly enumerates . Pairing enumerates all integer-positive-integer pairs; map each pair to . The list repeats rationals, which is acceptable. Since injects into , the Cantor–Schröder–Bernstein theorem or the least-occurrence construction proves .
Worked example 2.1.7
(Finite strings are countable)
Over the alphabet , list strings first by length and then lexicographically. There are strings of length , so each appears at a finite place. Every program written using a fixed finite alphabet is one such finite string; the set of syntactically valid programs is at most countable. This is an explicit enumeration, without making a separate choice at each length. Infinite binary sequences are a different set: they correspond to subsets of and cannot be listed by Cantor's theorem.
Worked example 2.1.8
(The real numbers have the size of a power set)
An injection sends to its rational lower cut . Distinct reals have different cuts by density of . A fixed enumeration of identifies its power set with . In the other direction, send to
If first differ at , their leading difference has magnitude , while all later differences total at most . Thus . The Cantor–Schröder–Bernstein theorem gives . This avoids ambiguous decimal expansions rather than ignoring their nonuniqueness.
Worked example 2.1.9
(Intervals have the size of the line)
The map is a bijection . On it is increasing from toward , on it is increasing from toward , and its inverse is : indeed , so . Every open interval with is bijective with by an affine map. Hence every nonempty open interval has the size of .
Closed intervals need one more step, because no continuous bijection exists. A shift along a specified sequence suffices. Define by
Listing , and for , the map sends each to , so the sequence is shifted two places along onto , and every other point is fixed. So is a bijection. This is the same device as the shift in the Dedekind-infinite example below, applied to an explicit sequence. Alternatively, the inclusion and the injection from into give the same conclusion by the Cantor–Schröder–Bernstein theorem, though without displaying the bijection.
Worked example 2.1.10
(Planes, sequences and integer sequences of continuum size)
Write for the pairing bijection of the proof above. Three bijections then follow.
- . Send a sequence of subsets of to . The inverse sends to the sequence whose -th term is . Both directions are given by formulas, so no choice is involved.
- . Send to ; evens and odds separate the two coordinates again.
- . The map injects into . In the other direction, is injective, because is a bijection and a function is determined by its graph. The Cantor–Schröder–Bernstein theorem finishes the argument.
Now fix one bijection , which exists by the example on the real numbers above. Applying coordinatewise transfers the first two bijections, so and . A plane, and even the set of all real sequences, has no more points than a line. This uses one fixed bijection, not a separate choice for each coordinate. The comparison concerns size only. A bijection cannot be continuous, since its restriction to a circle would be a continuous injection of a circle into , which the intermediate value theorem rules out. Topology distinguishes the two sets even though cardinality does not.
Worked example 2.1.11
(Algebraic and transcendental numbers)
Integer polynomials are countable, because they are finite lists of integers and can be explicitly enumerated by length and coefficient bounds. Every nonzero polynomial has finitely many complex roots. Those roots can be listed canonically by increasing real part and, on ties, increasing imaginary part; no arbitrary root choices are required. Thus algebraic complex numbers are at most countable. Since the real numbers are uncountable, some real numbers are transcendental. The argument proves existence; it does not identify a particular transcendental constant.
Worked example 2.1.12
(Countably infinite grids and finite records)
The pairing function proves . Iterating that explicit formula gives an enumeration of for every fixed positive finite . Finite tuples of varying length can also be listed without choice: assign a tuple a weight equal to its length plus the sum of its entries, list weights in increasing order, and within a weight list the finitely many possible tuples lexicographically. Each weight class is finite because both the length and each entry are bounded by the weight. Include the empty tuple at weight zero. Every finite tuple appears, and the procedure effectively produces the list.
Consequently a finite record consisting of finitely many integer labels, natural-number addresses and a finite control symbol has only countably many possibilities, provided each component encoding is fixed in advance. This is the reason finite proofs, programs and finite mathematical expressions can be encoded by natural numbers. It does not mean that infinite records or arbitrary real parameters can be encoded the same way. Replacing a finite list of rational coefficients by an arbitrary sequence of binary digits changes the cardinality of the available data.
Worked example 2.1.13
(Dedekind infinitude isolates a hidden assumption)
A set is Dedekind infinite if it is bijective with a proper subset of itself. In ZF this is equivalent to containing a countably infinite subset. Here is a proof that makes the equivalence concrete. If are distinct members of , shift to and fix every other point. This defines a bijection from onto .
Conversely, suppose is injective and misses some . Define by ordinary recursion. The values are distinct: if with , repeatedly cancel the injective to obtain , placing in the range of , contrary to its choice. Thus the sequence is a countably infinite subset. No simultaneous arbitrary selections are being made: one point is fixed and all later points are uniquely determined by iteration.
Every finite set fails this property by the finite pigeonhole principle. Under AC every infinite set has it: well-order the set and recursively take the least remaining element; if this process stopped after finitely many steps the set would be finite. In ZF alone, “infinite” means not bijective with a finite ordinal, and must not be silently replaced by “contains a countably infinite subset”. The equivalence just proved tells exactly what extra property the familiar Hilbert-hotel shift uses. The distinction is about available choices, not an error in that shift once a sequence is supplied. The example also shows that an explicit combinatorial construction may use no choice, while asserting uniformly for all infinite sets that its input is available can require a stronger axiom.
Counterexample mode
Equal size does not preserve the given order
A plausible but false inference is that two equinumerous ordered sets must have the same order type. The bijection sending the last point to and each finite to refutes it: one order has a greatest element and the other does not. Every order-isomorphism preserves the property of being greatest, so no bijection can be an order-isomorphism in this case.
Repair the inference by specifying what the map must preserve. For cardinality, the conditions are injectivity and surjectivity, with no order requirement. For ordinal comparison, the map must preserve the predecessor relation. A single underlying set may carry many different orders of the same cardinality, and the same countable cardinal supports both orders in this example. This distinction also explains why a pairing function can rearrange an infinite grid into a sequence without preserving its geometric placement or any lexicographic order initially assigned to it. The proof of countability claims only that every point occurs exactly once in the resulting enumeration.
So whenever a statement says “the same”, “encodable” or “isomorphic”, ask which structure is preserved. Encoding strings as natural numbers is only an effective correspondence between sets; it does not turn the prefix relation on strings into the usual order of the natural numbers. Forgetting the preservation conditions can turn a correct countability proof into a false conclusion about order type.
Common mistakes
Common mistake
(One injection is not a bijection)
An injection in one direction does not prove a bijection: injects into , but the reverse comparison is impossible.
Common mistake
(Reversing a surjection can need choice)
A surjection does not automatically come with an injection in ZF; choosing one point in each fiber can require choice. Least-occurrence selection works for precisely because it has a specified well-order.
Common mistake
(A diagonal argument needs a specified list)
A diagonal proof must identify the proposed list and construct an object absent from that list. Saying “infinity is too large” supplies no contradiction.
Ordinal expressions such as describe order; they can have cardinality without equalling .
Summary
Mutual injections imply a bijection by a concrete partition argument. Power sets strictly increase size by diagonalization. Countability proofs succeed when enumerations are explicit; arbitrary simultaneous selection is a separate issue, studied in the choice chapter.
Exercises
Quick check
(Give an explicit enumeration of all finite subsets of , and explain why the set of all subsets is larger.)
Solution · Answer
Send a finite subset to . Uniqueness of binary expansion makes this a bijection from finite subsets to , including the empty set mapped to zero. All subsets form , which is uncountable by Cantor. Finite and arbitrary subsets must not be conflated.
Quick check
(Prove that , where the latter denotes all functions .)
Solution · Answer
Send to , with value exactly on . Its inverse sends a function to . The two compositions are identities, giving a bijection without choices.
Quick check
(If injects into , prove that injects into . Does Cantor's theorem imply that always gives ?)
Solution · Answer
If is injective, send to . Equality of images implies equality of subsets by injectivity. Strictness does not follow from Cantor: Cantor compares a set with its own power set. The proof gives no strict comparison between the power sets of two different infinite sets; such a comparison needs a separate argument or additional hypotheses.
Quick check
(Prove that every infinite subset of is countably infinite, with no appeal to choice.)
Solution · Answer
Let be the least element of and the least element of . The latter set is nonempty because is infinite. The sequence is strictly increasing. If were missed, all terms before passing would be distinct elements of the finite set , which is impossible indefinitely; the least-remaining rule also prevents passing without taking it. Thus the sequence is bijective onto . Every step is uniquely specified.
Quick check
(Give a second proof of the Cantor–Schröder–Bernstein theorem through a fixed point. For injections and , let for . Show that has a fixed point and that yields a bijection.)
Solution · Answer
If , then , so and . Let , which contains , and put . For every we have , so ; hence . Monotonicity then gives , so and . Thus . This is the Knaster–Tarski fixed-point argument for monotone maps on .
The fixed-point equation says . Let on and on . The first branch maps bijectively onto , and the second maps bijectively onto , because is injective. These two images partition , so is a bijection. Since is injective, , and the least such fixed point is exactly the set of the chain proof. The two proofs build the same bijection.
Quick check
(Use Cantor's theorem and the basic laws of comparison to give a second proof that there is no set of all sets.)
Solution · Answer
Suppose were a set containing every set. Every subset of is a set, so , and hence . Since is nonempty (it contains ), part 3 of the basic laws gives a surjection . Cantor's theorem forbids this. In fact every set is a subset of , so the surjection built from the inclusion is the identity map, and its diagonal set is exactly Russell's set .
Quick check
(Prove that the set of continuous functions satisfies , although the set of all functions is strictly larger than .)
Solution · Answer
Constant functions give . For the other direction, send to its restriction . This is injective: given , the rationals form a specified sequence converging to , so continuity gives , and two continuous functions that agree on agree everywhere. A fixed enumeration of identifies with , and by the worked example on sequences. Hence , and the Cantor–Schröder–Bernstein theorem gives . All functions include all functions , a set equinumerous with , which is strictly larger than by Cantor's theorem and part 4 of the basic laws.
Quick check
(Prove that the set of all bijections is equinumerous with .)
Solution · Answer
Bijections form a subset of , which is equinumerous with by the worked example, so they inject into . Conversely, for let exchange and for every and fix all other numbers. Each is its own inverse, hence a bijection. If , then while , so is injective. The Cantor–Schröder–Bernstein theorem completes the proof. In particular a countable set has uncountably many permutations.