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

Infinity: Extended Collapsing Functions

This is the eleventh post of the Infinity Series. For the first, see here. For all posts, see the Infinity Series Portal.

In the previous post, an ordinal collapsing function was used to access high ordinals. However, all the outputs of the function discussed so far are alternatively expressible as Veblen functions with finite numbers of arguments. It was also seen that ψ(Ω^Ωα) is equal to the supremum of all ordinals that can be represented by an α + 1-argument Veblen function. This continues up to
ψ(Ω^Ωω), the first ordinal requiring infinite arguments to represent in Veblen notation. Being the supremum of countably many countable ordinals, it is countable, and is known as the small Veblen ordinal, though this ordinal is of course nothing near small.

In fact, it is small only when compared to even larger ordinals, such as the large Veblen ordinal, which is equal to ψ(Ω^ΩΩ). Alternatively, this ordinal represents the supremum of all others writable in Veblen notation of infinitely many, but only predicatively many, arguments. In short, since Veblen functions of high numbers of arguments are built off of those with lower numbers of arguments, only predicative ordinals, or those can be defined using lower ordinals alone, can serve as the number of arguments for such a function. Since Ω is clearly larger than any predicative ordinal, ψ(Ω^ΩΩ) is the supremum of the entire system of Veblen notation.

However, the ordinal collapsing function goes still further, defining ψ(Ω^ΩΩΩ), and in general ψ(Ω↑↑n) for finite n. Eventually one reaches the value ψ(ε_{Ω + 1}). The function is finally permanently stuck here, as ε_{Ω + 1} is not constructible from the original set S, and cannot be generated to plug to the ψ function. It is therefore never a member of the set C(α) no matter the value of α. ψ(ε_{Ω + 1}) is known as the Bachmann-Howard ordinal.

To go further using ordinal collapsing functions, we define a second function ψ₁, the value of ψ₁(α) being the smallest ordinal that cannot be finitely constructed using addition, multiplication, exponentiation, the original ψ function and ψ₁|_α, or the ψ₁ function restricted to α, these operations beginning from the set T₁ = {0,1,...,ω,...,Ω,Ω₂}, where Ω₂ is an ordinal higher than any of those that will be constructed with the ψ₁ function, and consequently, higher than Ω (again, it is not necessary for the definitions of Ω and Ω₂ to be in any way precise). Also, T₁ is assumed to contain all ordinals up to and including Ω, although we have no way yet of characterizing these ordinals, and so the definition is once again impredicative.

ψ₁(0) is clearly just ε_{Ω + 1}, as ψ₁|₀ is degenerate and has no values. But since all the ordinals less than Ω are in T₁, none of these can be equal to ψ₁(0), and since the ψ function only produces ordinals less than Ω, the first ordinal that is inaccessible is simply the limit of normal operations on Ω, namely ε_{Ω + 1}. Note that this is not the Bachmann-Howard ordinal, but a much larger indefinite quantity, the Bachmann-Howard ordinal being the ψ function at this value,
ψ(ε_{Ω + 1}). In fact, we cannot even be assured of the countability of ε_{Ω + 1}, due to the vagueness with which Ω was defined. Next,

ψ₁(1) = ε_{Ω + 2},

with the last term being the upper limit of iterated exponentiation on ε_{Ω + 1}. Now we return to the original collapsing function ψ, and modify its definition as follows:

ψ(α) is the first ordinal that cannot be constructed from the set S₁ = {0,1,ω,Ω,Ω₂} using the operations addition, multiplication, exponentiation, ψ|_α, and ψ₁.

Note no restriction is necessary on ψ₁ in this definition, as ψ₁ only produces values strictly greater than Ω, which is in turn greater than any ordinal produced by the ψ function. The outputs of ψ₁ therefore cannot affect which ordinal assumes the value of ψ(α), no matter its domain. This new definition produces values identical to those produced by the old for all ψ(α) such that α ≤ ε_{Ω + 1}, and using the same notation therefore produces no ambiguity. However, ψ(ε_{Ω + 1} + 1) is not equal to the Bachmann-Howard ordinal for this definition, since ε_{Ω + 1} is in C(ε_{Ω + 1} + 1). ψ(ε_{Ω + 1} + 1) is then equal to the next epsilon number after the Bachmann-Howard ordinal, namely

ε_{ψ(ψ1(0)) + 1} = ε_{ψ(εΩ + 1)) + 1}

One can go on through ψ(ψ₁(0) + 2), ψ(ψ₁(0) + Ω), and so on, on up to
ψ(ψ₁(1)) = ψ(ε_{Ω + 2}). Returning to ψ₁, ψ₁(2) = ε_{Ω + 3}, and in general
ψ₁(α) = ε_{Ω + 1 + α}, for all α up through Ω (with ψ₁(Ω) = ε_Ω*2) and beyond. Each of these can be plugged into the ψ function to yield yet another large countable ordinal, some of which are ψ(ψ₁(ψ₁(0))), ψ(ψ₁(ψ₁(ψ₁(0)))), and so on. Since each nested ψ₁ essentially iterates the ε function on Ω + 1, the limit of these expressions yields the first fixed point of such iteration, in other words the first α such that ψ₁(α) = α. This ordinal is ζ_{Ω + 1}, hence ψ₁(ζ_{Ω + 1}) = ζ_{Ω + 1}.

In a situation analogous to the original ψ function, ψ₁ is temporarily stuck at ζ_{Ω + 1}, as ζ_{Ω + 1} requires infinite steps to produce from T₁. ψ₁(α) is then fixed from ζ_{Ω + 1} on up to Ω₂, with ψ₁(Ω₂) still equal to ζ_{Ω + 1}, but ψ₁(Ω₂ + 1) is larger, as the domain of the restricted function ψ₁|_{Ω2 + 1} includes Ω₂, which is in T₁. ψ₁ is developed further in a similar way, a few notable values being

ψ₁(Ω₂*2) = ζ_{Ω + 2},
ψ₁(Ω₂²) = η_{Ω + 1}, and
ψ₁(ε_{Ω2 + 1}),

with the last being the highest value attainable by the ψ₁, as the function is constant afterward, in the same fashion as ψ is after ε_{Ω + 1}. Therefore,
ψ(ψ₁(ε_{Ω2 + 1})) is the highest ordinal accessible by the current definition of ψ, but is still much less than Ω.

Of course, there is no need to stop here. One can introduce a third function ψ₂, with ψ₂(α) the smallest ordinal not constructible from the set T₂ = {0,1,...,ω,...,Ω,...Ω₂,Ω₃}, in other words the set that contains all ordinals up to and including Ω₂, as well as an additional ordinal Ω₃, which is an arbitrary ordinal higher than any value that ψ₂ will attain.

ψ₂(0) is then equal to ψ(ψ₁(ε_{Ω2 + 1})). The definition of subsequent values of ψ₂ is as follows

ψ₂(α) is the smallest ordinal inaccessible from the operations of addition, multiplication, exponentiation, ψ, ψ₁, and ψ₂|_α from the set T₂.

One then alters the definitions of ψ₁, and finally, ψ, analogously in order to admit values such as ψ(ψ₁(ψ₂(Ω))), which is far greater than any ψ ordinal yet discussed, but of course considerably less than Ω. One can continue to generalize these functions, defining ψ₃, ψ₄, and so on, and each time altering all previous definitions accordingly. For natural numbers i and j, the function ψ_i adjusted for all ψ functions up to j, with j ≥ i, is written as ψ_ij. The general definition below is true for all functions ψ_ij (with the original ψ replaced by ψ₀ for clarity):

ψ_ij(α) is the smallest ordinal not constructible through a finite series of the operations addition, multiplication, exponentiation, ψ₀, ψ₁,..., ψ_i|_α, ψ_{i + 1},..., ψ_j on any elements of the set {0,1,...,ω,...,Ω,...Ω₂,...,Ω_i,Ω_{i + 1},...,Ω_j}, where each Ω_k is an arbitrary ordinal larger than any constructible with the function ψ_{k - 1}.

To understand this general definition, a few observations must be made. First, due to the definition of Ω_k, it is higher than any ordinal constructible with the previous ψ function. Therefore, the only restricted function in the definition is the one that is being defined, namely ψ_i, which produces ordinals strictly below Ω_i. Since the other ψ functions stay within their respective ranges also, they cannot (by themselves) produce a value in this range, and cannot directly affect ψ_i(α). Also, the purpose of the value j is simply to identify how "upgraded" each ψ function is, e.g., the difference between the initial definition of ψ (ψ₀) versus its "upgraded" definition incorporating ψ₁. Moreover, the set from which the ordinals are being constructed includes all ordinals up through Ω_i, but afterwards only the Ω ordinals between i and j.

Finally, the purpose of this multitude of functions is merely to plug them back in to ψ in order to generate further values, all of which are still far less than Ω. The limit of these functions is still less than Ω, and is sometimes denoted ψ_ω(0). By the use of fixed points, many more ordinals can be defined in this matter, but the processes involved are identical to those discussed. However, there are still higher countable ordinals, some of which are even beyond the principle of recursion (see the next post).

Sources: Large Countable Ordinals- Wikipedia, http://www.ams.org/journals/tran/1908-009-03/S0002-9947-1908-1500814-9/S0002-9947-1908-1500814-9.pdf

Infinity: Impredicative Ordinals

This is the tenth post of the Infinity Series. For the first, see here. For all posts, see the Infinity Series Portal.

At the conclusion of the previous post, Γ₀, the first impredicative ordinal, and the first defined with a "second-order" definition, was introduced. The remainder of the Γ-sequence was also defined. To find higher countable ordinals, one precedes in a similar manner to previously, by finding fixed points.

For example, the smallest fixed point of α → Γ_α is also the supremum of the set {Γ₀,Γ_Γ0,Γ_ΓΓ0,...}, and is known as the Ackermann ordinal, named after Wilhelm Ackermann, known for his contributions to computation theory.

Again, it becomes useful to have a standard notation for these ordinals, and a generalized form of the Veblen hierarchy is quite useful. To extend the Veblen notation, first we replace what was previously denoted as φ_β(α) with φ(α,β), namely a function of two arguments, the first being what was before the argument, and the second that which was the subscript. To extend the Veblen functions beyond what was already considered, we add a third argument γ, and consider the ordinals defined by expressions of the form φ(α,β,γ). These expressions are evaluated in the following way:

First, φ(α,β,0) = φ(α,β). Then, φ(0,0,1) is defined as the first ordinal that is inaccessible through the expressions φ(α,β), constructing from 0 upward. Since this definition is identical to the one for the Feferman-Schutte orindal, φ(0,0,1) = Γ₀. To become more familiar with the notation, consider these further examples:

φ(0,1,1) = φ_{Γ0 + 1}(0), or the first fixed point of the first Veblen function after φ_Γ0, φ(0,0,2) is equal to Γ₁, or the second fixed point of φ_α(0) → α. Every increase here in the second argument of the generalized Veblen function represents listing fixed points. Each increase in the third represents another Γ value. For example, φ(0,0,2) = sup{φ(0,0,1),φ(0,φ(0,0,1),1),φ(0,φ(0,φ(0,0,1),1),1),...}, with the second argument β assuming the value of the previous member in each element of the set, until Γ₁ is obtained. It is easy to see this is consistent with the previously cited value of Γ₁. All other φ(0,0,γ) can be defined this way, and, continuing from the discussion of Γ₀, which was defined in a second-order fashion, these ordinals have second-order definitions, and are all impredicative.

The smallest ordinal inaccessible from the standard operations on all the ordinals φ(0,0,1), φ(0,0,2), φ(0,0,3), etc. of finite third argument γ, yields a new γ value: ω, the ordinal being written φ(0,0,ω). Of course other values for α and β are also possible, such as φ(1,5,ω) or φ(ε₀,Γ₃,ω). But of more concern is the third argument, which can increase through more countable values until reaching nested Veblen functions such as φ(0,0,φ(0,0,1)), defining a sequence in which the γ assumes the value of the previous member of the sequence. Having gone as far as possible with three arguments, a fourth is introduced in the following way:

sup(φ(0,0,1),φ(0,0,φ(0,0,1)),φ(0,0,(φ(0,0,φ(0,0,1))),...} = φ(0,0,0,1)

Since φ(0,0,1) = Γ₀, the above equation is exactly the same as sup{Γ₀,Γ_Γ0,Γ_ΓΓ0,...} = φ(0,0,0,1). Additionally, φ(0,0,0,1) is the first fixed point of Γ_α → α, and, as said above, is also known as the Ackermann ordinal. This ordinal has a "third-order" definition, and is also impredicative by most definitions.

One can go on to define φ(α,β,γ,...,δ) for any finite number of arguments, all of which are limits similar to the example above, and although inaccessible from previous operations, are countable for all countable α,β,γ,...,δ. It becomes inconvenient to deal with so many arguments however, so there is an alternate method to create large countable ordinals with a function of only one argument.

As stated above, it is possible to go still further, by the use of a new kind of function, called an ordinal collapsing function. These functions again use the idea of inaccessibility in their definition, but there is a crucial difference between these and Veblen functions: ordinal collapsing functions assume the existence of an ordinal Ω that is beyond any ordinals that can be constructed with ordinal collapsing functions. This ordinal does not have to be defined in any precise way, but simply is assumed to exist as an upper limit to any ordinal constructed. However, since ordinals generated by ordinal collapsing functions make use of Ω, this definition is impredicative, as it assumes the existence of a larger ordinal to define a smaller.

To construct this function, first consider the set of ordinals S = {0,1,ω,Ω}. The set C(0) is then defined as containing all ordinals that can be constructed through a finite process from 0,1,ω, and Ω using addition, multiplication and exponentiation, including 1, 2, 3, ω, ω^ω, and ω^ωω. C(0) also includes Ω, Ω + 1, Ω^Ω, and others of this type, but these are not as important for the time being.

Now, we denote the smallest ordinal that is not in C(0) as ψ(0) (with the symbol psi, rather than phi for Veblen functions). ψ(0) is then equal to ε₀, the first ordinal that requires infinite steps from ω to construct. Next, C(1) is the set of ordinals constructible from S with addition, multiplication, and exponentiation, and the function ψ|₁, or the ψ function restricted to 1. Such a function can only take as an argument values that are members of 1, namely, only 0 (all ordinals are sets of all previous ordinals). Hence the ordinal ψ(0) = ε₀ is a member of C(1), as well as sequences of the normal three operations on it, such as ε₀ + 1, ε₀^ε₀, and so on.

The smallest ordinal not in C(1) is written ψ(1), and is equal to ε₁, as no finite sequence of operations from ε₀ yields this value. Similarly, C(2) is the set of ordinals accessible from members of S through the normal operations plus ψ|₂. Since 1 is a member of 2, ψ(1) = ε₁ is a member of C(2), as is ε₀ and any operations on these two ordinals with the other members of S. Preceding recursively, C(α) has as a member all ordinals defined through the three normal operations, and ψ|_α, which has a domain of all ordinals less than α.
ψ(α) is defined as before, and is seen to equal ε_α for all finite α.

But what about when α = ω? C(ω) includes all values taken by ψ|_ω, namely ε₀, ε₁, ε₂,..., ε_α, and so on for all finite α, as well as operations upon them. The corresponding ψ(ω) is the clearly ε_ω as this transcends all previous epsilon values and operations on them. Thus the equivalence of ψ(α) and ε_α continues for some infinite values of α. In fact, this equality holds true as long as α is less then or equal to ε_α.

However, in the case of α = ζ₀ (for which ε_α = α), C(ζ₀) includes all of the epsilon sequence below ζ₀, but does not contain the ordinal itself, as even applying the function ψ|_ζ0 to 0 any finite number of times (producing the sequence ε₀, ε_ε0,...) cannot yield ζ₀, and ψ(ζ₀) = ζ₀. α = ζ₀ + 1 presents an interesting case. One would think that the pattern would continue, generating ε_{ζ0 + 1} as the value for ψ(ζ₀ + 1). However, for this to happen, ζ₀ would have to be a member of C(ζ₀), since if this were not the case, ε_{ζ0 + 1} would not be the smallest ordinal not in C(ζ₀). But, beginning with the set S, it is impossible to construct ζ₀ with a finite number of operations. Even though one of the operations available for C(ζ₀) is ψ|_{ζ0 + 1}, which has ζ₀ in its domain and would produce ζ₀, no number of steps from S can produce this value in the first place to plug it into the function! There is therefore no way to obtain ζ₀, and
ψ(ζ₀ + 1) = ζ₀.

By the same logic, ψ(ζ₀ + 2), ψ(ζ₀ + ω), and others are still equal to ζ₀. It may seem that the function is "stuck" at ζ₀, and can produce no higher value. This is where Ω comes in. Consider the set C(Ω). This set is no different from previous ordinals in that it ψ(Ω) = ζ₀. The difference appears when considering C(Ω + 1), as ordinals in this set can be constructed from S using ψ|_{Ω + 1} along with the other three operations. Since Ω is in S and in the domain of ψ|_{Ω + 1}, ψ(Ω), that is, ζ₀, is in C(Ω + 1). If not for the addition of Ω to S, this function would cease to increase, and this is the importance of Ω. It also explains the name "ordinal collapsing function", as it takes large ordinals such as Ω, and using a function, "collapses" them into smaller ordinals, in this case ζ₀.

It has been established that ψ(Ω + 1) is larger than ζ₀, but what is it? C(Ω + 1) also includes the usual operations on ζ₀, including iterated exponents such as ζ₀^ζ₀ζ₀. Clearly the smallest ordinal that cannot be accessed in this way is ε_{ζ0 + 1}, and this is equal to ψ(Ω + 1). The correlation between the ε and ψ functions continues from there, with ψ(Ω + α) = ε_{ζ0 + α} for all finite and some infinite values of α, including cases greater than ζ₀. For example, ψ(Ω + ζ₀*2) =
ε_{ζ0 + ζ0*2} = ε_ζ0*3.

The above trend occurs up to ψ(Ω + ζ₁), but the function ψ|_{Ω + ζ1} cannot equal ζ₁ for any ordinal in its domain, nor can iterated exponentiation generate this value. Thus, ψ(Ω + ζ₁) = ζ₁. The next problem occurs when one reaches ψ(Ω + ζ₁), as the set C(Ω + ζ₁) has the operation ψ|_{Ω + ζ1 + 1}, which gives ζ₁, but only for the input Ω + ζ₁, and this input cannot be constructed with other operations to plug into the function. Thus, ψ(Ω + ζ₁) = ζ₁. Hence the function is stuck once again, with ψ(Ω + α) being equal to ζ₁ for α greater than or equal to ζ₁, but only up to a certain point.

Again, Ω bails us out, or, more precisely, Ω*2. Though ψ(Ω*2) still is ζ₁, Ω*2 can be constructed easily from S, and the set C(Ω*2 + 1) has available the operation ψ|_{Ω*2 + 1}, which has Ω*2 in its domain, and can produce ζ₁. Through similar logic as above, ψ(Ω*2 + 1) = ε_{ζ1 + 1}. The general idea continues, with each ψ(Ω*(1 + α) + 1) transcending another ζ ordinal, and yielding ε_{ζα + 1} (if this formula is unclear, try substituting 0 and 1 for α, which give known values, and serve as examples).

As it turns out, this repetition of multiples of Ω "unsticking" the function continues all the way up to ψ(Ω*η₀), with η₀ being the first fixed point of
α → ζ_α. ψ(Ω*η₀) is equal to η₀, as finite iterations of α → ζ_α from 0 give ordinals strictly less then this value. However, ψ(Ω*η₀ + 1) is also η₀, and the function is stuck again, this time all the way until ψ(Ω²), with ψ(Ω² + 1) equal to ε_{η0 + 1}, the first epsilon ordinal greater than η₀. In fact, further powers of Ω have ψ values corresponding roughly to Veblen functions of two arguments, up to
ψ(Ω^Γ₀) = ψ(Ω^Ω) = Γ₀, with the function stuck at Γ₀ for all ψ(Ω^α) for Γ₀ ≤ α ≤ Ω. ψ(Ω^Ω) is then the same as φ(0,0,1) = Γ₀. Multiplying by Ω corresponds to raising the second argument of the Veblen function, and multiplying the exponent of Ω by Ω raises the third argument. For example, ψ(Ω^{Ω + 1}) is
φ(0,0,2), or Γ₁. More values include:

ψ(Ω^Ω2) = φ(0,0,0,1), or the Ackermann ordinal, ψ(Ω^Ω3) = φ(0,0,0,0,1), and so on, with each ψ(Ω^Ωα) equal to the smallest ordinal requiring α + 2 arguments to represent. Alternatively, each of these is the supremum of all ordinals requiring at most α + 1 arguments to represent. However, the ordinal collapsing function has only yielded ordinals expressible as Veblen functions of finite arguments. Even higher countable ordinals accessible through this function are discussed in the next post.

Sources: http://www.ams.org/journals/tran/1908-009-03/S0002-9947-1908-1500814-9/S0002-9947-1908-1500814-9.pdf, Ordinal Collapsing Function - Wikipedia

Infinity: Larger Countable Ordinals

This is the ninth post of the Infinity Series. The first is found here. For all posts, see the Infinity Series Portal.

Over the course of the previous post, a plethora of infinite ordinals were introduced, all of which were, somewhat surprisingly, countable. We concluded with the epsilon sequence, a series of ordinals α for which ω^α = α, where ω is the set of all finite ordinals, and therefore the smallest infinite ordinal.

It was also discussed that any epsilon sequence member of countable index was itself countable. Therefore, ε_ε0, ε_ε1, ε_εω, and so on, are countable.

Since ε_ε0 is countable, the epsilon ordinal with this index, namely ε_εε0, is also countable, and one can continue this recursive process indefinitely. By doing this, one can construct the set {ε₀,ε_ε0,ε_εε0,...}, with each member of the set having a finite number of "ε's". Since there is one and only one member of this set for every positive natural number, it is countable, and again has a countable supremum. This ordinal is sometimes called ζ₀ (zeta-naught), and is also defined as the smallest fixed point of the function on ordinals which carries each ordinal α to ε_α. Hence ε_ζ0 = ζ₀.

Ordinals accessed in this way, such as ε₀ and ζ₀ are values of what are called the Veblen functions, which are functions that generate fixed points of given other functions. In this case, ε₀ is a value of the Veblen function on α → ω^α and ζ₀ a value of the Veblen function on α → ε_α.

Of course, ζ₀ is only the smallest fixed point of the second Veblen function, and is certainly not the end of countable ordinals. ζ₀ + 1, ζ₀ + 2, ζ₀*2, ζ₀^ω and other normal operations on ζ₀ can be defined, eventually leading one to the ordinal ε_{ζ0 + 1}, which, by the definition of the epsilon sequence is the limit of the sequence ε_ζ0, ε_ζ0^ε_ζ0, and so on. However, ε_ζ0 is simply equal to ζ₀, so

ε_{ζ0 + 1} = sup{ζ₀,ζ₀^ζ₀,ζ₀^ζ₀ζ₀,...,ζ₀↑↑n,...}.

Hence this latest ordinal is countable, as are ε_{ζ0 + 2}, ε_ζ0*ε0, and others, eventually leading up to ε_{εζ0 + 1}. Being countable, the epsilon ordinal of this index is as well, in addition to any subsequent iterations.

Thus, one can define the countable ordinal sup{ζ₀ + 1,ε_{ζ0 + 1},ε_{εζ0 + 1},ε_{εεζ0 + 1},...}. In the limit, this is clearly another fixed point of the second Veblen function, but it is greater than ζ₀, as it incorporates ζ₀ + 1 into its definition. It is then the second fixed point of α → ε_α, and is denoted ζ₁. Continuing in this manner, ζ₂ = sup{ζ₁ + 1,ε_{ζ1 + 1},ε_{εζ1 + 1},...}, where ζ₂ is again a fixed point of the above function, i.e. ε_ζ2 = ζ₂. Repeating this process, one obtains ζ_α for any finite α, and, in the limit of these, ζ_ω. For the same reasons as the epsilons, any zeta ordinal of countable index is countable. We then have the countable ordinals ζ_ζ0, ζ_ζζ0, etc., culminating in a new ordinal, namely the smallest fixed point of the function α → ζ_α, and the smallest value of the Veblen function on this mapping.

Although this ordinal could be written η₀ (eta-naught), it becomes useful to have a more standard notation for Veblen functions. To do this, first denote the function α → ω^α as φ₀. Then, for example, φ₀(1) = ω¹ = ω, and φ₀(3) = ω³. Moving on, the function φ₁ is defined as the Veblen function on φ₀, and therefore "lists" its fixed points. φ₁(0) then means "the first fixed point of α → ω^α", which we know to be equal to ε₀. φ₁(1) is the second fixed point of φ₀, which is ε₁. It is clear from the definition of the epsilon sequence that φ₁(α) = ε_α. To find subsequent Veblen functions, one uses the recursive scheme φ_β' (The Veblen function indexed by the successor of β) = "the function that lists the fixed points of φ_β". This series of functions is known as the Veblen hierarchy. Therefore, φ₂ lists the fixed points of φ₁, and is equivalent to the function α → ζ_α. Similarly, φ₃(0) is the first fixed point of φ₂, namely what we briefly referred to as η₀.

Any function of the Veblen hierarchy has a domain of the ordinal numbers, with countable arguments generating countable outputs. Using the recursive formula above, the functions φ₄, φ₅, etc., can be constructed. Another important fact about Veblen functions is that each value taken by one of these functions is taken by all previous functions. In formula form, where α, β, γ, and δ and ordinals,

For all ordinals φ_β(α), there exists an ordinal γ for all δ < β such that φ_β(α) = φ_δ(γ)

In other words, each value taken by a function in the Veblen hierarchy is also a fixed point of all previous ones. For example, ζ₀ is also a fixed point of α → ω^α, as well as of α → ε_α. Using this fact, φ_β(α) can be defined in the case that β is a limit ordinal:

If β is a limit ordinal, then φ_β lists the common fixed points of all the functions φ_δ for all δ < β. For example, φ_ω(0) is the smallest ordinal that is a fixed point of all the functions φ₀, φ₁, φ₂, etc. One can further define the ordinals φ_ε0(0), φ_ζ0(0), and even

φ_φω(0)(0), φ_φφω(0)(0)(0), and so on.

All ordinals accessible through the operations of addition, multiplication, exponentiation and the Veblen hierarchy have now been described. Next, we define the ordinal that is the limit of the above ordinals, i.e. the smallest ordinal such that φ_α(0) = α. It is also described as the first fixed point of
α → φ_α(0). This ordinal transcends the entire Veblen hierarchy, and it is sometimes called the Feferman-Schutte ordinal. It is written Γ₀.

Γ₀ has many interesting properties. First and foremost, it is countable, being constructed using Veblen ordinals of countable argument. Also, it is considered by many to be what is called "impredicative", essentially meaning here that it cannot be defined without reference to the totality of the system of ordinals. This is because, unlike all previous ordinals, it depends on a "second-order" definition, namely it is dependent on the Veblen hierarchy, each member of which is a function. In this way, it is constructed through a sort of "meta"-function, i.e. a function on functions. Since functions such as those of the Veblen hierarchy have domains encompassing the system of ordinal numbers, Γ₀ makes use of this entire system in its construction, and references all ordinal numbers, including itself. The fundamental point is that the definition that led to Γ₀ was of a different nature than all those previously, and is the first of a different class of ordinals, the impredicative ordinals.

Also, by definition of its construction, it is a fixed point of all Veblen functions φ_β, where β < Γ₀. Hence ω^Γ₀, ε_Γ0, ζ_Γ0, etc. are all equal to Γ₀. We use this fact to confirm that

sup(Γ₀ + 1,ω^{Γ₀ + 1},ω^{ωΓ₀ + 1},..} = ε_{Γ0 + 1} > Γ₀.

Similarly, sup(Γ₀ + 1,ε_{Γ0 + 1},ε_{εΓ0 + 1},...} = ζ_{Γ0 + 1} > Γ₀.

Further, φ_β(Γ₀ + 1) can be defined for higher ordinals, eventually leading to φ_{φΓ0 + 1(0)}(0). The limit of

φ_{Γ0 + 1}(0), φ_{φΓ0 + 1(0)}(0),...

is then the second fixed point of φ_α = α, and, being greater than Γ₀, it is denoted Γ₁. In the same way, Γ₂, Γ_ω, Γ_Γ0 can be defined. Being limits involving Veblen functions, these ordinals are also countable. However, these still does not constitute all of the countable ordinals. The trek forward is continued in the next post.

Sources: http://folk.uio.no/herman/incompleteness.pdf, Large Countable Ordinals-Wikipedia

Infinity: Countable Ordinals

This is the eighth post of the Infinity Series. For the first post, see here. For all posts, see the Infinity Series Portal.

In the previous posts (here and here), ordinal numbers and basic operations concerning them were introduced. Now, using exponentiation, the ordinal ω² can be defined. By the definition of exponentiation,

ω² = ω*ω,

which is greater than any ordinal ω*n, for all natural numbers n, and is therefore greater than ω. ω² as a set is written {0,1,2,...,ω,ω + 1,...,ω*2,ω*2 + 1,...,ω*3,...,ω*n,...}.

In contrast, consider 2^ω, which is the limit of 2ⁿ over natural numbers. Clearly, this is just the limit of a sequence of increasing natural numbers, namely ω. Therefore, 2^ω = ω. In the same way, one can define further ordinals of the form ωⁿ, and confirm that n^ω = ω for all natural numbers n.

To prove that ordinals such as ωⁿ are countable, one must use the following theorem:

The union of countably many countable sets is countable. (1)

Besides being a mouthful, this theorem is invaluable in confirming the countability of sets. To see how the theorem works, consider a countable set of countable sets {A,B,C...} (each of A, B, C, etc. is a countable set). Since this set is countable, the sets in this set can be labeled with natural numbers. Each set can then be identified with, and written, as a number, (for clarity, the numbers will be in boldface), with A = 1, B = 2, C = 3, and so on. Since each of these sets individually is countable, the elements of each one can be labeled 1, 2, 3 and so on. For example, the element labeled "1" in set A will be denoted 1₁. We now construct the following function for labeling the elements of all of the above sets (the first ten values, corresponding to the natural numbers 1-10, are shown)

1→ 1₁, 2→ 1₂, 3→ 2₁, 4→ 1₃, 5→ 2₂, 6→ 3₁, 7→ 1₄, 8→ 2₃, 9→ 3₂, 10→ 4₁,...

It is easily calculated that the general member m of any set n can be found by the following formula:

((m + n)(m + n - 1))/2 - n + 1→ n_m

This formula may seem rather complicated, but the important fact is that for any element of any set in {A,B,C...}, there is exactly one natural number that serves as its "label", and the above sequence is a one-to-one correspondence.

We first observe that ω² is countable, as it is a union of all sets of the form {ω*n + 0, ω*n + 1,...} for natural n. Each of these is countable, as every set of the above form can be put into a one-to-one correspondence with the natural numbers simply by dropping the ω term from each member, and the set of all these sets is also countable, as there is one for each natural number n. (1) is therefore applicable, and ω² is countable.

Similarly, one can define a set of sets of the form {(ω²)*n,(ω²)*n + 1,...,(ω²)*n + ω,(ω²)*n + ω + 1,...,(ω²)*n + ω*2,...,(ω²)*n + ω*3,...,(ω²)*n + ω*m,...}. If n = 0, then the set above reduces to ω². For all other values of n, the set can be put into a one-to-one correspondence with ω² by dropping the first term. The union of all these sets, with the set of sets being, of course, countable, is ω³.

The above outlines a recursive scheme that confirms that all ωⁿ are countable. The countability of each power of ω allows one to apply (1) to the next power. Therefore, if one repeats this process indefinitely over all natural numbers, the limit is the ordinal ω^ω, which is again countable, being a limit of countably many countable sets. The property of such a limit being countable is very important to ordinal numbers and will be used often. It is a consequence of the theorem proved above, and will be referred to by (2).

This fact seems at odds with what was previously discussed about cardinal numbers, with 2^ℵ₀ being equal to the cardinality of the continuum, which describes a property of uncountable sets. It seems much "easier" in a sense to access uncountable cardinals than it is to describe uncountable ordinals, and it will soon be described just how difficult the latter is.

Continuing from ω^ω, one can use a similar recursive scheme to show that ω^ω2, ω^ω3, and so on, are countable. Remarkably, under the same limiting process, combined with recursion, ω^ωω, ω^ωωω, and any larger finite power towers of ω are countable.

At this point, no larger ordinals can be described through the operations of addition, multiplication, and exponentiation directly in terms of ω. We therefore define the ordinal ε₀ (epsilon-nought) as the limit of the sequence ω, ω^ω, ω^ωω, ω^ωωω,..., or, more formally, as the smallest ordinal α such that ω^α = α. In other words, this ordinal is so large that the two quantities ω^ε₀ and ε₀ are indistinguishable. Mathematically, ε₀ is also the smallest fixed point of the map α → ω^α, i.e. is left unchanged when it is applied.

Remarkably, ε₀, despite being extremely large, is still countable! It is the limit of the set {ω, ω^ω, ω^ωω, ω^ωωω,...,ω↑↑n,...}, where ↑↑ represents the hyper4 operator, or iterated exponentiation, which in this case a shorthand for writing "n ω's in the power tower". Since, in this set, n takes only natural number values, the set itself is countable, and ε₀ is the limit of countably many countable ordinals, and, by (2), is itself countable.

Of course, ordinals do not end here. One can go on to define ε₀ + 1, ε₀*2, ε₀^ω and others. For the same reasons as the corresponding expressions involving ω, these are all countable. One can go to on to define the limit of the set {ε₀,ε₀^ε₀,ε₀^ε₀ε₀,...,ε₀↑↑n,...} as a new ordinal, ε₁. Reviewing the process through which this ordinal was created, one can see that it is a limit of a set of limit ordinals, each of which was itself a limit of a sequence of ordinals! Despite being so far removed from our original ω, it is again countable, by the same logic used for ε₀. Also, this is the second fixed point of the map mentioned above, as all ordinals between ε₀ and ε₁ are not equal to themselves under
α→ ω^α, e.g. ω^{ε₀ + 1} = ω^ε₀*ω = ε₀*ω ≠ ε₀ + 1.

Continuing even further, one can define ε_α for any natural number α. The formula below shows how this is done, with the symbol "sup{}", representing the supremum, or least ordinal greater than or equal to every member, of a set. Essentially, the notation "supremum of a set" is interchangeable with "limit of a sequence", but the former is easier to write. The formula for ε_α is recursive, using succession to define each member of the epsilon sequence.

ε_α' = sup{ε_α,ε_α^ε_α,ε_α^ε_αε_α,...,ε_α↑↑n,...}

Since each set in the above equation is countable, and each ordinal involved is countable, the members of the epsilon sequence for finite α are countable. Of course, one can then construct a set of all epsilon ordinals of natural number index α, i.e. {ε₀,ε₁,ε₂,...,ε_α,...}. This set is countable, as well as all of its members, and it therefore has a countable supremum, which can be defined as ε_ω. Subsequently,
ε_{ω + 1}, ε_{ω + 2},...,ε_ω*2, and others can be defined. Each of these ordinals, if the subscript of ε is limit ordinal, is simply the supremum of all previous members of the epsilon sequence. Otherwise, the subscript is the successor to some other ordinal, and the formula that was used for ε ordinals of finite indices can be applied.

An important property of the epsilon sequence is that any ordinal in the sequence with a countable index is also countable. This is because, for such an ordinal, the set of all previous members of the epsilon sequence is countable. The reason for this is that they can be easily put into a one-to-one correspondence with a countable set, simply by dropping the "ε", and considering only their indices. For example, ε_ω*2 is the supremum of the set
A = {ε₀,ε₁,ε₂,...,ε_ω,ε_{ω + 1},...}. A bijection can be constructed from this set to ω*2, namely the one assigning ε₀→0, ε₁→1, etc., confirming the countability of A and the applicability of (2).

Among the epsilon ordinals of countable index are ε_ω^ω, ε_ω^ωω, and even ε_ε0. But where can one go from here? This is still just the beginning of infinite ordinals. More are explored in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes, http://en.wikipedia.org/wiki/Epsilon_nought, Large Numbers at MROB

Infinity: Operations on Ordinals

This is the seventh post of the Infinity Series. For the first post, see here. For all posts, see the Infinity Series Portal.

In the previous post, the concept of ordinal numbers was introduced, as well as the idea of succession. Now, one can build the idea of ordinal addition by considering iterated succession. In the definition of ordinal addition, a recursive scheme is used, with succession as each step in the addition process.

The definition of addition is as follows for two (finite) ordinals α and β:
α + 0 = α
α + β' = (α + β)'

This procedure works for any finite ordinals (natural numbers). For example, the sum of 4 and 3 is

4+3 = 4+2' = (4+2)' = (4+1')' = ((4+1)')' = ((4+0')')' = (((4+0)')')') = (((4)')')' = ((4')')' = (5')' = 6' = 7

However, when attempting to evaluate the addition of infinite ordinals, one encounters a snag. Consider the ordinal ω, which is the set of all finite ordinals (natural numbers). For example, one cannot evaluate 1 + ω using the previous rule, as ω is not the successor of any ordinal, as it is the limit of the natural numbers. Ordinals which cannot be expressed as successors of others are accordingly known as limit ordinals.

The succession scheme above leads to all the familiar properties of addition for natural numbers, commutativity, associativity, and the like. However, the addition of infinite ordinals does not possess all of these properties. Consider the sum ω+1. The succession-based addition scheme works here, as

ω + 1 = ω' = ω∪{ω},

or, in more familiar set notation, the set of ordinals

ω + 1 = {0,1,2,3...,ω}, which is not equal to ω, as it has ω as a member, and no ordinal has itself as a member, only all previous ordinals. Therefore, unlike in cardinal addition, where adding any natural number to ℵ₀ leaves it unchanged, ω + 1 is distinct from ω.

However, now consider 1 + ω. Although this expression cannot be evaluated using the previous method, one can intuitively think of the addition as the limit over natural numbers n of

1 + n,

which simply is, as n increases without bound among the natural numbers, ω. This is because the limit of a sequence of natural numbers can never exceed ω.

1 + ω = ω ≠ ω + 1

Paradoxically, these ordinals are different, but have the same cardinalities, namely ℵ₀. To reinforce this fact, one can readily identify a one-to-one function f from ω + 1 to ω defined in the following way:

f(α) = α + 1, if α ≠ ω and f(α) = 0, if α = ω

Therefore, f(0) = 1, f(1) = 2, and so on, with each natural number being mapped to another, clearly within the range, ω, and the final member of ω + 1, ω, being mapped to 0. The methods used here are similar to those that were earlier used to demonstrate cardinal equalities.

In a similar fashion, 2 + ω = ω, and for that matter n + ω = ω for any natural number n. Also, ω + n > ω for any n ≥ 1, being instead equal to the set {0,1,2,3...,ω,ω + 1,ω + 2,...,ω + n - 1}

Ordinal multiplication can now be introduced as iterated addition, with

α*0 = 0
α*β' = α*β + α

Trivially, by this definition, ω*1 = ω*0 + ω = ω. Also, 1*ω is the same as the operation "+1" iterated for each natural number, i.e. an infinite number of times. In the same way as 1 + ω, 1*ω = ω.

However, what about ω*2? By the definition of multiplication it is equal to ω + ω. Clearly this is greater than ω and is equal to the set of ordinals {0,1,2,...,ω,ω + 1,ω + 2,...}. However, 2*ω is the limit of 2*n as n increases through the natural numbers. In the same way as 1 + ω, 2*ω = ω, hence ordinal multiplication is not commutative.

The above cases can be generalized to any ordinal of the form ω*m + n. Such an ordinal is strictly greater than ω, but is countable, i.e. there exists a bijection from this set to ω. Such a function is easily constructible along the lines of the linear function y = mx + n. To illustrate this process, consider the example ω*2 + 3 = {0,1,2,...,ω,ω + 1,ω + 2,...,ω*2,ω*2 + 1,ω*2 + 2,ω*2 + 3}. The function from this ordinal to ω is constructed as follows:

0 -> 3, 1 -> 5, 2 -> 7,... (finite ordinals α transform to α*2 + 3)
ω -> 4, ω + 1 -> 6, ω + 2 -> 8,... (ordinals of the form ω + α, for finite α, transform to α*2 + 4)
ω*2 -> 0, ω*2 + 1 -> 1, ω*2 + 2 -> 2

Clearly, this assigns a unique natural number (member of ω) to each element of the set ω*2 + 3, and the latter set is therefore countable, with a cardinality of ℵ₀. All ordinals of the form ω*m + n have this same cardinality.

Finally, to extend the system of infinite ordinals further, one must introduce ordinal exponentiation, defined as follows:

α⁰ = 1
α^β' = (α^β)*α

For limit ordinals, the same limit argument used before will apply. Using these three operations, together with the idea of a limit, one can define many other infinite countable ordinals, a topic explored in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes, http://en.wikipedia.org/wiki/Ordinal_addition

Infinity: Ordinal Numbers

This is the sixth post in the Infinity Series, the first of which is found here. For all posts, see the Infinity Series Portal.

In order to further explore the concept of infinity, one must temporarily move away from the concept of the cardinal number, and consider yet another type of number: the ordinal. The system of ordinal numbers is again entwined in set theory, and, unlike cardinal numbers, they can be expressed as sets. It is also important to know that any cardinal number can alternatively describe a family of sets, i.e. all of the sets that have that cardinality. For example, the cardinal number 3 not only describes a number of members that a set can have, but also represents the family of all sets with three members.

Formally, ordinal numbers are very similar to cardinal numbers in that, in finite situations, they represent properties of classes of sets. The property that an ordinal number represents is known as order type. However, the class of sets whose order type is described by an ordinal number much more specific than that of a cardinal number. To understand the type of set that has an order type can represent, one must first understand the concept of a well-ordered set.

A well-ordered set is a set that can be well-ordered by a relation. A relation, in this case, is just a quantity that connects pairs of elements. A good example is the relation "<" or "less than". To understand well-ordering, observe the example below.

Consider the set S = {2,5,7}, and the relation R = <
If "<" is restricted to the set S, it simply means that the two elements of each ordered pair of the relation must come from S, i.e. chosen from 2, 5, or 7. Of the six possible ordered pairs, (2,5), (2,7), (5,7), (5,2), (7,2), and (7,5), three are members of the relation <, namely (2,5), (2,7), and (5,7). This is because 2<5, 2<7, and 5<7. Obviously, the remaining pairs are not, as 5 is not less than 2, and so on.

In this case, "<" well-orders S, meaning that each (non-empty) subset of S has a "minimal" element. For the relation "<", the "minimal" element of a subset is simply its smallest member. Since it is easy to find the smallest number of any subset of S, it is a well-ordered set.

In contrast, consider the set of all whole numbers N = {1,2,3...}. The above relation "<" does well-order the set, because, for any subset, one can state the smallest element. However, this does not hold with the operation "greater than" or ">". For example, if the subset N' is the set of natural numbers greater than 3, i.e. {4,5,6...}, then there is no "minimal" element under the relation ">", as there is no element in the set that is greater than all the others. However, overall, the set is still "well-ordered", because there is at least one relation that does satisfy the needed conditions.

Now, returning to the class of sets a certain order type, consider all the well-ordered sets that can be put into one-to-one correspondence (i.e. all the well-ordered sets with a given cardinality). However, this correspondence is of a rather special type, matching up the "minimal" elements with each other, followed by the "next-to-minimal" elements, and so on. Every class of sets for which all the members are connected is an equivalence class, and all sets in this class have an identical order type, which is a certain ordinal number.

For instance, the above set S = {2,5,7} under "<", and the set T = {b,c,d} under the relation that will be defined as "alphabet" (which puts alphabet in order), can be related by a correspondence. The minimal element of set S under "<" is clearly 2, and the minimum of T under "alphabet" is b, with b being the letter in the set closest to the beginning of the alphabet. Since the other elements can be paired in a similar way, these two sets are therefore members of an equivalence class and are of the same order type (intuitively, they are this order type because they each have three elements).

However, for each equivalence class, it is convenient to chose one, and only one set to be representative of the entire class, and thus, the ordinal. The first such set is the empty set, Ø, having no elements and being the only member of its equivalence class. We identify this set with the ordinal number "0". Therefore,

0 = Ø = {}

Hence forth, the representative set of each equivalence class is defined as the set containing all of the previous representative sets. For example, the successor of 0 is denoted "1", or the second ordinal number, and is defined as

1 = {Ø}

Note that this set is not the empty set, but rather the set containing only the empty set. It is obvious that this set can be well-ordered, as, trivially, there is only one element to order. It is equally clear that this set is representative of the class of sets with a single element and that it can be put in a one-to-one correspondence with each set in that class. Continuing the pattern of each representative set containing all of those previously, we have

2 = {Ø, {Ø}},
3 = {Ø, {Ø}, {Ø, {Ø}}},
and so on. Note that "2", has 0 and 1 as members, and "3" has 0, 1, and 2 as members.

Henceforth, "ordinal number" will refer to a set of this type, and 0, 1, 2, 3,... will refer to ordinal numbers unless otherwise specified. These ordinal numbers are well-ordered by the membership relation, or the relation set up between two sets with the second containing the first. In other words, each element of an ordinal number set is a member of all subsequent elements in the set. For example,

4 = {Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}}

In this set, each member is a member of each subsequent member, namely, Ø, being the first element of 4, is a member of {Ø}, {Ø, {Ø}}, and {Ø}, {Ø, {Ø}}}, which, of course, are just the ordinal numbers 1, 2, and 3. The minimal element for each ordinal number is Ø.

It is clear that one can go on to define any natural number as a set of this type, namely as the set of all previous ordinals. As with cardinal numbers, the first infinite ordinal number corresponds to the set of all natural numbers. This ordinal is denoted ω, and has every (ordinal) natural number as a member. It is clear that this set can be put in a one-to-one correspondence with the set of "regular" natural numbers, and it therefore has a cardinality of aleph-zero. However, the world of infinite ordinals is very different than that of infinite cardinals.

One crucial difference is the idea of succession in ordinals. From any ordinal α (greek letters are often used for ordinal variables), there is a successor to α, denoted α', which is defined as the next ordinal after α. Formally, α' is the smallest ordinal which has α as a member. Furthermore, α' can be constructed using the formula

α' = α ∪ {α}

where ∪ is the symbol for a union of sets. The concept of union entails combining all the members of two sets into one, and deleting any duplicates. For instance,

{1,4,6} ∪ {3,6,13} = {1,4,6,3,6,13} => {1,4,6,3,13}

Returning to the succession formula above, note the distinction between α and {α}. The first is an ordinal, but the second is not, being rather a set containing a single ordinal, α, as its only member. To more easily visualize this process, consider the simplest example:

0 = Ø
0' = Ø ∪ {Ø}

Now, the union of the empty set with any other set is simply the other set, as the empty set contributes no members to the result. Therefore,

0' = Ø ∪ {Ø} = {Ø},

the final term of which is, in fact, the ordinal 1! Though ordinal addition has not been defined, we can observe that the succession operation, in a more general case, identifies with the process of adding 1 (0+1=1 and 0'=1, etc.). The role that succession plays in infinite ordinals, as well as in operations on ordinals, is considered in the next post.

Sources: Axiomatic Set Theory by Patrick Suppes

Infinity: Uncountable Sets

This is the fifth post of the Infinity Series, beginning here. For all posts, see the Infinity Series Portal.

In previous posts, the idea of an "uncountable set" has arisen, namely a set that has a cardinality greater than that of the natural numbers. We have already revealed that the sets of real numbers and complex numbers are uncountable, specifically having a cardinality that is two to the power of aleph-zero, the cardinality of the natural numbers. However, there are other sets which have this cardinality, as well as sets with one greater than this.

First, sets with the cardinality of the continuum will be listed. The sets of real and complex numbers fit into this category, along with any interval of either of them. For example, the set of real numbers between 1 and 5 (inclusive or exclusive) will have the cardinality of the continuum.

A somewhat more interesting case is the Cantor set, a famous entity in mathematics. It is obtained geometrically by beginning with a solid line segment, (mathematically, this segment is the real numbers on [0,1]) and on each step removing the middle third of every existing line segment. This process is illustrated below.



The first seven steps in producing the Cantor Set. This process is repeated infinitely many times. It appears that the entire original line segment will eventually be removed after an infinite number of the above steps, and this is, in a way, true. During the first step 1/3 of the total bar is removed, followed by 1/9 of the total for each remaining segment on the second step, then 1/27 of the total for each remaining part on the third step, and so on. The sum of these removals is 1/3+2/9+4/27+... since there are 2^n segments on the nth step (the amount removed on second step equals 2*1/9=2/9, and on the third, 4*1/27=4/27). The above sequence sums, in the limit as n increases without bound, to 1. In other words, 100% of the original segment is taken away as the Cantor Set is constructed.

Despite the apparent paradox, it is clear that for any segment remaining at any step of the above process, it will have two endpoints that are untouched even after an infinite number of steps. This is because only the middle of all such segments are removed. The remaining points, which all become endpoints at some step, are the points of the Cantor Set. For example, the points 0 and 1 are never removed, along with 1/3, 2/3, 1/9, 2/9, 7/9, 8/9 and many others. The cardinality of this set can be discovered by expressing all its points in base-3 (ternary) decimal notation. In it, 1/3=.1=.02222..., 2/3=.2=.12222..., 1=.22222..., 7/9=.20222..., etc. Many of these numbers have two forms, i.e. 1/3=.1=.0222..., but it can be shown that the Cantor Set contains only points whose base-3 decimal representation has at least one form (out of the two) that consists of only 2's and 0's (a more full discussion is found here). If one took all of these decimals and changed all of the 2's into 1's, a set of binary sequences would be produced. The Cantor set has all base-3 points consisting of only 2's and 0's, but after the function, which is clearly a bijection, it is now the set of all binary sequences, which has previously been shown to have the cardinality of the continuum. The Cantor Set does as well.

Mathematically, this is remarkable. Even though the Cantor Set is an infinitesimal fraction of the line segment [0,1], it still has the cardinality of the continuum. Since no two points of the final Cantor Set are "adjacent" to each other, the Cantor Set is defined to have the property of being nowhere dense. Simply put, this means that any interval containing two points of the Cantor Set does not necessarily contain a third. In contrast, there are an infinite number of rational numbers between any two one could chose, and the set of rational numbers is therefore dense. The fact that such a "nowhere dense" set can have the cardinality of the continuum is also incredible, because all of the discrete sets (natural numbers, integers, etc.) that we have examined have not had this cardinality. These are clearly nowhere dense, as there are real numbers between any two natural numbers, or any two integers.

Another very interesting case is the cardinality of the set of continuous functions on the real numbers. To find this cardinality, it is useful to use a proof of trichotomous exclusion. Such a proof confirms that a set must have a cardinality greater than or equal to that of a certain set, and then proves that it must simultaneously satisfy the condition of having a cardinality less than or equal to that of the same set. Since one quantity cannot be less than and greater than another, the cardinality of the two sets must be equal.

To go about the above proof, it is useful to reevaluate the definition of a continuous function. The "local" definition is of most use here. It states that for any value x on a continuous function, there exists a sufficiently small ε such that f(x+ε) approximates f(x) to an arbitrary accuracy σ. In addition, as ε goes to 0, σ will as well, as point Q becomes a better and better approximation to point P. This is all summarized in the figure below.



Compare the above to the discontinuous function below, where the open circle on the curve represents a discontinuity, the true function value f(x) being located at point P. Even with ε miniscule, the approximation to f(x) never reaches the desired accuracy of σ.



Having defined what it means to be continuous, it is now possible to find the cardinality of the set of continuous functions. The key concept is that knowing the value of a continuous function on all rational numbers is enough to determine it uniquely, i.e. to find its value at any real number.

To see this, consider the value x from above to be a certain real number (for our purpose, make it irrational). This number can be approximated to an arbitrarily high accuracy with a rational number, e.g. π≈3.14159=314159/10000, etc. and therefore ε can be made as small as desired. In the limit as ε goes to 0, the approximation to f(x) becomes exact, and the function value is uniquely determined. Therefore, the knowledge of the value of a continuous function over the rational numbers is enough to determine it.

The main idea is that the above shows that the any specific continuous function needs no more than a countable set of real numbers to define it. The cardinality of the set of all continuous functions is therefore either equal to or less than that of the set of the countable sets of real numbers, or the power set of real numbers, (a power set is the set of all combinations of elements of a given set, discussed in an earlier post) whose cardinality is 2 to the power of the cardinality of all countable sets: aleph-zero. The set of continuous functions therefore has no more than the cardinality of the continuum.

To confirm that this is the cardinality, we must still prove that the set of continuous functions is uncountable. There is a very simple way of doing this. Take a subset of the continuous functions, the constant functions, for which f(x)=k, k being a real number. Clearly, if one defines a set of all constant functions, including every possibility of k, the set will be equivalent in cardinality to the real numbers: the cardinality of the continuum. However, the constant functions are a subset of all continuous functions, the true cardinality must be equal to or greater than this. Since we have already confirmed that it is no greater, and now it is known that the cardinality of the set is no less than that of the real numbers, it follows that the two must be equal.

In contrast, discontinuous functions cannot be pinned down without their value at each and every real number. For example, the discontinuous (piecewise) function that defines f(x) to be equal to 1 for all x except π, and at π for the value to be 12, no degree of accuracy in the rational numbers can confirm that f(π) will equal twelve. The best approximations will simply yield f(π)=1, as they "expect" the function to be continuous at π. More generally, some discontinuous function could potentially have a jump at any or every real number. Therefore, it takes a set of real numbers to uniquely determine such a function.

The total set of functions (including both continuous and discontinuous) on the real numbers is then the power set of the real numbers, with a cardinality greater than any yet discussed. It is 2 to the power of the cardinality of the continuum, which is also known as beth-two, the symbol of which is illustrated below.



This is the third member of what is called the beth sequence. Beth-zero is equal to aleph-zero, and each subsequent element of the sequence is defined recursively as 2 to the power of the previous one. Beth-one is equal to 2 to the power of aleph-zero, or the cardinality of the continuum, and so on. Equivalently, each element is the cardinality of the power set of the previous element. The distinctions between the aleph series and the beth series are revealed in a later post. The next post is on a new type of number.

Sources: http://en.wikipedia.org/wiki/Cantor_set, etc.

Infinity: Operations on Cardinals

Before reading this post, make sure you have read the first three parts of the Infinity Series, the first of which is found here. For all posts, see the Infinity Series Portal.

Having found the mathematical relationship between aleph-zero and the cardinality of the continuum, one wonders if it is possible to perform other operations with infinity cardinals, and whether these equations create any numbers not yet discussed. To start, take a simple addition from cardinal arithmetic:

(1)

What exactly does this equation mean? We are asked to "add" two quantities, one of which is an infinite cardinal, and one is a simple number. That it is possible to evaluate the sum (1) follows from the fact that aleph-zero and 1 are both cardinal numbers. Since they are of the same number system, they are "compatible" in a way, and can be combined by the use of sets. We have already proved (1) in the first post of the series, but let us recap. It has been discussed that adding the element 0 to the set of natural numbers does not change its cardinality, since the function y=x-1 from one set to the other is a bijection. In set notation, with vertical lines representing cardinality: |{0}|+|{1,2,3...}|=|{0,1,2,3...}| Note that if one replaces the values in this equation with the actual cardinalities, one obtains the equation (1) above! The equation in simple sets that has the same meaning as a cardinal equation will henceforth be known as the Corresponding Set Equality (CSE).

The generalization of (1) for any natural number n is

(2)

This can also be transformed into a CSE, since any subset of integers also has cardinality aleph-zero. The the set {-n+1,-n+2,...-2,-1,0} clearly has n elements, and can be added to the natural numbers to form the CSE, namely: |{-n+1,-n+2,...-2,-1,0}|+|{1,2,3...}|=|{-n+1,-n+2,...-2,-1,0,1,2,3...}|. By evaluating the cardinalities on both sides, one obtains equation (2). It is easy to continue on to other arithmetic operations, such as multiplication:

(3)

This particular equation also has a CSE. First consider the set of integers. It is clear that it can be split into two components, both of which have a cardinality of aleph-zero, namely the whole numbers: {0,1,2,3...} and the negative integers: {...-3,-2,-1} However, when these two sets are combined, the set of integers results, which we already know has cardinality aleph-zero as well. The CSE here is |{0,1,2,3...}|+|{-1,-2,-3...}|=|{...-3,-2,-1,0,1,2,3...}|. All three of the cardinalities are evaluated as aleph-zero, and (3) results. Now we shall prove the general multiplication result

(4)

for any natural number n. We have already determined that the rational numbers, and any infinite subset of them have cardinality aleph-zero. Consider the set {a/n,1+(a/n),2+(a/n),...}. This is simply the set of natural numbers with the rational number a/n added to each term. For a constant n, one could consider creating a set for each integral value of a from 0, to n-1, inclusive. This produces n sets of cardinality aleph-zero.

An example will make this more clear. Consider the case with n=3. For a=0, the set produced is simply the whole numbers ({0/3,1+(0/3),2+(0/3)...}={0,1,2...}) For a=1, the set is {1/3,1+(1/3),2+(1/3)...} and for a=2, the set is {2/3,1+(2/3),2+(2/3)...}, all of which have cardinality aleph-zero. The sum of these sets is {0,1/3,2/3,1,1+(1/3),1+(2/3),2...}, or the set of all multiples of 1/3, which also has the same cardinality. We have just proved (4) for n=3. The more general CSE for (4) is |{0/n,1+(0/n),2+(0/n)...}|+|{1/n,1+(1/n),2+(1/n)...}|+
|{2/n,1+(2/n),2+(2/n)...}|+...+|{(n-1)/n,1+((n-1)/n),2+((n-1)/n)...}|=
|{0,1/n,2/n...,1,1+(1/n),1+(2/n),...}|, the final set being the set of multiples of 1/n.

This equation is tedious, but it simply is the division of the set of multiples of 1/n into n parts, all of which have cardinality of aleph-zero. Since the set of multiples on the right hand side of the equation as an equivalent cardinality, this proves (4). Moving on, even the multiplication of two infinite quantities is possible.

(5)

The CSE for this equation follows from the countability of the set of ordered pairs. The set of ordered pairs (x,y) with natural numbers x and y can be split into components by setting a value for x, for example 1, and letting y vary among the natural numbers. For each constant value of x, a set of cardinality aleph-zero is generated, and since there are aleph-zero choices for x, the above result (5) follows. In CSE form, |{(1,1),(1,2),(1,3)...}|+|{(2,1),(2,2),(2,3)...}|+...=[the cardinality of the set of ordered pairs]. Each quantity in the equality has value aleph-zero when evaluated, and since there are as many members on the left side, it follows that the cardinality of the natural numbers, when multiplied by itself, yields the same quantity. This result can too be generalized to any positive integer power:

(6)

Since the case n=2 makes use of ordered pairs, it is natural to assume that higher powers will involve the corresponding ordered n-tuplet. This is correct. There are aleph-zero possibilities for each element of an integral ordered n-tuplet, and each choice of element contributes an aleph-zero to the product. The end result is aleph-zero to the nth power, but since it has already been said that the cardinalities of the sets of ordered n-tuplets for finite n are all aleph-zero, the equality (6) is a direct result.

Summarizing the above, no additions, multiplications, or nth powers, when applied to aleph-zero, change its value. However, it has already been shown that two taken to the power of aleph-zero produces a different infinite cardinal, namely the cardinality of the continuum. But what about a general natural number n taken to the same power, or even aleph-zero taken to the power of itself?

(7)

Remarkably, we find that this quantity is equal to the cardinality of the continuum! This can be derived intuitively from the result (6). Since aleph-zero to the power of n is equal to the cardinality of the set of the ordered n-tuplets, one obtains (7) by letting n increase without bound to aleph-zero, at which point one obtains the cardinality of the set of infinite sequences, which has previously been shown to be greater than aleph-zero, and named the cardinality of the continuum. Any other n taken to the aleph-zero power is also equal to the cardinality of the continuum, as such quantities would clearly be greater than 2 to that power and less than the left side of (7). Since these both have the same value, those of the general case do as well. This is all summarized below.


The next post explores uncountable sets, namely stating what other sets besides the real or complex numbers have a cardinality equal to, or even greater than, the cardinality of the continuum.

Sources: http://en.wikipedia.org/wiki/Power_set