Well-foundedness and ordinals

This page is under construction.

Well-founded relations

The concept and properties of well-founded relations are a straightforward generalization of the work we did with algebraic drafts. The point is that the validity of these constructions only made use of some aspects of the involved structures rather than the very precise use of an algebraic language. Namely all we need from drafts is the binary relation ≺ defined as (txOD Im lx), i.e. xy ⇔ (yODx∈Im ly). We can also ignore variables, reinterpreted as constants, leading to an equivalent characterisation of well-foundedness just like (Ind) is equivalent to (Ind1).
Generally, a binary relation ≺ on a set X is called well-founded when it satisfies the following equivalent conditions, abbreviating by [ ] its curried form ⃖≺ (so that xyx∈[y]):

AX, (∀xX, [x] ⊂ AxA) ⇒ A=X
AX, AX ⇒ ∃xX\A, [x]⊂A
AX, A≠∅ ⇒ ∃xA, A∩[x] = ∅
AX, A ⊂ ≺(A) ⇒ A=∅

Well-founded relations are irreflexive and antisymmetric.
Like we get a minimal algebra from any algebra by taking its minimal sub-algebra, we get a well-founded relation from any binary relation ≺ on a set X by restriction to the set of well-founded elements y, equivalently characterized by

AX, (∀xX, [x] ⊂ AxA) ⇒ yA
AX, yA ⇒ ∃xA, A∩ [x] = ∅

Well-founded relations (resp. elements x) have no descending sequence, that is uX such that ∀n∈ℕ, un+1un (resp. with moreover u0 = x).
Indeed such a sequence contradicts well-foundedness as Im u≠∅ and ∀y∈ Im u, Im u∩[y]≠∅.

Transitive closure

Similarly to the concept of co-stability (sub-draft), a subset K of a relational system (X,≺) is called transitive if ∀x,yX, xyKxK. In particular an element zX is called transitive when the set [z] is transitive, as this looks like a formula of transitivity for ≺. It is equivalent to the co-stability (like sub-drafts) of K, i.e. (yK ⇒ [y]⊂K). As this property is stable by intersection, the transitive closure of a set K, is the smallest transitive set including it.

Similarly to the concept of term with a root x, we have the set Tx that is the transitive closure of {x}, obtained from that of [x] by adding there x itself. It is made of all y such that there exists a finite sequence u with

u0=yun=x ∧ ∀i<n, uiui+1.

Now, a relational system is well-founded if and only if all its elements are well-founded; and as can be easily shown, an element x is well-founded if and only if the restriction of ≺ to Tx is well-founded.

Well-founded recursion

For any well-founded relation ≺ on a set X, any set E and any Φ : ∐xX E[x]E, there exists a unique h : XE such that ∀xX, h(x) = Φ(x,h|[x]).

The case of interpretation of drafts in algebras comes as Φ(x,u) = σ(x)E(ulx). The general case admits essentially the same proof as we gave for the algebraic case, so we shall not repeat it here, especially as more interesting variants of this proof will be seen later:

Models of set theory

Among possible recursions along the well-founded relation of an algebraic draft, their interpretations in algebras were particular cases in the sense that from (x,u), the function Φ only used σ(x), ulx and the algebraic structure of E. This letting Φ only depend on the structure of the draft, not being attached to a particular draft, makes it invariant by isomorphism between drafts, and quotientable by condensation.

Now let us focus on a more particular case of recursion obtained by further reducing the sensitivity of Φ: applying to the structure of algebras the same simplification LE∋(s,u) ↦ Im u ∈ ℘(E) by which drafts were reduced to well-founded relations, will make interpretations more generally invariant by any change of domain which preserves the well-founded relation.
Let us call set-algebra a system (E,φ) where φ : ℘(E) → E, from which we define Φ(x,u) = φ(Im u). In fact Dom φ may not be all ℘(E), but just needs to contain all possible Im u for functions u from some [x] to E. For example this may be the set of all finite subsets of E if all sets [x] are finite.

For that use, the quality for a well-founded relation ≺ to play the same role as that of condensed drafts, is the injectivity of x↦[x]. Such relations are called extensional, as this condition is similar to the Axiom of Extensionality, replacing ∈ by ≺ :

x,yX, (∀zX, zxzy) ⇒ x=y.

There is also a unique condensation of any well-founded system (X, ≺) preserving its interpretations in set-algebras: its equivalence relation on X is recursively defined in its curried form as the interpretation of X in the set-algebra P = ℘(X) with structure ℘(P)∋A↦{xX | [x]⊂ ⋃A ∧ ∀BA, B∩[x] ≠ ∅}.
Condensed drafts became term algebras when their injective stuff was bijective, letting the algebraic structure be defined by the inverse. Now trying to do the same, to serve both as a final well-founded system and an initial set-algebra, we cannot make φ bijective from ℘(X) to X, due to Cantor's theorem. Still we can look for some weaker conditions leading to similar properties.
A general idea is that such systems will be models of some set theory, where ≺ plays the role of ∈. While term algebras are essentially unique, looking after similar properties won't make set theory complete either semantically nor logically, but can reduce some of the chaotic diversity of shapes of universes which would otherwise occur.
Thanks to the completeness theorem, the unprovability of a formula in a theory, respectively its irrefutability also called "consistency" (the consistency of the theory where it is added as an axiom), amounts to the existence of models where it is false (resp. true). For set theories and other founding theories, whose consistency cannot be proven in the absolute as we shall see by the incompleteness theorem, we can only talk about the relative consistency of a theory, or of a statement in a theory, which means showing that it is consistent if the previous theory was. Relative consistency results are usually proven by using a model of the old theory to build a model of the new one.
For example, to see that finite set theory is consistent relatively to arithmetic, we can make a countable universe whose objects are all its own finite sets, by means of a bijection between ℕ and the set of all its finite subsets. A natural one is given by the binary representation of natural numbers, where for example {1,2}=6. This forms a well-founded relation.
A simple modification (similarly to the distinction of variables in drafts) gives models U of set theories also admitting pure elements as objects : by a bijection between some class of subsets of U (as viewed from the outside), and a subset of U serving as the class of its "sets". For example a well-founded countable model of the finite set theory with n pure elements represented by numbers lower than n, is given by defining xn+y as "x belongs to the binary representation of y". It is also easy to define a countable model with an infinity of pure elements.
For simplicity, we shall only discuss here universes only made of sets and eventually elements, but not anything else like functions.

Axiom of foundation

The above suggests to require of models of set theory, to have ∈ well-founded, thus allowing to defining something on every set recursively, as determined by what is attributed to its elements. This would formalize the intuitive idea that such universes come as "built" in order, starting from the empty set and progressively adding there sets of already existing objects. From any universe we can make a well-founded one as the meta-set of all sets which are well-founded (in the above sense of well-founded element of a set with a relation, here an element of the universe with the predicate ∈), though care may be needed on details depending on the truths (axioms) we want to preserve.
A problem arises to formalize the well-foundedness of a universe U, which is basically a second-order requirement (using ∀ over ℘(U)), into axioms of set theory which need to be first-order formulas. Before turning such a second-order axiom into a scheme of axioms we may already try it over two kinds of meta-subsets of the universe: the sets, and the complements of sets. Here, one side turns out to not be informative, as, when A is a set, the formula (∀B, BABA) is always false by Cantor's theorem. But the other side is actually called the axiom of foundation (AF):

A, A≠∅ ⇒ ∃xA, Ax = ∅

Its relative consistency easily comes by taking the meta-set of all sets E which seem "well-founded" for the similar expression (∀A, EA ⇒ ∃xA, Ax = ∅), but the question remains whether it actually suffices to make the universe well-founded. To answer this, we need the concept of transitive closure.
The condition for a set x to be well-founded would be expressed by AF where A ranges over all meta-subsets of its transitive closure Tx which is a priori only defined as a meta-set. Finally for A to actually range there in AF, we just need Tx to be a set, whose powerset we shall then trust to do the job. So, are all Tx sets ?
From set theory we can get Tx as the union of the sequence u recursively defined by u0=x ∧ ∀n∈ℕ, un+1 = ⋃un... if only such a sequence exists. Otherwise, we may add as an axiom that Tx is a set ... if justified from the intended well-foundedness of the universe: from the recursive expression Tx = {x}∪⋃yx Ty, we could deduce that Tx is a set when all Ty are sets... if only {Ty | yx} was accepted as a set in the universe. But this does not result either from our previously accepted axioms, since this expression is a priori only defined on the meta level.
But a good reason to add it as an axiom, is to make the universe actually useful in its intended role as a union of representatives of all extensional well-founded relations, where recursion would be well-defined... by formulas which make sense inside the same universe without the help of any special language for it. Namely, to define the image of any x by any recursion, requires to check its validity by using, as a function, the interpretation of that recursion with domain at least Tx, which must thus be a set. May that mean to add Tx to the universe, or to remove x from there when Tx cannot be found.

More needed axioms

Any well-founded system (X, ≺) must have its image (unique interpretation) among sets related by ∈. This axiom is relatively consistent for the following reason.
Any use of this axiom will only apply it to some family of well-founded systems (Xi, ≺i)iI, indexed by a set I. Then the sum of this family forms itself a well-founded system, which can be condensed into an extensional one, where all (Xi, ≺i) are interpreted. Let us admit here that without contradiction, we can assume the existence of a copy (Y, ≺) of that extensional system made of pure elements. Now that copy Y can be changed into a set of sets related by ∈, by the modification of the predicate ∈ giving to each element y of Y the role of the set [y], itself left as a pure element.∎
A similar trick shows the relative consistency of the negation of the foundation axiom : from any extensional but non-well-founded relation we can create a copy related by ∈ as well.

Now well-founded recursion can process from any system Tx of sets related by ∈ in particular, just like from any well-founded system in general, with target any given set-algebra known to be a set. However, to also work with target the whole universe, is a quite stronger requirement : it implies the just mentioned ability of sets to represent all well-founded relations (by recursion from a well-founded set into the universe) but is not relatively consistent anymore, in particular for the already mentioned sequence of powersets of ℕ. But this, as well as the existence of the transitive closure of any set, are just a particular cases of the even much stronger scheme of replacement that is the last part of ZF, which will be discussed later.

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. How theories develop
4.5. Second-order logic
4.6. Well-foundedness and ordinals
4.7. Undecidability of the axiom of choice
4.8. Second-order arithmetic
4.9. The Incompleteness Theorem