This page discusses cardinals and cardinal arithmetic, both with and without the Axiom of Choice. In general the subject is a very rich one with many results and still many difficult problems at the research level.
Cardinal numbers are discussed at length in the beginning of Section 11.1 of The Mathematics of Logic. In particular two sets have the same cardinality or are equipolent (written ) if there is a bijection . This is an equivalence relation on sets. Informally you can think of the cardinality of a set as the equivalence class of the set by this equivalence relation, but this raises a problem: the cardinality of a set if defined this way is not itself a set but a class. To get round this problem one of two alternative definitions are usually provided.
In the absence of the Axiom of Choice, the following definition is usually preferred.
, the cardinality of , is the set .
Thus the cardinality of a set is the set of sets equipolent to it of minimal rank. Since this is a subset of some it is a set.
If the Axiom of Choice holds then a simpler alternative is available.
By the well-ordering principle every set is well-orderable, and hence in 1–1 correspondence with an ordinal. Thus there is a least ordinal . We define to be this ordinal.
This definition has the advantage that is a canonically chosen set with the same cardinality as . Note that the two definitions, as just given, are not compatible. In practice, the definition (any definition) of is simply a convenience rather than essential, since results about a cardinal are usually proved by first taking a set that has that cardinality. Here we will implicitly assume AC holds and take the second definition of cardinal, but indicate which of the theorems we prove do not need choice.
An ordinal is initial if there is no bijection for .
For example, is initial but is not. (This is a consequence of the next proposition below.)
Given a set , the least ordinal in 1–1 correspondence with it is an initial ordinal, since if not there would be a smaller ordinal in 1–1 correspondence with , because 1–1 correspondences compose. Thus cardinals are initial ordinals. Conversely, all initial ordinals are their own cardinals.
An infinite initial ordinal is a limit ordinal.
If is infinite there is a bijection defined by , for and for all other .
The theorems and proofs in Sections 11.1 and 11.3 should be studied carefully. All of the proofs there are valid in or , and where Zorn's lemma was used it is known that some form of the Axiom of Choice is required for the result in question. In particular the definitions of cardinal arithmetic and the order relation on cardinals is important. We define
For sets , if there is an injection . We define if or there is a surjection .
However, the Zorn's lemma proof in the book that cardinal arithmetic has for all infinite is slightly long-winded. For those that know about ordinals (including everyone reading these web pages) there is a different proof.
First we define bijections recursively on ordinals . Define , , and for limits . Define to be the empty function, and if , if , and if ; finally for any with . You can check that these define bijections as claimed and extends for .
If is an infinite initial ordinal then there is a bijection .
Suppose is initial and for every smaller initial ordinal there is a 1–1 correspondence . Consider . If we are finished, by Schröder–Bernstein. So . Also for all initial since , and all have the same cardinality strictly less than . Let and let so is in the range of . Now as is initial and hence is a limit ordinal. Therefore there is a bijection from to , some initial ordinal less than , and this induces an impossible bijection from to .
The previous result does not need the axiom of choice, but the conclusion that for all infinite cardinals does not follow from it without choice as (in the absence of choice) some sets are not well-orderable.
The axiom of choice is not required in this section either.
Given any set , we define .
For all sets , is a set, and hence an ordinal. There is no injection and is the least ordinal with this property.
So is a set by separation and power set axioms and there is for each a unique ordinal order-isomorphic to . Define and by replacement the image of is a set, and note that this image is . There is no injection for if there was we would have .
For all , is initial.
If not, and are bijections then their composition maps injectively, so .
Initial ordinals are sometimes called Alephs because of the following.
, the first infinite initial ordinal; ; and for limit ordinals .
Each is initial; every initial ordinal is for some .
If is a limit and is a bijection then a restriction of is an injection , contradicting Schröder–Bernstein. Thus every is initial as the result is obvious for the zero and sucessor cases. The converse is proved by taking an initial ordinal and considering the least ordinal such that . This exists by the fact that for all , and must be a successor. For if is a limit, by definition of there would be with . Thus and so there is an injection as , hence as is initial.
Under the Axiom of Choice, every set is well-ordered so is in one-to-one correspondence with an ordinal. Thus the Axiom of Choice implies every cardinal is an aleph.
Hartog's function gives one way to make a larger cardinal from a smaller one. Another way is to use the power set function.
Let be a set. Then there is no bijection between and .
Suppose is a bijection and let . We get a contradiction by taking such that and trying to decide if or not.
For a set , is the cardinality of .
Thus we have two ways to make a cardinality just a bit bigger than :
either or . Assuming the Axiom of Choice
we have . Cantor's Continuum Hypothesis (CH)
is the statement that . Whether or not this is
remains a moot point, but it has been shown to be independent of the ZFC axioms
(assuming ZFC to be consistent.
More generally, the Generalised Continuum Hypotheis (GCH) is the statement for all . Again, this is consistent with the axioms of ZFC but not provable in them. It can be shown that GCH implies the axiom of choice, so assuming GCH makes no sense without also assuming AC.
The Trichotomy theorem (Proposition 11.18 in The Mathematics of Logic) is equivalent to the Axiom of Choice. To see this, let be any set. Then it is not the case that , by the construction of Hartog's function, so by Trichotomy . In other words there is an injection and as is an ordinal a well ordering on may be defined via this injection and on . Under a particular assumption on the arithmetic of certain cardinals, an interesting weakening of trichotomy can be obtained without Choice. In this section are just names for infinite cardinals: the fact we call them this is not intended to mean that they are necessarily ordinals. (Sometimes they will be ordinals, sometimes not.)
If are cardinals such that then or .
Suppose are disjoint sets with cardinalities and is a bijection and is the projection map. If the composite of is onto then we know that . Otherwise there is such that for each the unique such that is in . This defines an injection taking into . Thus .
This result has the consequence that our theorem on cardinal arithmetic is in fact equivalent to the axiom of choice.
If for all infinite cardinals then the Axiom of Choice holds.
Let be an arbitrary set with cardinality and let . Then so by Schröder–Berstein . Thus by the previous either or . But is impossible by the definition of and hence so there is a surjection and hence an injection given by is the least with . This allows us to define a well-ordering on as before.
On the other hand, the proposition for all infinite cardinals is known to be strictly weaker than the axiom of choice.