Mountain Math Software

Generalizing Kleene's O to ordinals ≥ ω₁^CK
Paul Budnik
paul@mtnmath.com
Copyright © 2012 Mountain Math Software
All Rights Reserved
Jan 26, 2012

Click here for a PDF version of this paper with better more complete fonts.

Abstract

This paper expands Kleene's notations for recursive ordinals to larger countable ordinals by defining notations for limit ordinals using total recursive functions on nonrecursively enumerable domains such as Kleene's O. This leads to a hierarchy related to that developed with Turing Machine oracles or relative recursion. The recursive functions that define notations for limit ordinals form a typed hierarchy. They are encoded as Turing Machines that identify the type of parameters (labeled by ordinal notations) they accept as inputs and the type of input that can be constructed from them. It is practical to partially implement these recursive functional hierarchies and perform computer experiments as an aid to understanding and intuition. This approach is both based on and compliments an ordinal calculator research tool.

1 Objective mathematics
    1.1 Avoiding the ambiguity of the uncountable
    1.2 Objective mathematics beyond ω₁^CK
2 Kleene's O
3 P an extension of Kleene's O
    3.1 P conventions
    3.2 P definition
    3.3 Summary of rules for P
4 Q an extension of O and P
    4.1 Hierarchies of ordinal notations
    4.2 Q syntax
        4.2.1 Q label (lb) syntax
        4.2.2 Q ordinal (od) syntax
    4.3 Q conventions
    4.4 Ranking labels (lb) in Q
    4.5 Q definition
    4.6 Summary of rules for Q
5 Conclusions
Index

1 Objective mathematics

Kleene's O is part of what I call objective mathematics. O is a set of recursive ordinal notations defined using finite structures and recursive functions. ω₁^CK is the set of all recursive ordinals. The recursive ordinal notations in Kleene's O are constructed using computer programs whose actions mirror the structure of the ordinal. Thus the ordinals represented in O have an objective interpretation in an always finite but possibly potentially infinite universe.

Part of the motivation for generalizing Kleene's O to notations for larger countable ordinals is to help to draw the boundaries of unambiguous mathematics that is physically definable and physically meaningful in an always finite but potentially infinite universe. Many others have attempted to draw related lines in various ways. Section 1.2 discusses the objectivity of creative divergent processes with important properties that can only be defined by quantification over the reals. Even so these properties are objective and important in am always finite but potentially infinite universe.

The Lowenheim-Skolem theorem proves that the uncountable is ambiguous in any finite or r. e. (recursively enumerable) formalization of mathematics. Any effective formal system, that has a model, must have a countable model. Thus, in contrast to much of mathematics[2], uncountable sets cannot be given an unambiguous objective definition by finite beings in a finite universe. The uncountable is meaningful and useful as a reflection of mathematics that has yet to be sufficiently explored to be seen as countable and as describing ways that `true' mathematics can always be expanded. Platonic interpretations that see the uncountable as absolute and open to human intuition are questionable¹.

1.1 Avoiding the ambiguity of the uncountable

"I am convinced that the Continuum Hypothesis is an inherently vague problem that no new axiom will settle in a convincingly definite way². Moreover, I think the Platonistic philosophy of mathematics that is currently claimed to justify set theory and mathematics more generally is thoroughly unsatisfactory and that some other philosophy grounded in inter-subjective human conceptions will have to be sought to explain the apparent objectivity of mathematics."
-Solomon Feferman, from "Does mathematics need new axioms?"[7]

Relationships between all elements of an infinite r. e. sequence are inter-subjective human conceptions, yet they can be logically determined and thus objective. For example an infinite r. e. sequence of finite statements may be all true, have at least one true and one false statement or be all false. Two of these three properties are human inventions in the sense that infinite sequences do not seem to exist physically. If at least one statement is true and another false, this can be proven with a finite argument, but there can be no general way to determine if all statements are true or all are false. Yet these two possibilities are objectively true or false in the sense that every event that determines either statement can be (at least in theory) physical.

Objective mathematics is logically determined by a r. e. sequence of events. `Logically determined' in this context is imprecise philosophy. Only fragments or what is intended can be precisely defined. The definition's power comes from recursively applying it to generate a precisely defined fragment of mathematics. Consider the question: does a r. e. set of Turing Machine (TM) Gödel numbers have an infinite subset, each element of which has an infinite number of outputs? All the events that determine this statement are r. e. The events are what each TM does at each time step. Generalizations of this question lead to the hyperarithmetic hierarchy[2].

1.2 Objective mathematics beyond ω₁^CK

One purpose of tying objective mathematics to an r. e. sequence of events is to insure that it is meaningful in and relevant to an always finite put possibly potentially infinite universe. Ideally this mathematics is more than indirectly relevant. For example large cardinal axioms have been used to derive consistency results and theorems in game theory[10]. Such results are usually arithmetic. Yet any arithmetic and even hyperarithmetic statement is decidable from a single axiom of the form n is or is not a notation for a recursive ordinal in Kleene's O. This is true because O is a Π₁¹ complete set. Using large cardinal axioms to decide these problems may be clever and important, but it assumes far more than is required.

The phrase physically meaningful implies more than Feferman's Q1: "Just which mathematical entities are indispensable to current scientific theories?"[6,p 284]. Questions about divergent evolution in an always finite but unbounded and potentially infinite universe can require quantification over the reals to state yet they are physically meaningful and even important to finite beings in such a universe. Consider the question will a single species have an infinite chain of descendant species. Assume a totally recursive and potentially infinite universe. Since a single species can, in theory, have an unbounded number of direct descendant species, it can have an unbounded sequence of finite chains of descendants without a single upper bound on all chains. Yet there may be no single chain of unbounded length. Thus this problem requires quantification over the reals to state.

For more about the mathematics and philosophy of creative divergent processes see:

Gödel, Darwin and creating mathematics (FOM posting),
Mathematical Infinity and Human Destiny (video)[3] and
What is and what will be (book)[1].

2 Kleene's O

Kleene's O is a set of integers that encode effective notations for every recursive ordinal[9]. From one of these notations, notations for all smaller ordinals are r. e. and those notations can be recursively ranked. However, there is no general way to decide which integers are ordinal notation nor to rank an arbitrary pair of notations in O.

In the following italicized lower case letters (n) represent integers (with the exception of `o'). Lower case Greek letters (α) represent ordinals. α = n_o indicates that the α is the ordinal represented by integer n. The partial ordering of integers, ` < _o', has the property that (∀m,n ∈ O)((n < _o m)→ (n_o < m_o)). The reverse does not hold because not all ordinal notations are ranked relative to each other.

Assume a Gödel numbering of the partial recursive function on the integers. If y is the index of a function under this Gödel numbering, y_n is its nth output. Then Kleene's O is defined as follows.

ordinal 0 = 1_o. The ordinal 0 is represented by the integer 1.
(n ∈ O) →(2ⁿ ∈ O∧(2ⁿ)_o = n_o + ordinal 1∧n < _o 2ⁿ).
If n is a notation in O then 2ⁿ is a notation in O for the ordinal n_o+ ordinal 1 and n < _o 2ⁿ.
If y is total and (∀n) (y_n ∈ O∧ y_n < _o y_n+1) then the following hold.
1. 3·5^y ∈ O.
2. (∪{n:n ∈ ω} (y_n)_o) = (3·5^y)_o.
3. (∀n) (y_n < _o 3·5^y).

The above gives notations for every recursive ordinal. For infinite ordinals the notations are not unique and there is no way to determine if an arbitrary integer is a notation. The ability to decide this is limited by the strength of the formal system applied to the problem.

3 P an extension of Kleene's O

The notations in O can be extended to larger countable ordinals with notations computed from the Gödel numbers of recursive functions that are total on well defined domains that are not r. e. The domains are labeled by ordinal notations. The extended notations are P and the extended relationship between notations is ` < _p'. Notations for finite ordinals are unchanged. Notations for successor ordinals are defined in the same way, but have different values because notations for limit ordinals differ. This approach is related to the development of countable admissible ordinals using TM oracles or relative recursion[13].

The domains or levels in P are denoted by ordinal notations as subscripts of P. Thus the level subscripts start with the sequence 1,2,4,...,2ⁿ of ordinal notations for the integers. The first level, P₁, contains notations for the integers. The next level, P₂, contains notations for the recursive ordinals represented by notations in O. Levels with a subscript that denotes a successor ordinal are defined with a generalization of O's definition. Successor levels use total recursive functions on the notations in the level with a subscript denoting the predecessor ordinal. Limit levels are defined as the union of levels with a smaller ( < _p) level index. Additional levels are defined by total recursive functions on defined domains that increase so rapidly that the notation computed from them must be used in specifying the minimum P level they all belong to. The levels are defined in Section 3.2.

It is convenient to base limit ordinal notations on the Gödel number of a TM rather than a recursive function. These TMs accept inputs and compute outputs. The inputs and outputs are ordinal notations. The first two outputs are prior to any input and specify the type of parameter accepted (that the TM is total over) and the type of parameter that can be defined using this TM. If n is limit ordinal notation in P, then the first output of the associated TM is n_a designating the type of parameter accepted (any notation in P_{n_a}) and the second output is n_b designating the minimum level in P that n is in. For notations of successor ordinals, the level index of valid inputs is meaningless. The parameter type or input level of finite successor notations in P is defined to be 1. It is in P₁. For infinite successor notations, the input level index is the same as it is for the notation for the largest limit ordinal from which this successor notation is computed.

3.1 P conventions

The following conventions are used in defining P.

A limit or successor notation is one that represents a limit or successor ordinal.
Greek letters (α, β, γ, ...) denote countable ordinals.
Italicized lower case letters (n , m, l, ...) (except a,b and p) denote integer ordinal notations. Base 10 integers (1,2,...,) are notations for ordinals and not ordinals themselves except in a phrase like "the ordinal 0". Thus, as in Kleene's definition of O, 1 represents the ordinal 0 and 4 represents the ordinal 2.
The subscript `p' in n_p implies n ∈ P and n_p denotes the ordinal represented by n under the assumed Gödel numbering of TMs and the map in Section 3.2 between TM Gödel numbers and ordinal notations. Only notations for finite ordinals are independent of this Gödel numbering.
P is defined in levels indexed by members of P using subscripts as in P_r. Levels are cumulative. P_r includes all members of P_s with s < _p r. A level is an input domain for TMs used in defining notations for a limit ordinals.
If n is a notation for a limit ordinal then the first output of the TM whose Gödel number was used in computing n is n_a and P_{n_a} is the domain or input level for this TM. The second output, n_b, labels the type of this notation as an input. All finite ordinal notations, m, have a predefined value for n_b=1. The a subscript has no meaning for successor notations in P. The notation for an infinite successor ordinal, s, denotes the sum of a limit ordinal, l, and a finite ordinal. s_b = l_b by definition.
The TM that defines limit notation n maps notations for ordinals in P_{n_a} to notations for ordinals in P_{n_b}. The union of all ordinals represented by notations in the range of this TM, over the domain, P_{n_a}, is the ordinal represented by n.
If m ∈ P, it is a valid input to the TM used to define the ordinal notation n iff m_b < _p n_a.
L(r) indicates that r is a notation for a limit ordinal.
If L(n), then T_n is the Gödel number of the TM used in defining n.
If k a valid input to T_n, then T_n(k) is the output of T_n for input k.

3.2 P definition

P and ` < _p' are defined in levels, P_r, as described below.

ordinal 0 = 1_p ∧1 ∈ P₁.
The notation for the ordinal 0 is 1. It is a member of P₁. the first level in the hierarchy.
(s < _p r ∧n ∈ P_s) → (n ∈ P_r).
A member of P_s also belongs to P_r if s < _p r.
(n ∈ P_r ∧β = n_p)→(2ⁿ ∈ P_r ∧β + ordinal 1 = (2ⁿ)_p ∧n < _p 2ⁿ).
The notation for the successor of the ordinal represented by n is 2ⁿ. If n ∈ P_r then 2ⁿ ∈ P_r and n < _p 2ⁿ.
(ordinal n ∈ ω) ≡ (ordinal n=(2ⁿ)_p ∧2ⁿ ∈ P₁).
P₁ is the set of notations for the integers or finite ordinals. The notation 2ⁿ represents the finite ordinal n.
The following defines a notation n for a limit ordinal in P_2^r using the Gödel number of the TM, T_n. that accepts inputs in P_r.
Note n = 3·5^T_n. This is the relationship between a limit ordinal notation and the Gödel number used in constructing the notation.
1. Before accepting inputs, T_n outputs the labels r and 2^r.
2. (∀m ∈ P_r) (T_n(m) ∈ P_2^r).
  The output of T_n for a valid input is in P_2^r. Note P_2^r contains all elements in P_r by Rule 2.
3. (∀m ∈ P_r) (∃k ∈ P_r) (m < _p T_n(k)).
  The range of T_n is not bounded in P_r and thus its level index is greater than r.
4. (∀u,v ∈ P_r) ((u < _p v)→ (T_n(u) < _p T_n(v))).
  T_n must map notations for ordinals of increasing size to notations for ordinals of increasing size.
  
  If 5a, 5b, 5c and 5d above hold then 5e, 5f and 5g below are true.
5. n = 3·5^T_n ∧n ∈ P_2^r.
  The ordinal notation, n, based on the Gödel number T_n belongs to P_2^r.
6. n_p = ∪{s:s ∈ P_r} (T_n(s))_p.
  The ordinal represented by n is the union of the outputs of T_n for all valid inputs.
7. (∀s ∈ P_r) (T_n(s) < _p n).
  The output of T_n for any element, m, in its range satisfies m < _p n or m_p < n_p.
L(r) → (P_r = ∪{s:s < _p r}P_s).
If r_p is a limit ordinal then P_r is the unions of of P_s for s < _p r.
(P′_r=(∪{m:m ∈ P_r}m))∧((∀m ∈ P_r) m < _p P′_r).
The notation for the union of all ordinals represented by notations in P_r is written as P′_r. Every ordinal notation in P_r is < _pP′_r. Note P_2^r contains a notation for the union of ordinals represented in P_r. This notation is constructible from the Gödel number of any TM that outputs r followed by 2^r and then copies its input to its output.
The limit of ordinal notations definable from the above is: ∪P′₂, P′_P′₂, P′_{P′_P′₂}, ... ,. It is straightforward to construct a TM that outputs this sequence of notations. However, only rule 5 defines notations for limit ordinals and it only defines these in a specified range, P_2^r. A rule is needed to define P_v from an r. e. set of ordinal notations where v is not previously defined.
The second output of the TM used to construct a notation for the above sequence must use its own Gödel number because the sequence includes all notations in levels indexed with notations for smaller ordinals. It is possible to construct this, but a simpler solution is to define that an initial second label output of 0 denotes the limit ordinal represented by the notation constructed from this TM's Gödel number.
If T_n meets the constraints listed below, this Gödel number can be used to construct an ordinal notation as defined below.
1. The first two outputs of T_n are r with r ∈ P followed by zero. The latter indicates a self reference to notation n.
2. (∀m ∈ P_r)(∀k < _p m) (T_n(k) < _p T_n(m)).
  T_n is a strictly increasing function on its domain.
3. (∀m ∈ P_r) (T_n(2^m) ≥ _p P′_{T_n(m)}).
  This puts a lower bound on the rate of increase of T_n. This rapid increase insures that the ordinal notations computed from valid parameters of T_n is consistent with a second output label of 0 from T_n.
  
  If 8a, 8b and 8c above hold then 8d, 8e and 8f below hold.
4. n=3·5^T_n ∧n ∈ P_n.
  The notation for the ordinal defined by T_n is 3·5^T_n. n is the index of the range, P_n, of the TM that defines n.
5. n_p = ∪{s:s ∈ P_r} (T_n(s))_p.
  The ordinal represented by n is the union of the outputs of T_n for all inputs in its domain.
6. (∀s ∈ P_r) (T_n(s) < _p n).
  The output, m, of T_n for any element in its range satisfies m < _p n.

3.3 Summary of rules for P

The above definitions 1 through 8 define integer notations for ordinals as summarized below.

The ordinal 0 has 1 as its notation (1).
Notations in P_s are in P_r if s < _p r (2).
The successor notation for n is 2ⁿ (3).
P₁ contains the notations for the integers (4).
Limit notations in P_2^r can be constructed from recursive functions whose range is P_r (5).
P′_r is a notation for the union of all ordinal represented by notations in P_r (7).
P_r with r a limit represents the union of all ordinals with notations in P_s for s < _p r (6).
The union of P′₂, P′_P′₂,P′_{P′_P′₂},..., and the union of other rapidly increasing TM outputs for increasing inputs can be defined using a domain, P_r, and a TM, T_n, on that domain. This rule defines both a notation v and a level P_v such that v ∈ P_v and v is not a member of any level with a smaller subscript. (8).

Although based on Kleene's approach, this notation system has different and weaker properties to allow for notations of ordinals ≥ ω₁^CK. Perhaps the most important is the logically required constraint that notations for ordinals ≥ ω₁^CK no longer allow the recursive enumeration of notations for all smaller ordinals. Non unique notations are defined for all smaller ordinals but there is no r. e. subset of these that represent all smaller ordinals. The exceptions are P₁ (the integers) and members of P₂ (notations for the recursive ordinals).

4 Q an extension of O and P

P seems to exhaust the idea of a typed hierarchy of domains of ordinal notations labeled and ordered by ordinal notations and defined by total recursive functions on those domains. Of course one can always add notations for countable ordinals inaccessible in an existing formalization, but more powerful extensions are desirable. This section develops the idea of a hierarchy of hierarchies and its generalizations. Q, is based on O and P. It labels levels with a sequence of ordinal notations supporting a hierarchy of hierarchies and beyond.

4.1 Hierarchies of ordinal notations

Kleene's O and the Veblen hierarchy[14,11,8,12] represent two complimentary ways in which a hierarchy of ordinal notations can be developed. Techniques like the Veblen hierarchy provide recursive ordinal notations for an initial segment of the recursive ordinals. In contrast Kleene's definition of O assigns integer notations for all recursive ordinals with no general way of determining which integers are notations or which notations represent the same ordinal.

The hierarchy of countable ordinals cannot be assigned notations as Kleene's O assigns notations for the recursive ordinals because the union of all countable ordinals is not countable. However the two ways of expanding the countable ordinal notations can extend past ω₁^CK. Any r. e. set of notations that reaches ω₁^CK will have gaps and any non r. e. complete set of notations will have a countable upper bound on the ordinals represented.

The first gap in the r. e. set of notations starts at the limit of the recursive ordinals represented in the system and may end at ω₁^CK. In contrast P in Section 3.2 assigns notations to all ordinals less than an ordinal much larger then ω₁^CK at the cost of not being able to decide in general which integers are ordinal notations. The ordinal calculator[4,5] defines a r. e. set of ordinal notations that go beyond ω₁^CK with gaps. The ordinal calculator project was one motivation for the development of P. Q establishes a theoretical base for expanding the ordinal calculator.

4.2 Q syntax

Many of the conventions in Section 3.1 are modified or augmented as described in Section 4.3. The notations in Sections 3.2 are reformulated in a more general form and expanded in Section 4.5.

Notations in Q are character strings that encode TM Gödel numbers and other structures. This replaces the integer coding conventions used by Kleene. The strings can be translated to integers using character tables like those for Unicode or ASCII.

`lb' is the syntactic element that labels a domain or level. Labels in Q play a similar role as level indices such as r in P_r. However labels in Q are lists of ordinal notations usually enclosed in square brackets. `od' is the syntactic element for an arbitrary ordinal notation. Either lb or od can be followed by _x (as in od_x) where x is a letter or digit to indicate a particular instance of a label or ordinal notation.

4.2.1 Q label (lb) syntax

The two labels output by TMs whose Gödel numbers are used in notations for Q (Section 4.5) are lists of notations in Q separated by commas and enclosed in square brackets. These labels implicitly define levels (or function domains) in Q. The explicit syntax for a level with label lb is Q[lb]. (Multiple square brackets enclosing the notation list in a label can be changed to 1.)

The label zero, used as a self reference in Rule 8 in Section 3.2, is replaced by the character string `SELF'. A notations with a range level label with a list containing a single notation `SELF' is defined as the zero label is defined in P. The ordinal notation is its own range level. The definition for other labels is in Rule 9 in Section 4.5.

Finite ordinal notations are base 10 integers starting with 0 for the empty set. They are the only notations without at least one explicit label. (For infinite successor ordinals the label of the type of input accepted is meaningless.) Some examples of levels in Q defined using notations for finite ordinals are:

Q[0] contains notations for finite ordinals, (those represented in P₁),
Q[1] contains notations for recursive ordinals (those represented in O and P₂),
Q[2] contains notations for ordinals represented in P₄,
Q[3] contains notations for ordinals represented in P₈,
Q[1,0] contains notations for ordinals represented in P and
Q[1,0,0] contains notations in a hierarchy of hierarchies (this is made precise in Section 4.5).

4.2.2 Q ordinal (od) syntax

The notation for a finite ordinal is a base 10 integer. The notation syntax for an infinite ordinal is `[lb_1] [lb_2] n + m'. The `+ m' is not used for limit ordinal notations. m is a base 10 integer indicating the mth successor of the limit ordinal represented by the part of the notation before `+'. n designates the TM with Gödel number n. lb_1 is an input label. It designates the type of inputs that are legal for this TM (they must be in Q[lb_1]) and lb_2 designates the type of this notation as a possible input to a TM in other notations. Thus Q[lb_2] is the first level that contains the notation, `[lb_1] [lb_2] n'.

The explicit labels are redundant because TM n must write out [lb_1] [lb_2] before accepting input.

4.3 Q conventions

The following include modified versions of the conventions from Section 3.1 with `P′ and `_p' replaced by `Q' and `_q' and other changes. There are also new conventions.

A limit or successor notation represents a limit or successor ordinal.
Greek letters (α, β, γ, ...) denote countable ordinals.
Bold face text is used for syntactic elements `lb' and `od' that can be expanded to a string of characters. `lb' (label) syntax is defined in Section 4.2.1 and `od' (ordinal notation) syntax is defined in Section 4.2.2. Instances of these syntactic elements are represented as `lb_x' and `od_x' where x can be a letter or an integer.
T_n is the TM whose Gödel number is n. If od_x is a valid input to T_n then T_n(od_x) is the ordinal notation computed from this input.
This is defined differently in Section 3.1 where the n in T_n is the ordinal notation constructed from the TM Gödel number. In that section T_3·5ⁿ is the TM with Gödel number n if 3·5ⁿ is an ordinal notation.
Italicized lower case letters (n , m, l, ... except a,b,q,s and t) denote integers.
If od_1=[lb_1][lb_2]n+m with the `+m' is omitted if m=0, then the following are defined.
od_1_a=[lb_1].
od_1_b=[lb_2].
od_1_t=n.
od_1_s=m.
od_1_q= the ordinal represented by this notation.
Finite ordinals are represented as base 10 integers. Their labels are both defined to be zero.
od_1 < _qod_2 indicates the relative ranking of the two notations in Q. It implies that od_1_q < od_2_q. The reverse is not always true since not all pairs of notations in Q are ordered by < _q.
od_1 is a valid input to T_{od_2_t} iff od_1_b < _qod_2_a.
The subscript `q' in od_1_q implies od_1 ∈ Q and od_1_q denotes the ordinal represented by od_1 under an assumed Gödel numbering of TMs.
Q is defined in labeled levels written as Q[lb]. These levels define valid inputs for a TM whose Gödel number is part of an ordinal notation. Such a TM maps notations for ordinals to notations for ordinals. The union of all ordinals represented by notations in the range of this TM, over the domain of valid inputs, is the ordinal represented by the notation.
lb_1+m is a modified version of lb_1 with m added to its least significant notation. This is used in Rule 7 in Section 4.5, which is a relative version of Rule 5 in Section 3.2.
SELF signifies an ordinal notation that uses its own Gödel number in the second output label. SELF can only occur in the second label as the least significant notation. The rest of the second label must be the same as the first label as in:
[od_1,...,od_m,od_x][od_1,...,od_m,SELF]n.
od_1+k is the kth successor of od_1.
The notation for the union of all ordinal notations in [lb_1] is ` Q[lb_1]'. A notation for this ordinal is also given by [lb_1][lb_1+1]n where T_n outputs the two labels and computes and outputs the identity function on any inputs.
L(od_1) indicates that od_1 is a notation for a limit ordinal.
If od_1_b < _qod_2_a∧L(od_2) then T_{od_2_t}(od_1) is the notation output from the TM encoded in od_2 with input notation od_1. This can also be written as od_2(od_1).
[lb_x]_m is the notation in the mth position of lb_x. The least significant position is 0.
L(n,[lb_x]) means the nth least significant notation in lb_x denotes a limit ordinal. Note the least significant notation in a label is at position n=0.
L([lb_x]) = L(0,[lb_x]) and means the least significant notation in lb_x denotes a limit ordinal.
S(n,[lb_x]) means the nth least significant notation in lb_x represents a successor ordinal and all less significant notations in lb_x are 0.
R(n,[lb_x],od_y) is the syntactic substitution of the nth least significant notation in [lb_x] with od_y.
R([lb_x],od_y) = R(0,[lb_x],od_y) and is the syntactic substitution of the least significant notation in [lb_x] with od_y
[lb_x]_n is the nth least significant notation in lb_x. The least significant position is [lb_x]₀.
||lb_x|| is the maximum number of notations that occur as text in the notation fragment lb_x (including notations equal to zero) or, if it is greater, the value of ||lb_y|| where lb_y ranges over all the labels in the notations contained in lb_x. Thus it is applied recursively down to finite labels.
Z([lb_x]) is the number of consecutive zeros in lb_x starting at the least significant notation. Following are some examples.
Z([m,0])=1.
Z([12,0,0,11,1,0,0,0,0])=4.
Z([76,0,0,0,0,0,0,1])=0.
A(n,[lb_1],[lb_2]) means lb_1 and lb_2 have the same most significant notations starting at position n. A(0,[lb_1],[lb_2]) means they agree on all positions.
M([lb_1]) is the position (the least significant position is 0) of the most significant nonzero notation in lb_1.
V(m,[lb_1]) ≡ (Z([lb_1])=m ∧M([lb_1])=m∧[lb_1]_m=1).
V(m,[lb_1]) means [lb_1] is of the form [1,0,...,0] with m consecutive least significant notations of zero and a most significant notation of 1 at position m.
Q_L, the set of all labels used in Q. Thus it contains all finite sequences of notations, every element of which is ranked ( < _q) against every other element.

4.4 Ranking labels (lb) in Q

The level labels in P are ordinal notations ranked by < _p. In Q, level labels are a list of ordinal notations. These labels are ranked using < _q augmented by other constraints. For example all members of O represent ordinals < ω₁^CK. This constraint is generalized in Rule 1 below.

The following rules determine when the relationship [lb_1] < _q [lb_2] is defined and, if defined, what its truth value is.

V(m,[lb_1]) →(∀lb_2 ∈ Q_L)((||lb_2|| ≤ m) → ([lb_2] < _q[lb_1]))
Every label of the form [1,0,...,0] with m+1 notations is greater than ( > _q) every notation that has at most m notations such that each of these ordinal notations has at most m notations in their two labels and this is true recursively down to integer notations.
If lb_1 and lb_2 agree except for the the mth position and [lb_1]_m < _q [lb_2]_m then [lb_1] < _q [lb_2].
([lb_1] < _q [lb_2] ∧[lb_2] < _q [lb_3]) →([lb_1] < _q [lb_3]).
< _q on labels is transitive.
[lb_1] < _q [lb_2] if all four of the following conditions hold.
1. Z(m,[lb_2])
  The least significant m notations in lb_2 are zero.
2. A(m+1,[lb_1],[lb_2]).
  lb_1 and lb_2 have the same notations at position m+1 and all more significant positions.
3. [lb_1]_m < _q [lb_2]_m.
  The notations in position m in lb_1 is less than the notation in position m in lb_2.
4. (∀{k:0 ≤ k < m})[[lb_1]_k] < _q [lb_2].
  For all consecutive least significant zero notations in lb_2, the label containing the single notation in the same position in lb_1 is [[lb_1]_k], and [[lb_1]_k] < _q [lb_2].

4.5 Q definition

The definition of Q is based in part on the rules for P in Section 3.2. Q and ` < _q' are defined in stages, Q[lb_x]. Q[0] contains base 10 integer notations for the finite ordinals. The ordinals represented by notations in O are those with notations in Q[1]. The ordinals represented by notations in P are those with notations in Q[1,0].

Q contains the notations defined below.

Notations for finite ordinals, starting with the empty set, are base 10 integers. Q[0] contains these notations.
The syntax for level labels (lb) and ordinal notations (od) are in sections 4.2.1 and 4.2.2. The ` < _q' partial relationship between labels is given in Section 4.4. An additional requirement for a limit ordinal notation od_1 is od_1_a < _qod_1_b.
Q_L is the set of all labels used in defining Q. Q_L contains all finite sequences of ordinal notations such that for any two labels in a sequence, lb_1 and lb_2, the relationship lb_1 < _q lb_2 is defined.
(∀lb_x ∈ Q_L)(∀od_1 ∈ Q[lb_x])((od_1+1) ∈ Q[lb_x] ∧od_1 < _q (od_1+1)).
An ordinal is < _q its successor and they both belong to the same level.
The notation for the union of all ordinals represented in Q[lb_1] is Q[lb_1]′. A notation for this ordinal is also given by [lb_1][lb_1+1]n where T_n outputs [lb_1][lb_1+1] and then copies each input as output. This is similar to the definition in Rule 7 in Section 3.2.
([lb_1] < _q [lb_2]∧od_n ∈ Q[lb_1]) → (od_n ∈ Q[lb_2]).
If [lb_1] < _q [lb_2], any member of Q[lb_1] belongs to Q[lb_2].
The following defines limit ordinal notations in Q[lb_1+1] using notations in Q[lb_1]. It is a relativized version of Rule 5 in Sections 3.2. If T_n meets the following constraints it can be used to define ordinal notation [lb_1][lb_1+1]n in Q[lb_1+1].
1. T_n must output labels `[lb_1] [lb_1+1]' before accepting input.
2. (∀od_x ∈ Q[lb_1]) (T_n(od_x) ∈ Q[lb_1+1]).
  The output of T_n for valid input is an ordinal notation in Q[lb_1+1].
3. (∀od_x ∈ Q[lb_1])(∃od_y ∈ Q[lb_1])(od_x < _q T_n(od_y)).
  The range of T_n is not bounded in Q[lb_1] and thus its level label is greater than lb_1.
4. (∀od_x,od_y ∈ Q[lb_1])(od_x < _q od_y) → (T_n(od_x) < _q T_n(od_y)).
  T_n must map notations for ordinals of increasing size to notations for ordinals of increasing size.
  
  If 7a, 7b, 7c and 7d above hold then 7e, 7f and 7g below are true.
5. [lb_1][lb_1+1]n ∈ Q[lb_1+1].
6. (∀od_x ∈ Q[lb_1])(T_n(od_x) < _q [lb_1][lb_1+1]n).
  The output of T_n for any element in its range is < _q [lb_1][lb_1+1]n.
7. ([lb_1][lb_1+1]n)_q = ∪{od_x:od_x ∈ Q[lb_1]}(T_n(od_x))_q.
  [lb_1][lb_1+1]n represents the union of the ordinals with notations that are output from T_n from inputs in its domain.
(Z([lb_x])=m∧L(m,[lb_x])) →(Q[lb_x] = ∪{od_x:od_x < _q [lb_x]_m} Q[R(m,[lb_x],od_x)])
If the least significant non zero notation in lb_x is od_y in the mth position and it represents a limit ordinal, then Q[lb_x] is the union of levels in which od_y in the mth position is replaced by all notations od_x < _qod_y.
A relative version of Rule 8 in Section 3.2 is needed. There is no restriction on the first label. The second label must agree with the first label except the least significant notation is replaced with SELF. This use of SELF requires that the function that defines this notation increase rapidly enough that its Gödel number can be used to label its output.
If an ordinal notation of the form od_1=[lb_1][R([lb_1],SELF)]n meets the conditions listed below than it is an ordinal notation in Q[od_1] as defined below.
1. T_n outputs [lb_1][R([lb_1],SELF)] before accepting input.
2. (∀od_x,od_y ∈ Q[lb_1])((od_x < _qod_y)→(T_n(od_x) < _q T_n(od_y)))
  T_n is strictly increasing over its domain.
3. (∀od_x ∈ Q[lb_1]) (T_n(od_x+1) ≥ _q Q[T_n(od_x)]′)
  The insures that T_n increased fast enough that the SELF label applies.
  
  If 9a, 9b and 9c above hold then 9d, 9e and 9f below hold.
4. od_1 ∈ Q[od_1].
  The notation for od_1 labels the level it belongs to.
5. od_1_q = ∪{od_x:od_x ∈ Q[lb_1]} (T_n(od_x))_q.
  od_1 represents the union of the ordinals represented by notations T_n(od_x) for od_x in Q[lb_1].
6. (∀od_x ∈ Q[lb_1])(T_n(od_x) < _q od_1).
  For all ordinal notations, od_(x), in Q[lb_1] the notation T_n(od_x) < _q od_1.
(S(m,[lb_1]) ∧m > 0)→(Q[lb_1] = ∪{lb_x:[lb_x] < _q[lb_1]} Q[lb_x])
If lb_1 is a label with one or more consecutive least significant notations of zero and a least significant nonzero notation that is a successor then Q[lb_1] is the union of all levels Q[lb_x] with [lb_x] < _q[lb_1].

4.6 Summary of rules for Q

Q[0] contains notations for the finite ordinals (1).
The syntax for ordinal notations and labels is referenced. The rules for label ranking are referenced. The rule that in every notation od_x, od_x_a < _q od_x_b is added. (2).
Q_L, the set of all labels used in Q, contains all finite sequences of notations, every element of which is ranked ( < _q) against every other element (3).
An ordinal is < _q its successor and they both belong to the same level (4).
Q[lb_1]′ is the union of notations in Q[lb_1] (5).
Levels inherit notations from all lower levels. (6).
Limit ordinal notations in levels with a label whose least significant notation is a successor are defined using recursive functions on the predecessor level. (7).
Levels with a label whose least significant nonzero notation represents a limit ordinal are defined (8).
Notations with labels that reference themselves and the corresponding levels are defined (9).
Levels with a label that has one or more least significant zeros and a least significant nonzero successor notation are defined. (10).

5 Conclusions

In set theory infinite ordinals are treated as objects. However infinite sets do not seem to exist in our universe. They are Platonic abstractions that have long been questioned perhaps from the dawn of mathematical thinking about the unbounded. In our universe even the countable infinite appears to be unreachable and the uncountable is irreducibly ambiguous as shown by the Lowenheim-Skolem theorem. By expanding the ordinal hierarchy as computable notations on non recursive but objectively defined domains, the ambiguity of the uncountable is avoided. The Gödel numbers of TMs with a well defined property must form a countable set. Of course the properties can be defined in ways that are ambiguous or inconsistent. There is no way to guarantee against such mistakes, but they are mistakes not philosophical issues.

Mathematicians can use whatever formalism and whatever intuitive abstractions help as long as the results are derivable in a widely accepted formalism. Currently such formalisms include ZFC set theory. This is not likely to change until and unless a more philosophically conservative formalism is more powerful than ZFC at least in deciding arithmetical questions.

One advantage of ordinal notations, as developed here, is that they can be explored with computer code. This allows the manipulation of combinatorial structures of complexity well beyond the capabilities of the unaided human mind. This differs from the substantial efforts at automated theorem proving and computer verification of existing proofs . Both efforts are important, but they focus on automating and verifying the work that mathematicians do now.

I conjecture that all mathematics that is unambiguous in an always finite but potentially infinite universe can be modeled by recursive processes on a logically determined domain. Here recursive processes include single path and divergent recursive processes that explore all possible paths. If this is true than, to some degree, the foundation of mathematics can become an experimental science.

References

[1]: Paul Budnik. What is and what will be: Integrating spirituality and science. Mountain Math Software, Los Gatos, CA, 2006.
[2]: Paul Budnik. What is Mathematics About? In Paul Ernest, Brian Greer, and Bharath Sriraman, editors, Critical Issues in Mathematics Education, pages 283-292. Information Age Publishing, Charlotte, North Carolina, 2009.
[3]: Paul Budnik. Mathematical Infinity and Human Destiny HQ (video). January 2009.
[4]: Paul Budnik. An overview of the ordinal calculator. March 2011.
[5]: Paul Budnik. A Computational Approach to the Ordinal Numbers: Documents ordCalc 0.3. 2011.
[6]: Solomon Feferman. In the Light of Logic. Oxford University Press, New York, 1998.
[7]: Solomon Feferman. Does mathematics need new axioms? American Mathematical Monthly, 106:99-111, 1999.
[8]: Jean H. Gallier. What's so Special About Kruskal's Theorem And The Ordinal Γ₀? A Survey Of Some Results In Proof Theory. Annals of Pure and Applied Logic, 53(2):199-260, 1991.
[9]: S. C. Kleene. On notation for ordinal numbers. Journal of Symbolic Logic, 3(4), 1938.
[10]: Peter Koellner and W. Hugh Woodin. Large cardinals from determinacy. In Matthew Foreman and Akihiro Kanamori, editors, Handbook of Set Theory, pages 1951-2120. Springer, 2010.
[11]: Larry W. Miller. Normal functions and constructive ordinal notations. The Journal of Symbolic Logic, 41(2):439-459, 1976.
[12]: Michael Rathjen. The Art of Ordinal Analysis. In Proceedings of the International Congress of Mathematicians, Volume II, pages 45-69. European Mathematical Society, 2006.
[13]: Gerald E. Sacks. Metarecursively Enumerable Sets and Admissible Ordinals. Bulletin of the American Mathematical Society, 72(1):59-64, 1966.
[14]: Oswald Veblen. Continuous increasing functions of finite and transfinite ordinals. Transactions of the American Mathematical Society, 9(3):280-292, 1908.

Footnotes:

¹The uncountable may have an objective countable model in a formal system and thus have a definite interpretation relative to that formal system. It is not a definite thing in an absolute sense. I agree with Weyl and Feferman:"To quote Weyl, platonism is the medieval metaphysics of mathematics; surely we can do better"[6,p 248].

There is, however, an important element of truth in the idea of an abstract Platonic ideal that has become a practical reality in the age of computers. We may not be able to construct a perfect circle but π has been computed to more than a trillion decimal places with a very high probability that it is correct. The Platonic ideal, for sufficiently simple combinatorial mathematics, is approachable to ever higher accuracy with ever higher probability.

²Feferman's note: "CH is just the most prominent example of many set-theoretical statements that I consider to be inherently vague. Of course, one may reason confidently within set theory (e. g., in ZFC) about such statements as if they had a definite meaning."

File translated from T_EX by T_THgold, version 4.00.

Mountain Math Software

Email comments to: webmaster@mtnmath.com