# Well-orderings and ordinals

A well-ordering on a set is an order relation where every nonempty subset has a least element. Well-orderings are total orders, which means that any 2 elements are always comparable (as the pair must have a least element among them). Two well-ordered sets are called isomorphic if there is a strictly monotone bijection between them (=which preserves the order, and thus all properties of this order)

The natural order on the set ℕ is a well-ordering (this is an expression of the recursion axiom). Thus the concept of well-ordering generalizes the order relation on ℕ. There are many well-orderings which are not isomorphic to that of ℕ.
The restriction of a well-ordering to any subset is also a well-ordering. So any subset of ℕ is well-ordered. In fact the well-orderings 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-orderings bigger than ℕ too. The description of any well-ordering 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.
Contrary to the general study of order relations, for well-orderings we generally need the strict (antireflexive) order. So we shall write < for the strict order, and ≤ for the large order.

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.
(The proof is a little difficult technically; it can be helped by the below construction that replaces Zorn's lemma).

An ordinal can be defined as an isomorphism class of well-ordered sets. The traditional study of ordinals, and thus of well-orderings, formalizes each ordinal by its only representative whose strict well-ordering 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; the large well-ordering is then the inclusion. 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-orderings 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-orderings 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-ordering 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.

### 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.

### Well-ordering and the axiom of choice

We shall show later that the axiom of choice implies the existence of a well-ordering on all sets. This is a bit difficult to prove but the converse is simple:

If all sets can be well-ordered then the axiom of choice can be deduced in the following way. If ∀x∈E, ∃y∈F, xRy, then with a well-ordering on F we can define f from E to F by f(x) = the smallest y such that xRy.

Thus without the axiom of choice we cannot assume that ZF-ordinals which are cardinals represent all cardinals.

### 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-ordering 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-ordering 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-ordering of this subset...

### Construction of Aleph1

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, that is undecidable, is takes the form of the claim "There is a bijection exists between Aleph1 and P(ℕ)".

### Surreal numbers

This is a construction of somethings that aims to behave as a nonstandard set of real numbers (a "nonstandard set of real numbers" basically means the system of "real numbers" in a model of set theory or second-order arithmetic whose "set of natural numbers" is non-standard), but based on ordinals instead of normal model-theoretical tools.
However the "explicit" character of this construction happens at the expense of ordinary properties: only the basic operations seem to be defined (but it does not even seem clear how it works and whether it will keep working in all cases) but not more complicated ones: while the multiplication seems to be defined (?), the decomposition of numbers in prime factors is not (as far as I know) since this decomposition requires logical tools not contained in this construction.
So I won't present this construction here.

## An alternative to Zorn's lemma

The following theorem is independent of the axiom of choice, but the results in set theory traditionally deduced from Zorn's lemma can instead be deduced from this together with an elementary expression of the axiom of choice.

Theorem. Let φ a function whose domain D is a set of sets, such thatxD, φ(x)∉x. Then there exists a unique subset KD satisfying the following properties

• The restriction φ|K is injective
• ∀x∈K, x⊂φ[K]
• The binary relation on K defined by (x,y)(φ(x)∈y)  is a strict well-ordering
• φ[K]∉D.

Proof.

Note : I'm not satisfied with this proof that is quite long and complicated. I hope to find a more elegant proof (through more interesting intermediate steps) in the future.

The proof will make use of Tarski's Fixed Point Theorem (3.5).
Let f be the function from P(D) to itself defined by:

• xD, f({x}) =  {x∪{φ(x)}} if x∪{φ(x)}∈ D, or ∅ otherwise
• For any other A⊂D, f(A) = {∪A} if ∪A ∈ D, or ∅ otherwise. In particular, f(∅) = {∅}
Then let K be the smallest subset of D stable by f (such that ∀AK, f(A)⊂K). By the fixed point theorem, ∀xD, xK⇔(x=∅∨(y K, x = y∪{φ(y)})∨(A K, x = ∪A)).

xK,∀Ax, (∀y,y'K, (yA ∧ (y∪{φ(y)}= y'⊂x))⇒y'⊂A))⇒A=x because
If (∀y,y'∈K, ((yA)∧ y∪{φ(y)}= y'⊂x)⇒y'⊂A)), then the set C={z∈K| z⊂x⇒z⊂A}is stable by f. Thus C=K. But x∈K, thus x⊂x⇒x⊂A. Finally A=x.
x,yK, (x⊂y ∨ yx) because
Let us show that C={xK|∀yK, xyyx}is stable by f. The stability by unions is straightforward :
AC, ∀yK, ((∃xA, yx)⇒y⊂∪A ) and ((∀x∈A, xy)⇒∪Ay)
Then ∀xC, ∀x',zK, x' = x∪{φ(x)}⇒((zxx')∨(xz)). Now if xz and φ(x)∉z then (∀y,y'∈K, (y⊂x ∧ y∪{φ(y)}= y'⊂z)⇒(x=y'∨x⊄y')⇒y'⊂x), so that x=z according to the above, and z⊂x'. In the other case of x⊂z and φ(x)∈z we have x'⊂z. Finally x'∈C.
Thus C is stable by f, thus C=K, thus ∀x,yK, (x⊂y ∨ y⊂x).
x,yK ,  (x⊂y ∧ x∪{φ(x)}∉K) ⇒x=y because
∀z,z'K, (zx ∧ (z∪{φ(z)}= z'⊂y))⇒ (z'=x ∨ x⊄z') ⇒ z'⊂x.
The restriction φ|K is injective because
xyK, φ(x)=φ(y)⇒φ(x)∉y ⇒(x∪{φ(x)}∉Ky = x)⇒x=y.

(To be continued).