Motivation
Counting a set should produce an answer that does not depend on the order in which its elements were counted. That familiar assertion needs a proof: it says that two different natural numbers cannot be bijective. The same proof explains why an injective map from a finite set to itself is surjective, and why that implication changes when the set is infinite.
We work in ZF, using the natural numbers and their arithmetic already constructed. Here denotes the finite ordinal , so . Countable choice will be stated explicitly when it is needed. These notes fill elementary dependencies of the cardinality chapters.
Counting and the pigeonhole principle
Definition 2.3.1
(Finite and infinite sets)
A set is finite if there is a bijection for some . It is infinite if no such natural number exists. We have not yet proved that this is unique. A finite ordinal is a particular ordered set, whereas an arbitrary finite set need not arrive with an order or a preferred enumeration.
Theorem 2.3.2
(Finite pigeonhole principle)
For every natural number , there is no injection from to . More generally, an injection can exist only if .
Proof
(Induction with a transposition)
Induct on . A function from the nonempty set to the empty set cannot exist. For the induction step, suppose there is no injection , but that is injective. Put . On the target , let exchange and , fixing the other elements. If , take to be the identity. This is a permutation, so is injective and .
No other input can have image . Restricting to the inputs therefore gives an injection , contradicting the induction hypothesis. This proves the first assertion. If , restriction of any injection to its first inputs would contradict that assertion.
The transposition in this proof has a purpose: it moves one occupied target to the last position, so that deleting the last input also frees the last target. Merely deleting an arbitrary input and an arbitrary target would not leave a function with the desired codomain.
If both and are bijections, their composite inverses give bijections between and . The theorem yields and , hence . We can now write for a finite set without ambiguity. In particular, the empty set has cardinality zero and no nonempty set does.
Subsets, images and finite self-maps
First prove a small closure fact without relying on the conclusion we seek: every subset of a finite set is finite. It suffices to consider and induct on . For , only the empty subset occurs. For , the set is finite by induction. If , then . If and is a bijection, extend by sending the new input to ; this is a bijection . Transport the result along an enumeration for an arbitrary finite ambient set.
A proper subset of a set of cardinality has cardinality strictly below . To see the strictness, let and take . If , exchanging with gives a bijection . Thus injects into . Since it is finite, pigeonhole gives . The case has no proper subset.
An image of a finite set is finite too. For , associate to each its least preimage in . These least preimages form a subset , and is bijective. The subset result proves finiteness. Taking the least preimage is justified by the given finite order; no choice principle is used.
Theorem 2.3.3
(A finite self-map is injective exactly when it is surjective)
If is finite and , then is injective if and only if it is surjective.
Proof
(Reduction to pigeonhole in both directions)
Enumerate and conjugate by that enumeration, reducing to . If is injective but misses an element, its range is a proper subset with cardinality . A bijection from that range to turns into an injection , contradicting pigeonhole.
Conversely, suppose is surjective. Let consist of the least preimage of each target. Then is a bijection onto . If were not injective, some fiber would contain two different inputs, of which only its least belongs to . Thus would be proper. Its cardinality would be below , contradicting the bijection . This includes : the empty self-map is both injective and surjective.
Worked example 2.3.4
(Infinite self-maps break both implications)
The shift , defined by , is injective and misses zero. In the other direction, put and . This map is surjective, since reaches every , but it is not injective because . The finite theorem has failed in both directions, with two explicitly different maps. It did not fail because one of the definitions of injection or surjection changed.
What finite constructions preserve
If and , fix enumerations and . Taking two witnesses in one proof is a finite logical operation, not an application of the axiom of choice.
The tagged union is bijective with : use the first positions for the first tag, and the next for the second. Forgetting the tags maps this finite set onto , so the ordinary union is finite and has cardinality at most . Equality need not hold when and overlap.
The product has cardinality . If either factor is empty this is immediate. Otherwise, enumerate by the index for . Division with remainder gives a unique inverse for every index below . Composing with gives the claimed bijection. Induction now proves that every union or product indexed by a finite set of finite sets is finite. The initial cases are the empty union, which is empty, and the empty product, whose only member is the empty function. This induction proves existence of each finite collection of enumerations; it does not select an infinite family of them.
The power set of has cardinality . Start with , of cardinality . If , each subset of has exactly one description as either or , where . These two forms are disjoint and identify the new power set with . Induction gives .
Concept lensCombinatorial
Subsets as binary records
A subset carries the same information as its indicator function , where exactly when . The map is a bijection from onto the set of functions , inverted by . Through an enumeration , such a function is a record of binary positions. Adding a new element adds one position, which is the factor in the induction above.
Worked example 2.3.5
(An overlap changes the count)
Let and . Their tagged union has five elements, whereas has four. Their product has six elements, including the distinct pairs and . The power set of consists of , , and , so has four elements. These are different constructions, even though all start with the same two finite sets.
Worked example 2.3.6
(Finite records do not make every collection of records finite)
Every function has a graph with exactly three ordered pairs: is a bijection onto the graph. Nevertheless the set of all these functions is infinite, because the constant functions are distinct for distinct . A finite domain makes each individual record finite. A finite number of possibilities at each of finitely many positions is the stronger hypothesis that makes the whole collection finite.
Removing repetitions from an infinite range
An infinite set and a sequence visiting infinitely many of its elements are different pieces of information. Once a sequence is supplied, however, repetitions can be removed without choice.
Theorem 2.3.7
(An infinite range contains a canonical countable subset)
If has infinite range, there is an injection , defined from alone.
Proof
(Keep the first occurrence of each value)
Keep the first occurrence of each value. More precisely, separation gives
For every element of the range there is a least occurrence index, so is a bijection from onto the range. If were finite, the range would be finite by the image result. Thus is an infinite subset of .
Every infinite subset of is unbounded: a bound would put it inside a finite ordinal. Define and, recursively, . Unboundedness ensures that the set in this minimum is nonempty. Each value is uniquely determined, so ordinary recursion and replacement produce the whole function . Finally set . The indices increase and belong to , hence their values are distinct.
Proof X-ray
A least choice is a specified rule
The proof takes infinitely many minima, but it does not invoke an axiom saying that arbitrary simultaneous selections exist. For each stage, the existing order on specifies exactly one next index. Recursion applies to this single-valued rule. This is why a sequence with infinite range supplies more than a bare assertion that the ambient set is infinite: it supplies the ordered positions on which a least-occurrence rule can operate.
For , the first-occurrence indices are , and the construction returns .
Counterexample mode
Infinitely many positions do not give an injection
Claim: the first-occurrence construction turns every sequence into an injection . Take and for even , for odd . Index is a first occurrence, and so is index because . Every repeats the value . Hence
The recursion stops at the third step. No other construction can succeed: an injection restricted to would be an injection , contradicting pigeonhole. The repaired statement is the theorem as stated: an infinite range makes infinite, hence unbounded, so every minimum is taken over a nonempty set.
Where countable choice enters
Definition 2.3.8
(Countable choice)
Countable choice, , asserts that for every sequence of nonempty sets there is a function choosing one member of each . The sets themselves need not be finite or countable.
An infinite set admits an injection for every finite , already in ZF. Indeed, begin with the empty function. An injection with finite range cannot exhaust , for otherwise would be finite. Taking one element outside that range extends the finite injection by one position. Induction proves the separate existence assertions for every .
That induction does not produce one sequence of compatible choices. Nor does the statement automatically yield a function assigning one suitable to every .
Theorem 2.3.9
(Countable choice supplies a countable subset of an infinite set)
In ZF together with , every infinite set contains a countably infinite subset.
Proof
(Choose tuples, not a coherent sequence)
For each , let be the set of all injections . This is a set, as a subcollection of the function set, and the preceding finite induction proves . Replacement forms the uniquely specified sequence . Countable choice supplies one for each .
The tuples need not extend one another. Put . This is a set and it is infinite: if , the injection would violate pigeonhole. To supply a sequence onto , fix and define
This maps onto . A fixed pairing bijection turns it into a sequence with range . The preceding theorem removes repetitions to give an injection . Its image is the required countably infinite subset.
Proof X-ray
Why incoherent tuples still give an infinite set
The selected tuples may disagree everywhere: need not extend . The proof needs only that their ranges together are not finite, and pigeonhole supplies that from a single member, , once a size is assumed. The padding value makes total on without a second selection; it exists because has one input. The order of the remaining steps is forced: removing repetitions needs a sequence, so the union is first enumerated through the fixed pairing, and only then does the first-occurrence theorem produce the injection.
Only the selection of the family used countable choice. We did not assume dependent choice, a well-order of , or coherent tuple choices. The countable-range argument explains why coherence is unnecessary.
The earlier cardinality notes prove in ZF that an injection is equivalent to a bijection between and a proper subset of itself; the latter property is Dedekind infinitude. Consequently the present theorem proves, under , that every infinite set is Dedekind infinite. We have proved this implication, not an equivalence with , and we have not constructed a choiceless countermodel. In an argument using ZF alone, do not replace “infinite” by “Dedekind infinite” without a further justification.
Common mistakes
Common mistake
(Finite induction does not collect infinitely many witnesses)
Finite induction justifies any fixed finite succession of existential choices. It does not by itself collect infinitely many witnesses. Conversely, not every infinite recursion needs choice: the least-index construction above already has a unique output at each step.
Common mistake
(An injective self-map of an infinite set need not be onto)
An injection into an infinite set does not have to be onto, even when its domain is that same set. The finite self-map theorem depends on the finite pigeonhole theorem.
Common mistake
(Finite members do not come with enumerations)
Saying that each member of a sequence of sets is finite does not supply enumerations of all those sets. A later exercise identifies a sufficient choice principle for that separate task.
Exercises
Quick check
(For naturals , characterize exactly when an injection exists and when a surjection exists. Include empty domains and codomains.)
Solution
An injection exists exactly when : inclusion gives sufficiency and pigeonhole gives necessity. A surjection exists exactly when either , or . For the latter case, send to itself and all remaining inputs to zero. Necessity follows by taking the least preimage of each target, which gives an injection . If , no function exists at all; if , the empty function cannot be onto.
Quick check
(Prove that a finite set cannot be bijective with a proper subset of itself. Identify the point at which the shift avoids your argument.)
Solution
If and , then by the proper-subset result. A bijection would contradict finite cardinal uniqueness, or pigeonhole. For , the proper subset is not a subset of a finite ordinal. The induction proving the strict finite-size inequality therefore does not apply.
Quick check
(Let . Compute the first-occurrence set and the injection returned by the infinite-range theorem. Explain why applying that theorem to a constant sequence is invalid.)
Solution · Answer
Each value first appears at , so , and . A constant sequence has a one-element range and ; there is no next first-occurrence index after zero. The hypothesis guaranteeing those next indices is absent.
Quick check
(Prove in ZF that is infinite if and only if for every there is an injection . Explain why this statement alone is not a construction of an injection .)
Solution · Answer
If is infinite, extend finite injections one at a time as proved above; induction gives existence for every finite length. Conversely, if were bijective with , an injection followed by that bijection's inverse would contradict pigeonhole. The separate witnesses need not be compatible and have not been selected as a family. The quantifiers are not an already supplied function of .
Quick check
(Assuming , prove that the union of a sequence of finite sets is at most countable. Do not assume enumerations have already been supplied, and include the empty-union case.)
Solution
For each , let be the unique finite cardinal of . Uniqueness and replacement supply the function . The set of bijections is nonempty; when , it contains the empty bijection. Countable choice selects simultaneously. Let . If is empty, its injection into is empty. Otherwise fix one and send to for , and to otherwise. This is a surjection from onto . Pairing gives a sequence onto , and assigning each value its least occurrence index gives an injection . The last step works for finite or infinite .
Quick check
(Call Dedekind finite if it is not bijective with any proper subset of itself. Using the earlier Dedekind equivalence and this unit's infinite-range theorem, prove that every function has finite range. Prove the converse too.)
Solution · Answer
An infinite range for some would, by the theorem, give an injection . The earlier equivalence would make Dedekind infinite, a contradiction. Thus all such ranges are finite. Conversely, if were Dedekind infinite, that same equivalence would supply an injection , whose range cannot be finite by pigeonhole. For there are no functions ; the range condition is vacuously true, as it should be.