Cardinals

Source file content/set-theory/cardinals/cardinals.tex

Source file content/set-theory/cardinals/cp.tex

Cantor's Principle

Cast your mind back to section “Von Neumann's Construction of the Ordinals” in chapter “Ordinals”. We were discussing well-ordered sets, and suggested that it would be nice to have objects which go proxy for well-orders. With this is mind, we introduced ordinals, and then showed in corollary six in chapter “Ordinals” that these behave as we would want them to, i.e.:

Cast your mind back even further, to section “Equinumerosity” in chapter “The Size of Sets”. There, working naïvely, we introduced the notion of the “size” of a set. Specifically, we said that two sets are equinumerous, $\cardeq{A}{B}$source, just in case there is a bijection $f \colon A \to B$source. This is an intrinsically simpler notion than that of a well-ordering: we are only interested in bijections, and not (as with order-isomorphisms) whether the bijections “preserve any structure”.

This all gives rise to an obvious thought. Just as we introduced certain objects, ordinals, to calibrate well-orders, we can introduce certain objects, cardinals, to calibrate size. That is the aim of this chapter.

Before we say what these cardinals will be, we should lay down a principle which they ought to satisfy. Writing $\card{X}$source for the cardinality of the set $X$source, we would want them to obey:

We'll call this Cantor's Principle, since Cantor was probably the first to have it very clearly in mind. (We'll say more about its relationship to Hume's Principle in section “Appendix: Hume's Principle” in chapter “Cardinals”.) So our aim is to define $\card{X}$source, for each $X$source, in such a way that it delivers Cantor's Principle.

Source file content/set-theory/cardinals/cardsasords.tex

Cardinals as Ordinals

In fact, our theory of cardinals will just make (shameless) use of our theory of ordinals. That is: we will just define cardinals as certain specific ordinals. In particular, we will offer the following:

We just used the phrase “$A$source can be well-ordered”. As is almost always the case in mathematics, the modal locution here is just a hand-waving gloss on an existential claim: to say “$A$source can be well-ordered” is just to say “there is a relation which well-orders $A$source”.

But there is a snag with definition one in chapter “Cardinals”. We would like it to be the case that every set has a size, i.e., that $\card{A}$source exists for every $A$source. The definition we just gave, though, begins with a conditional: “If $A$source can be well-orderedldots”. If there is some set $A$source which cannot be well-ordered, then our definition will simply fail to define an object $\card{A}$source.

So, to use definition one in chapter “Cardinals”, we need a guarantee that every set can be well-ordered. Sadly, though, this guarantee is unavailable in $\ZF$source. So, if we want to use definition one in chapter “Cardinals”, there is no alternative but to add a new axiom, such as:

We will discuss whether the Well-Ordering Axiom is acceptable in chapter “Choice”. From now on, though, we will simply help ourselves to it. And, using it, it is quite straightforward to prove that cardinals (as defined in definition one in chapter “Cardinals”) exist and behave nicely:

The next result guarantees Cantor's Principle, and more besides. (Note that cardinals inherit their ordering from the ordinals, i.e., $\cardfont{a} < \cardfont{b}$source iff $\cardfont{a} \in \cardfont{b}$source. In formulating this, we will use Fraktur letters for objects we know to be cardinals. This is fairly standard. A common alternative is to use Greek letters, since cardinals are ordinals, but to choose them from the middle of the alphabet, e.g.: $\kappa, \lambda$source.):

noindent We can also use the lemma on Cardinals Behave Right to re-prove Schröder--Bernstein. This is the claim that if $\cardle{A}{B}$source and $\cardle{B}{A}$source then $\cardeq{A}{B}$source. We stated this as the theorem on schroder bernstein, but first proved it---with some effort---in section “Appendix: Proving Schröder-Bernstein” in chapter “Infinite Sets”. Now consider:

noindent Whilst this is a very simple proof, it implicitly relies on both Replacement (to secure theorem five in chapter “Ordinals”) and on Well-Ordering (to guarantee the lemma on Cardinals Behave Right). By contrast, the proof of section “Appendix: Proving Schröder-Bernstein” in chapter “Infinite Sets” was much more self-standing (indeed, it can be carried out in $\Zminus$source).

Source file content/set-theory/cardinals/milestone.tex

$\ZFC$source: A Milestone

With the addition of Well-Ordering, we have reached the final theoretical milestone. We now have all the axioms required for $\ZFC$source. In detail:

$\ZFC$source stands for Zermelo--Fraenkel set theory with Choice. Now this might seem slightly odd, since the axiom we added was called “Well-Ordering”, not “Choice”. But, when we later formulate Choice, it will turn out that Well-Ordering is equivalent (modulo $\ZF$source) to Choice (see theorem “in set theory Z F” in chapter “Choice”). So which to take as our “basic” axiom is a matter of indifference. And the name “$\ZFC$source” is entirely standard in the literature.

Source file content/set-theory/cardinals/classing.tex

Finite, enumerable, nonenumerable

Now that we have been introduced to cardinals, it is worth spending a little time talking about different varieties of cardinals; specifically, finite, enumerable, and non-enumerable cardinals.

Our first two results entail that the finite cardinals will be exactly the finite ordinals, which we defined as our natural numbers back in definition of the natural numbers and omega in chapter “Steps towards Z”:

noindent It also follows that several reasonable notions of what it might mean to describe a cardinal as “finite” or “infinite” coincide:

This licenses the following definition of some notions which we used rather informally in part “Naïve Set Theory”:

noindent But note that this definition is presented against the background of $\ZFC$source. After all, we needed Well-Ordering to guarantee that every set has a cardinality. And indeed, without Well-Ordering, there can be a set which is neither finite nor Dedekind infinite. We will return to this sort of issue in chapter “Choice”. For now, we continue to rely upon Well-Ordering.

Let us now turn from the finite cardinals to the infinite cardinals. Here are two elementary points:

Now, as early as the definition on enumerable, we flagged we can distinguish between enumerable and non-enumerable infinite sets. That definition naturally leads to the following:

noindent Indeed, $\omega$source has a special place. Whilst there are many countable ordinals:

Of course, there are infinitely many cardinals. So we might ask: How many cardinals are there? The following results show that we might want to reconsider that question.

You should compare this with both Russell's Paradox and Burali-Forti.

Source file content/set-theory/cardinals/hp.tex

Appendix: Hume's Principle

In section “Cantor's Principle” in chapter “Cardinals”, we described Cantor's Principle. This was:

where `$F \sim G$source' abbreviates that there are exactly as many $F$sources as $G$sources, i.e., the $F$sources can be put into a bijection with the $G$sources, i.e.:

But there is a type-difference between Hume's Principle and Cantor's Principle. In the statement of Cantor's Principle, the variables “$A$source” and “$B$source” are first-order terms which stand for sets. In the statement of Hume's Principle, “$F$source”, “$G$source” and “$R$source” are not first-order terms; rather, they are in predicate position. (Maybe they stand for properties.) So we might gloss Hume's Principle in English as: the number of $F$sources is the number of $G$sources iff the $F$sources are bijective with the $G$sources. This is called Hume's Principle, because Hume once wrote this:

And Hume's Principle was brought to contemporary mathematico-logical prominence by Gottlob Frege (1884), §63, who quoted this passage from Hume, before (in effect) sketching (what we have called) Hume's Principle.

You should note the structural similarity between Hume's Principle and Basic Law V. We formulated this in section “Appendix: Frege's Basic Law V” in chapter “The Iterative Conception” as follows:

And, at this point, some commentary and comparison might help.

There are two ways to take a principle like Hume's Principle or Basic Law V: predicatively or impredicatively (recall section “Predicative and Impredicative” in chapter “The Iterative Conception”). On the impredicative reading of Basic Law V, for each $F$source, the object $\fregeext{x}{F(x)}$source falls within the domain of quantification that we used in formulating Basic Law V itself. Similarly, on the impredicative reading of Hume's Principle, for each $F$source, the object $\fregenum{x}{F(x)}$source falls within the domain of quantification that we used in formulating Hume's Principle. By contrast, on the predicative understanding, the objects $\fregeext{x}{F(x)}$source and $\fregenum{x}{F(x)}$source would be entities from some different domain.

Now, if we read Basic Law V impredicatively, it leads to inconsistency, via Naïve Comprehension (for the details, see section “Appendix: Frege's Basic Law V” in chapter “The Iterative Conception”). Much like Naïve Comprehension, it can be rendered consistent by reading it predicatively. But it probably will not do everything that we wanted it to.

Hume's Principle, however, can consistently be read impredicatively. And, read thus, it is quite powerful.

To illustrate: consider the predicate “$x \neq x$source”, which obviously nothing satisfies. Hume's Principle now yields an object $\# x( x\neq x)$source. We might treat this as the number $0$source. Now, on the impredicative understanding---but only on the impredicative understanding---this entity $0$source falls within our original domain of quantification. So we can sensibly apply Hume's Principle with the predicate “$x = 0$source” to obtain an object $\#x (x = 0)$source. We might treat this as the number $1$source. Moreover, Hume's Principle entails that $0 \neq 1$source, since there cannot be a bijection from the non-self-identical objects to the objects identical with $0$source (there are none of the former, but one of the latter). Now, working impredicatively again, $1$source falls within our original domain of quantification. So we can sensibly apply Hume's Principle with the predicate “$(x = 0 \lor x = 1)$source” to obtain an object $\#x(x = 0 \lor x = 1)$source. We might treat this as the number $2$source, and we can show that $0\neq 2$source and $1 \neq 2$source and so on.

In short, taken impredicatively, Hume's Principle entails that there are infinitely many objects. And this has encouraged neo-Fregean logicists to take Hume's Principle as the foundation for arithmetic.

Frege himself, though, did not take Hume's Principle as his foundation for arithmetic. Instead, Frege proved Hume's Principle from an explicit definition: $\fregenum{x}{F(x)}$source is defined as the extension of the concept $F \sim \Phi$source. In modern terms, we might attempt to render this as $\fregenum{x}{F(x)} = \Setabs{G}{F \sim G}$source; but this will pull us back into the problems of Naïve Comprehension.