Infinity: Beyond Recursive Ordinals

This is the twelfth and penultimate post of the Infinity Series. For all posts, see the Infinity Series Portal.

In the previous post, the idea of an ordinal collapsing function was expanded to produce a series of these functions, each corresponding to a natural number. One could go even further listing fixed points and identifying ordinals inaccessible from certain operations and functions, but this is tedious, and is of little interest. To identify further ordinals beyond those accessible with a method involving fixed points, one must use a totally new idea.

Though set theory was mentioned as the basis for all subject matter in this series, no rigorous definition was ever made of any part of this theory. Rather, it has been assumed that the sets mentioned can be defined and constructed. However, set theory is based on assuming a few intuitively obvious or underlying statements that are accepted as being true. These are known as axioms. Formulae derived from these axioms or combinations thereof are then true statements.

However, there is no one "correct" set of axioms from which to assemble a theory that simultaneously has two desirable qualities: consistency and completeness. A consistent theory contains no two statements contradicting one another, i.e. if, for some statement p, "p is true" is derivable from the axioms "p is false" is not. In contrast, a complete theory is such that every statement p can be proved either true or false from the axioms. It was proved by Gödel in his incompleteness theorems that a set theory incorporating arithmetic cannot be simultaneously consistent and complete.

Therefore, there is a multiplicity of possibilities for the selected axioms, with no one clearly the "best", and, correspondingly, there are many different varieties of set theory. Of interest here are the axioms involved in the construction of sets. One basic axiom present in many variations of set theory is the pairing axiom, which, in logical notation, is

∀A∀B∃C∀D(D ∈ C↔(D = A∨D = B)).

In this axiom, A, B, C, and D are set variables, meaning that they take as values sets only, ∀ is the universal quantifier, read "for all", ∃ is the existential qualifier, meaning "there exists", ∈ is the membership relation, ↔ is the biconditional meaning "if and only if", and ∨ is the logic gate "or". Therefore, in common english, the axiom of pairing states:

"For all sets A and B, there exists a set C such that for all sets D, D is a member of C if and only if D is equal to A or D is equal to B."

This can be further paraphrased to "For any two sets, there is a third containing only the two as members", which simply allows one to create a set with a given two members, hence the name "pairing". Together with the definition {S,S} = {S}, which simply means that redundant elements in a set are deleted, one can construct the ordinals 1 and 2 from 0 through the axiom of pairing. 1 = {0} is derived from the case A = B = 0 in the axiom, as C is then {0} = 1. Furthermore, if A = 0 and B = 1, then the axiom guarantees the existence of the set {0,1} = 2. However, the ordinal 3 cannot be constructed in the same fashion, as it has more than two members. Therefore, the axiom of union, another axiom useful in constructing sets, is introduced:

∀A∃B∀C(C ∈ B↔∃D(C ∈ D∧D ∈ A))

This axiom collects all sets C such that C is a member of a member of A into a set B, known as the union of A. Note the relation to the definition of union we have already seen: the operation of union, when applied to multiple sets, collects their members; similarly, the union of a single set is the union of all its members. For example, the union of the set {{Ø},{{Ø}},{Ø,{Ø}} = {{0},{1},{2}}, the members of which are all guaranteed to exist by the axiom of pairing is the same as the union of its members, namely {0}∪{1}∪{2} = {0,1,2} = 3. By use of these two axioms, any finite ordinal can be constructed.

There is a third important axiom, called the axiom of infinity, which grants the existence of an infinite set, specifically the ordinal ω. Without it, one can not prove that infinite ordinals exist, and ω, the first ordinal that cannot be proven to exist, is called the strength of the theory. Strictly speaking, even some theories without the axiom of infinity "know" that ω exists, i.e. know that there is a set of natural numbers, but cannot prove that it is well-ordered, and thus cannot confirm its status as an ordinal. Thus far, the axioms discussed have been part of the theory known as Zermelo-Frankel Set Theory, or ZF set theory. The strength of this theory is measured by an ordinal higher than any ordinal so far discussed, as ZF set theory includes the concepts of function, fixed point, and (to a limited extent) inaccessibility. Therefore, all the processes used to describe ordinals thus far are "embedded" in ZF, and all the ordinals stated thus far can be explicitly constructed.

Technically, this new ordinal, which we shall call the ZF-ordinal, is not an ordinal at all, at least in ZF theory, where we cannot even confirm its status as an ordinal. This is an example of incompleteness in ZF theory. In order to prove that the ZF-ordinal, which contains all countable ordinals constructed thus far, is an ordinal, one must add additional axioms to ZF to strengthen the theory, and augment its ability to construct ordinals. But what axioms should be added? The type of axioms that serve this purpose are called large cardinal axioms, and confirm the existence of cardinals with certain properties. It seems somewhat odd that axioms concerning cardinal numbers would have anything to do with constructing ordinals. However, of the most importance are the properties themselves of the cardinals, which outline new methods for constructing ordinals.

The precise forms of these axioms will not yet be explained, as they do pertain to large cardinals that have not yet been discussed, but we will outline the hierarchy which they form. The first large cardinal axiom will be called A1, and is independent of ZF set theory, i.e. cannot be proved true or false by the existing axioms. Therefore, a new theory consisting of the original axioms and A1 is formed, which will be denoted ZFA1. This new theory can construct the ZF-ordinal, and even higher countable ordinals at that. The set of ordinals that can be constructed in this theory is again an ordinal, and by definition, its status as an ordinal is indeterminate within ZFA1. It is called the ZFA1-ordinal. By assuming more axioms A2, A3,..., one can obtain higher ordinals, and correspondingly "higher" set theories ZFA2, ZFA3,..., each of which has a higher corresponding strength. The ordinals defined in this way are called (rather paradoxically) unrecursible recursive ordinals, referring to the fact that they cannot be defined by recursive functions within the given theory, but rather require the theory itself in their definition.

From here one can set up a hierarchy of axioms. For any two axioms of this type, X and Y, either the two are "equal" in that they can be proved to imply one another, or one is stronger than the other, and augments ZF to yet a stronger set theory. The limit of the strength of the successive theories in this way may be further increased by using so-called axiom schemata (singular schema), which introduce additional variables into the logical statement. An axiom schema asserts that the given statement is true for all values of the variable. Also, meta-axioms, namely procedures for finding more axioms can extend the hierarchy even further. Eventually, a point is reached where no strengthened version of ZF or any other type of function can generate an ordinal. This inaccessible limit is called the Church-Kleene ordinal, and is written ω₁^CK.

ω₁^CK is the set of all recursive ordinals, and is then an ordinal, although it cannot be proven that this is true in any of the theories yet described. One could say that this ordinal's definition is based on those smaller than it and is therefore recursive, but this is not true, as the system of recursion itself is within the definition. Additionally, ω₁^CK could have served as the Ω in the previously discussed ordinal collapsing functions (see here), though, technically speaking, the ZF-ordinal or any others of the "unrecursible recursive" variety would have served as well. ω₁^CK is often chosen simply because its definition is simpler and more elegant.

Remarkably, ω₁^CK is still countable. This can be seen by considering the fact that there are only countably many notations through which to define ordinals; for each function considered thus far, each can take only countably many arguments, and there are only countably many functions based off of countable ordinals. Since all recursive notations are exhausted on countable ordinals, ω₁^CK is countable. Nor is it the last countable ordinal. One can of course create the set including all recursive ordinals and ω₁^CK, which is the ordinal ω₁^CK + 1, and so on.

In fact, one can define the set of all ordinals accessible from functions on all ordinals including the Church-Kleene ordinal, which is some other limit ordinal that could have served as Ω₂. Furthermore, by repeatedly define inaccessible ordinals, one can obtain a sequence of countable ordinals, each of which is greater than any recursive function on the previous one, and is parallel to the Ω sequence.

There is no end to this process, and one can generate as many countable ordinals as desired in a similar fashion. However, no matter how far one goes with defining countable ordinals, one can only reach an infinitesimal fraction of them, as functions defined within the countable ordinals always produce still more countable ordinals. The situation is analogous to that of whole numbers: one can always define a larger one, but there are always still infinitely more. How, then, can one work with uncountable ordinals and their cardinal counterparts? These problems will be addressed in the next post.

Sources; http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?handle=euclid.pl/1235418473&view=body&content-type=pdf_1,
Axiomatic Set Theory by Patrick Suppes, A New Kind of Science by Stephen Wolfram