Defining and comparing infinities : ordinals and cardinals

Different concepts of infinities and their comparisons, have been introduced in mathematics. The most important ones are the ordinals, the cardinals and the nonstandard numbers.

We already presented the nonstandard numbers in the previous text. This was due to the coexistence of different models of arithmetic. Now we shall present the ordinals and cardinals, which are "pure» set theoretic concepts (describing objects and staying in a fixed model of set theory) not involving any consideration of other theories and models.

Cardinals

Like with most other mathematical concepts, the notions of "size" and "size comparison" for sets, however intuitive they may seem, do not have any a priori meaning, but any meaning such words can have must come from somewhere, namely from a definition that must be given. So, the notion of cardinal is a concept defined in set theory to "compare the size" of any sets, including the infinite sets, generalizing the counting of elements by natural numbers.

Philosophical note : Some marginal philosophers would believe in the preexistence of a meaning of the words "size», "smaller» and "larger» for sets, purely based on their intuitive feeling that these words should make a priori sense, prior to any formal definition, and might even want to argue that this meaning differs from the concept of cardinal as it is commonly accepted; but such a discussion in fact has nothing to do with mathematics, since there is no logical way to express or discuss what some words of human language such as "size» and "comparison of size» should "really mean» as suggested by the intuition rather than from any formal definition. Only a few words and concepts from natural language can and need to be accepted as making a priori clear (unambiguous) mathematical sense without further explanations, in order for mathematics to have a start somewhere. The essential thing is to care only admitting this way the concepts that are indeed mathematically clear without trap. Such distinctions are not always obvious for beginners, but may require some experience to be done correctly. But well, nowadays this work has been completed. 

The concept of cardinals consists in saying that two sets E and F "have the same cardinal", or in sort, "are equipotent" as an abbreviation to mean that there exists a bijection between them. In the early times of set theory, people had a problem dealing with this name of "cardinals" that behave as sorts of "objects" of set theory which they could not easily formalize as effective objects among those admitted in the basic formalism. This problem was later resolved by taking the ZFC axiomatic system where ordinals appear as specific objects, and all cardinals are represented by ordinals (any set is in bijection with an ordinal) and there is a standard way to pick up a specific ordinal representing each cardinal.
However in fact we do not necessarily need the ZFC axiomatic theory for considering cardinals as a legitimate notion : instead they can be formalized without being uniquely determined objects, by letting sets play their role : the role of a variable with value a cardinal can be played by a variable with value any set in the cardinal (as a class of sets in bijection with each other), and formalizing formulas on cardinals by formulas whose value remains unchanged by replacing this set by any other set in bijection with it.

The main properties of cardinals are the following:

The class of cardinals is ordered by the relation of existence of injections between sets

It is easy to see that the relation between X and Y defined by "There is an injection from X to Y" is a preorder, that only depends on the cardinals of X and Y. It is an order (the existence of injections from X to Y and from Y to X implies the existence of a bijection, section 3.5).

Except if X=∅, the relation "There is a surjection from Y to X" is weaker than (implied by) "there is an injection from X to Y" (section 2.5), and is equivalent if the Axiom of Choice is accepted.

The powerset of X is stricly bigger than X

We have the obvious injection from X to P(X) defined by x {x}.
Cantor's theorem (2.5) says there cannot be any surjection from X to P(X). Thus there cannot be any injection from P(X) to X either (independently of the axiom of choice).

There is no set of all cardinals

For any set of cardinals, that is concretely, a set of sets representing different cardinals, their union is larger than each (as there is an obvious injection); then its powerset is even larger. Thus no set of sets can ever represent all cardinals.

Infinite cardinalities cannot easily increase without the powerset

Indeed we can easily find a bijection between ℕ and ℕ×ℕ. A set with the same cardinality as ℕ is said countable. Generally, many infinite sets are countable. Namely, those that can defined using no more than a finite sequence of numbers. For example the set of (positive or negative) integers, the set of rational numbers, the set of algebraic numbers (solutions of algebraic equations with rational coefficients)

The powerset preserves inequalities of cardinals

Without the axiom of choice, from a surjection from X to Y we can define an injection from P(Y) to P(X), and more generally from ZY to ZX for any set Z (see 2.5).

The set ℝ of real numbers has the same cardinality as P(ℕ)

Indeed we can find an injection from ℝ to [0,1], then from [0,1] to P(ℕ) given by the binary expansion; then we can find an injection from [0,1] to ℝ using the development in base 3 (or any other number than 2).
We can also find an injection from ℕ to ℝ using continuous fractions. But the equipotence between ℕand P(ℕ) can as well be deduced from P(ℕ)≈P(ℕ×ℕ)≈P(ℕ)≈P(ℕ)

The continuum hypothesis is undecidable

The continuum hypothesis is the claim "There is no cardinal between those of ℕ and P(ℕ)". A very hard result of mathematical logic is that the number of intermediate cardinals between ℕ and P(ℕ) can roughly be any number between zero and many infinities, depending on the model of set theory. However it would be naive to say "There may exist an intermediate cardinal but we cannot find it". In fact the problem (cause of undecidability) is not to find it, but it is whether the explicitly constructed set (that is the candidate set for having an intermediate cardinal), is in bijection with P(ℕ) or not. We shall explain this below.

This can be contrasted with the case of finite sets : if X is a finite set with n elements then P(X) has 2n elements. Thus there are manier and manier intermediate cardinals when n increases.

More properties use the axiom of choice

If the axiom of choice is accepted then cardinals form a total order (for any sets X and Y there either exists an injection from X to Y or from Y to X). And more precisely, a well-ordering, as cardinals can be represented by ordinals, that is, essentially, well-ordered sets.


Back to the main menu