4.7. Ordinals and cardinals

This page is under construction.

Well-order

A well-order is a total order where every nonempty subset has a smallest element.
The order in ℕ is a well-order. Obviously, the strict order of any well-order is well-founded, extensional and transitive. Less obvious is the converse:

Proposition. If a relation ≺ on a set X is well-founded, extensional and transitive then it is a strict total order, thus defining a well-order.

Proof. Denote xy ⇔ (xyx=y) and ∀xX, Bx = {yX | xyyx}.
For any xX such that ∀zx, Bz=X,
yX, [y]⊂Bx ⇒ ((∃zy, xzxy) ∨ ([y]⊂[x] ∴ (([y]=[x] ∴ y=x) ∨ (∃zx, yzyx)))) ⇒ yBx.
Thus Bx=X.
Thus ∀xX, Bx=X. ∎
Then xy ⇔ [x]⊂[y].
Indeed ⇒ comes from transitivity; ⇐ comes from totality and extensionality (yx contradicts [x]⊂[y]).

The restriction of a well-order to any subset is also a well-order. So any subset of ℕ is well-ordered. In fact the well-orders on finite sets are the total orders, and they are isomorphic as soon as they have the same number of elements.
But there are well-orders bigger than ℕ too. The description of any well-order is always the same: it starts from the smallest element (0), then the smallest above 0 (1), then the smallest above 1 (2), and so on up to infinity; then the smallest after all natural numbers, then the next one, then the next,... and so on to infinity, then the next... and so on and so forth, even possibly beyond any description, but this can stop at any time. See Chaitin's speech for a more explicit description.

An initial segment of a well-ordered set E is a subset of E of the form {x∈E | x<y} for some y∈E..
A fundamental property  is that for any two well-ordered sets E and F, there exists a unique isomorphism that is either between E and F, or between E and an initial segment of F, or between an initial segment of E and F.

An ordinal can be defined as an isomorphism class of well-ordered sets. The traditional study of ordinals, and thus of well-orders, formalizes each ordinal by its only representative whose strict well-order is given by the membership predicate ( ∈ ) and that are transitive (x∈A∈E ⇒ x∈E). In such conditions we have {x∈E | x<y}=y, which may simplify things. But the proof of existence of such an ordinal isomorphic to any well-ordered set, requires the schema of replacement to be proven. Here we shall call ZF-ordinals the transitive sets well-ordered by ∈.
In fact most properties of well-orders and their isomorphism classes can as well be developed without such a representative, thus without the axiom schema of replacement, though it may be a little bit more tedious.

Any set of ordinals (as classes of well-ordered sets) is well-ordered by defining "equality" by the isomorphism, and the order between non-isomorphic well-orders is given by which of both sets is isomorphic to an initial segment of the other.

In the case of ZF-ordinals this all simplifies as the same predicate ∈ defines the strict well-order inside and between all ordinals.

There is no set of all ordinals

For any ordinal there is a bigger one obtained by adding an element after it. In fact, for any well-ordered set E, we can define the "next" well-ordered set as the set of all initial segments of E plus E itself. That is E ∪{E} in the case of ZF-ordinals. And for any set of ordinals we can take their "union", that is the smallest ordinal that is larger than them all. This is simply the union as sets in the case of ZF-ordinals.

Cardinals

In mathematics, the idea of a multiplicity of infinities, beyond the finite countings by natural numbers, requires to choose a precise concept (a theory) to define and compare infinities (as whenever words or intuitions such as "size" or "large" are not a priori clear, they can only become mathematically meaningful relatively to a choice of definition or other formal clarification). There are mainly 3 such concepts: cardinals, ordinals, and nonstandard numbers. Ordinals and cardinals are defined in set theory.
The concept of cardinal consists in saying that two sets E and F "have the same cardinal", when they are equinumerous (there exists a bijection between them).
As we already saw, model theory somehow sees all infinities as the same in the sense that they cannot be distinguished by any first-order description, according to the Löwenheim-Skolem theorem; but since this confusion affects the distinction of finiteness itself, it provided the concept non-standard numbers by looking at the formalism of finite countings from a viewpoint where the finiteness of its objects is seen as an illusion.

Some ordinals are cardinals

Among all ordinals in bijection with a given ordinal, there is a smallest one. Such a smallest ordinal inside a cardinal (an ordinal not in bijection with any initial segment of itself) will be chosen to represent this cardinal.

There is no set of all cardinal-ordinals either

If we could well-order any set (thus, if we accept the axiom of choice) then we could simply argue that the class of cardinal-ordinals does not form a set because this has been shown for cardinals in general.
For example, ℕ is not the biggest cardinal because P(ℕ) is bigger and any well-order on it gives an ordinal with cardinality larger than ℕ.

Otherwise the traditional method also uses the axiom schema of replacement, making it unclear which assumptions are needed to show that the class of cardinal-ordinals is not a set. However we can still deduce it from just the powerset axiom, without either the axiom of choice nor the axioms of replacement, but this is a little bit more subtle. Here it goes:
For any well-ordered set X, take the set A={R⊂X×X | R is a well-order of a subset of X}. Then the quotient of A by the relation of isomorphism, is naturally a well-ordered set whose ordinal is the smallest ordinal with cardinality strictly larger than X. Because if it was in bijection with a subset of X then it would define a well-order of this subset...

Construction of Aleph1 - the continuum hypothesis

The continuum hypothesis states the existence of an uncountable subset of ℘(ℕ) not equinumerous with it. It is undecidable.

This is the smallest uncountable cardinal-ordinal, thus a candidate as an intermediate cardinal between ℕ and P(ℕ).
According to the above, it can be explicitly constructed out of P(ℕ), as the quotient of a well-defined subset of P(ℕ) ≈ P(ℕ×ℕ) by a well-defined equivalence relation. Thus there exists a surjection from P(ℕ) to it.
Using the axiom of choice it can be represented as a subset of P(ℕ).
The continuum hypothesis takes the form of the statement "There is a bijection exists between Aleph1 and P(ℕ)".


Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Model Theory
4.1. Finiteness and countability
4.2. The Completeness Theorem
4.3. Non-standard models of Arithmetic
4.4. Development of theories : definitions
4.5. Constructions
4.6. Second-order logic
4.7. Well-foundedness
4.8. Ordinals and cardinals
4.9. Undecidability of the axiom of choice
4.10. Second-order arithmetic
4.11. The Incompleteness Theorem