Read injections, initial ordinals, choice and cofinality first. We distinguish the square theorem provable for well-orderable sets in ZF from its application to arbitrary infinite sets using choice. Subsequent unrestricted cardinal comparisons are made in ZFC.
Motivation
A pairing function shows that two natural-number coordinates carry only countably many possibilities. The corresponding statement for every infinite cardinal is less obvious: a naive row-by-row order of an uncountable square can have enormous initial segments. The right order processes pairs according to their largest coordinate, so every earlier segment is controlled by a smaller square.
Addition and multiplication then simplify dramatically, but exponentiation does not collapse in the same way. Cantor's diagonal already gives . König's diagonal examines a different obstruction: a product has room to evade a proposed list even when the list is split into many parts, provided the corresponding coordinate is larger than its part. This will explain why the continuum cannot have countable cofinality, without identifying its cardinal value.
Definitions
Definition 2.4.1
(Cardinal sums, products and powers)
For sets , cardinal addition is the size of the tagged disjoint union, multiplication the size of the Cartesian product, and exponentiation the size of the function set:
Bijections show independence from the chosen representatives. For a family, means the size of , while means the size of its choice-function set. Under choice, every set has an initial ordinal as its cardinal, so these expressions are comparable cardinals. Without choice, arbitrary sets need not be well-orderable.
We use ; characteristic functions identify with . For a cardinal , its successor cardinal is the least cardinal strictly above it, not the ordinal successor . For an infinite cardinal , is the least cardinal length of a cofinal map into the ordinal , as defined in the ordinal chapter.
Theorem/proposition
Theorem 2.4.2
(The infinite square theorem)
In ZF, every infinite well-orderable cardinal satisfies . Hence, in ZFC, every infinite set is equinumerous with its Cartesian square. If are nonzero well-orderable cardinals and at least one is infinite, then
Theorem 2.4.3
(König's inequality)
In ZFC, let be cardinals for every . Then
The strict inequality compares the whole disjoint sum with the whole product, not a sum with the corresponding sum.
Theorem 2.4.4
(Power sets have large cofinality)
In ZFC, for every infinite cardinal ,
In particular . This is a cofinality restriction, not a proof of the continuum hypothesis.
Proof sketch or proof idea
Proof
(Maximum-first ordering of the square)
First, an infinite initial ordinal is a limit ordinal. An infinite ordinal is equinumerous with : send the extra last point to zero, send each natural number to , and fix all other points of . Thus an infinite successor ordinal cannot be the first ordinal of its cardinality.
Suppose the square theorem fails and let be the least infinite cardinal where it fails. Well-order by first comparing , then , then . Every nonempty subset has a least pair: successively minimize these three ordinal coordinates. The predecessors of a pair with maximum lie in . Since , let . If is finite, that square is finite; if infinite, minimality gives . Every proper initial segment of our pair order consequently has cardinal less than .
Let its order type be . If , its initial segment of order type would have cardinal , a contradiction. Thus , giving an injection of the square into . The reverse injection exists because is infinite. Cantor–Schröder–Bernstein finishes the contradiction. Only well-ordered sets entered this argument; no well-ordering of an arbitrary set was smuggled in.
Write . The product injects into , and nonemptiness of both factors gives an injection of the larger one into the product. The disjoint sum injects into , while it contains a copy of the larger summand. This proves both formulas.
Finite strings over an infinite well-orderable alphabet of size also form a set of size . Each positive finite power has size by induction. A single fixed pairing bijection, iterated, supplies uniform encodings for all lengths; tag the length in and use . The empty string adds only one point. The length tag is essential: different-length strings must not accidentally receive the same code.
Proof
(König's diagonal)
For König, use the initial ordinals themselves as coordinate sets. Suppose
were onto. For each , the set has cardinal at most , so it omits a point of . Let be the least omitted ordinal. The function differs from in coordinate for every tagged input . Thus is not in the range, contradicting surjectivity. Cardinal comparability in ZFC turns the absence of a surjection into the displayed strict inequality. If is empty, the sum is zero and the product is a singleton, so the result still holds.
Proof X-ray
Diagonalize against a part of the list
Cantor's proof assigns one forbidden coordinate to each listed function. Here many inputs share coordinate , but there are only such inputs, fewer than the available values. Choose a coordinate value missed by the entire part. The tagging in the sum tells us which coordinate defeats each input; no enumeration of the entire product is assumed.
Before applying the inequality, establish the exponent laws by explicit rearrangement of functions. A function on a disjoint union is exactly a pair of functions; a function assigning a function to each argument is exactly a function of two arguments. Therefore
These are cardinal formulas. They do not assert the corresponding identities for ordinal exponentiation.
Proof
(A short cofinal family contradicts König)
Put and suppose . Choose a cofinal family of ordinals for , and put . Its disjoint sum has cardinal exactly . For the upper bound it injects, after choosing the representative bijections, into , which has size . For the lower bound, every is below some because is a limit ordinal and the family is cofinal. Send to its occurrence in the least such index; the representative bijections then inject into the tagged sum.
For every , . König and the exponent laws now give
a contradiction. The comparison extends functions by zero on the extra arguments, using an injection of into . Both cardinal multiplication and function rearrangement have been proved before they are used here.
Proof X-ray
The identity that makes the power set special
The argument has two halves. Cofinality at most writes as a sum of smaller cardinals, and König makes that sum strictly smaller than a product of factors, each at most . The contradiction then rests on one identity, , which holds because and . For and the first half still works, but it yields only , so no contradiction arises, as requires. Choice enters through the representative bijections and through cardinal comparability.
Worked examples
Worked example 2.4.5
(Pairs of countable ordinals)
The set has cardinal . This does not mean that ordinal multiplication equals : the former order has an entire second block following the first. Cardinal arithmetic forgets order and asks only for a bijection. The maximum-first square order controls earlier pairs without claiming that every familiar order of the same set has the same order type.
Worked example 2.4.6
(Finite descriptions versus infinite streams)
All finite strings over a countably infinite alphabet form a countable set, while binary infinite streams have cardinal . Finite programs can therefore be counted without implying that all infinite outputs or real numbers are computable. Variable finite length is a countable union; infinite length is a function set. Interchanging these constructions loses the diagonal obstruction.
Worked example 2.4.7
(Countable unions need uniform choices)
In ZFC, if is countable for every , choose injections simultaneously. Map each element of to using its least membership index. This injects the union into , hence it is countable. In ZF, merely knowing that each injection exists does not provide the whole family. When the injections are given as data, the same proof needs no new choice. The distinction concerns the selection of encodings, not the final pairing formula.
Worked example 2.4.8
(A cardinal the continuum cannot equal)
The earlier ordinal chapter proved . The new theorem therefore excludes in ZFC. It does not decide whether , nor does it settle every value not excluded by this necessary condition. No forcing or consistency theorem is being invoked.
Common mistakes
Common mistake
(Infinite cardinals do not cancel)
An infinite cardinal can absorb an added copy of itself, so cancellation and subtraction behave differently from finite arithmetic. Removing a subset of size from a set of size can leave nothing, one point, or another set of size . The sizes of the two sets alone do not determine the remainder.
Common mistake
(The square theorem for all sets uses choice)
The square proof concerns well-orderable sets in ZF. Extending it to every infinite set uses the well-ordering principle, hence choice. Likewise, a countable union argument must specify where its family of enumerations came from.
Counterexample mode
König needs strictness in every coordinate
Claim: if for every , then . Take and . The sum is the size of , namely . The product is the set of functions on whose values lie in , and its only member is . Thus
so even the non-strict inequality fails. In the proof, the set is now all of , and no least omitted value exists. The repaired hypothesis is the stated one: in every single coordinate.
Cardinal exponent laws count functions; ordinal powers describe transfinite order constructions. Their notations overlap, but their operations are different.
Summary
Maximum-first ordering proves the infinite square theorem without choice for well-orderable cardinals. It yields the maximum rules for nonzero sums/products and finite-string encodings. Function rearrangement gives exponent laws, while König's coordinatewise diagonal supplies a strict obstruction. Applied to a hypothetical short cofinal family, it proves without resolving the continuum hypothesis.
Exercises
Quick check
(For infinite well-orderable , prove . Give both comparisons and identify the square theorem's role.)
Solution · Answer
The inclusion gives . Since , the reverse bound is . The middle equality rearranges a function of two arguments; the last uses the square theorem. Cantor–Schröder–Bernstein gives equality.
Quick check
(In ZFC, let be infinite and every nonempty have size at most the infinite cardinal . Prove , and explain when equality is forced.)
Solution · Answer
Choice selects injections simultaneously and well-orders . For each union element choose its least membership index, then send it to . Thus the union injects into , whose cardinal is . Equality follows if the union contains a subset of that maximum size. It need not otherwise: all the nonempty may be the same singleton, even when the index set is huge. Disjoint nonempty sets force the lower bound in ZFC, and a member of size forces the other lower bound.
Quick check
(Apply König directly to prove . Compute the sum and obtain an upper bound for the product in terms of .)
Solution · Answer
Each , so König applies. Put . The sum is at most , and it is at least every , hence at least their supremum . Thus , where the upper bound regards each product member as a function into . This is a strict exponent bound at a singular cardinal, not an evaluation of the exponent.
Quick check
(Explain why cannot be the union of a countable increasing family of sets, each of cardinal strictly below . Do not assume a uniform bound on their sizes.)
Solution · Answer
Put and suppose has size while . If , an infinite cardinal bound on all sizes would give union size at most , a contradiction. Thus , giving a countable cofinal family in the ordinal , contradicting . The finite-bound case is covered by enlarging the bound to . Increasingness is not actually needed.
Quick check
(Construct a bijection between and . Deduce and explain why this does not give in cardinal arithmetic.)
Solution · Answer
Send to ; the inverse takes the union of these labeled sections. They are inverse maps, so the equality follows, including empty-domain cases. Cardinal means a disjoint additional point; splitting the exponent domain gives . For infinite , both this product and the cardinal sum happen to equal , but that equality uses infinite arithmetic, not a general exponent distribution over addition. Already for finite , .