Relation between an OCF and an Ordinal Notation

Googologists here often confound several distinct notions such as:

1. an OCF (ordinal collapsing function)
2. an ordinal notation
3. a notation with a correspondence to ordinals
4. a notation with a system of fundamental sequences
5. a system of fundamental sequences for ordinals,

even if they are highly familiar with analysis. I have seen them to state "I created a new ordinal notation!" just by showing a notation with a correspondence to ordinals so many times. They might not know what an ordinal means (it does not mean a symbol!), what a recursive order means (it does not mean the order of the corresponding ordinals!), what the well-foundedness means (it is not a removable condition which you can always ignore!), what an ordinal notation precisely means, or something like that.

They have written so many blog posts containing incorrect descriptions on OCFs and ordinal notations. As a result, when newbies come here to study OCFs and ordinal notations, they will unfortunately find and trust those blog posts, because there are few explanations in this wiki explaining what they atually are. Of course, it is newbies' own failure derived from skipping to check sources. However, don't you think that it much better for us to resolve this awful ruin in order to avoid more victims of predecessors' relics? That is why I explain what OCFs and ordinal notations are and the relation among them in googology.

OCF

An OCF is a shorthand of an ordinal collapsing function, and is a notion in set theory. It is a sort of a function which reduces some "degree" of an ordinal. So "a function \(\psi\) is an OCF" is not a mathematical statement, but is an explanation of a role of \(\psi\) in the context.

Purpose

We want a computable large number!

In order to define a computable large number, we use ordinal notation with a recursive system of fundamental sequences through functions which converts terms in a well-ordered set into natural numbers, e.g. FGH and HH. Therefore we need an ordinal notation whose ordinal type is a large ordinal.

In order to define an ordinal notation, we use a large recursive countable ordinal admitting a recursive way to express all ordinals below it by finite strings so that \(\in\)-relation can be interpreted into a primitive recursive relation on finite strings.

In order to define such a large recursive countable ordinal, we use cardinals through functions which send cardinals to recursive countable ordinals, e.g. several \(\psi\)-functions and \(\vartheta\)-functions. So these are OCFs. They reduce the cofinality (or the cardinality) of cardinals. Therefore we need a large cardinal.

In order to define a large cardinal, we use weakly (hyper) inaccessible cardinals through functions generalising OCFs above sending weakly (hyper) inaccessible cardinals to cardinals, e.g. several extended \(\psi\)-functions. They reduce the degree of the weak (hyper) inaccessibility. Therefore we need a large weakly (hyper) inaccessible cardinal, and also a larger cardinal far beyond them, e.g. a weakly Mahlo cardinal.

In order to define a large... Ok. I stop it.

Construction

For appropriate ordinals \(\kappa\) and \(\alpha\), we would like to define a new ordinal \(\psi_{\kappa}(\alpha)\). To begin with, choose

• finitely many (possibly multi-variable) functions \(F_0,F_1,\ldots,F_m\) which sends ordinals to ordinals, e.g. the constant map \(\alpha \mapsto 0\), the addition \((\alpha,\beta) \mapsto \alpha + \beta\), and Veblen function \((\alpha,\beta) \mapsto \varphi_{\alpha}(\beta)\), and
• a set \(C_{\kappa}^0\) of ordinals.

There are essentially two ways to define \(\psi_{\kappa}(\alpha)\) by transfinite induction on \(\alpha\).

1. Define a set \(C_{\kappa}(\alpha)\) of ordinals presentable by a combination of ordinals in \(C_{\kappa}^0\), \(F_0,F_1,\ldots,F_m\), and \(\psi_{\pi}(\beta)\) for some \(\beta < \alpha\) and \(\pi\). Then define \(\psi_{\kappa}(\alpha)\) as the smallest ordinal which does not belong to \(C_{\kappa}(\alpha)\).
2. Define a set \(C_{\kappa}(\alpha)\) in a similar way above, except that combinations of \(C_{\kappa}^0\), \(F_0,F_1,\ldots,F_m\), and \(\psi_{\pi}(\beta)\) are allowed only when the expressions are of "normal form". So you need to define the notion of normal form for expressions of ordinals. What is an "expression" of an ordinal? You can formally define an expression as a sequence of constants and functions in set theory.

An OCF defined without using expressions is easy for readers to understand. On the other hand, we need to make implicit efforts to define it, because we are not allowed to define an OCF in a way like "Replace the last appearence of \(\omega\) in the input of \(\psi_{\kappa}\) by blah-blah".

An OCF defined by using expressions is not so easy for readers to understand. Moreover, we need to define the notion of normal form in a way that every ordinal (with a fixed bound if necessary) admits precisely one normal form expression. But after that we are allowed to define an OCF in a way like "Replace the last appearence of \(K\) in the input of \(\psi_{\kappa}\) by blah-blah".

Defining an OCF by using expression is quite similar to defining an OCF and an ordinal notation simultaneously by using each other. Therefore even if they do not use expressions, they often actually need to define the notion of normal (or standard) form for formal strings in order to define the associated ordinal notation.

Example

I set \(F_0\) as the addition \((\alpha,\beta) \mapsto \alpha+\beta\), and only allow the case \(\kappa = 0\). Since \(\kappa\) does not vary in this context, I abbreviate \(\psi_{\kappa}\) and \(C_{\kappa}^0\) to \(\psi\) and \(C^0\) respectively. I compute \(\psi\) in the case \(C^0 = \{0,\Omega\}\).

---

For an ordinal \(\alpha\) and a natural number \(n\), I simultaneously define a set \(C^{\infty}\) and an ordinal \(\psi(\alpha)\) in the following recursive way:

1. \(C^{\infty}(\alpha)\) is the smallest set satisfying the following:
   1. \(0,\Omega \in C^{\infty}(\alpha)\).
   2. For any \(\beta, \gamma \in C^{\infty}(\alpha)\),\(\beta + \gamma \in C^{\infty}(\alpha)\).
   3. For any \(\beta \in \alpha \cap C^{\infty}(\alpha)\), \(\psi(\beta) \in C^{\infty}(\alpha)\).
2. \(\psi(\alpha)\) is the least ordinal which is not contained in \(C^{\infty}(\alpha)\).

---

If I allow use of more functions \(F_0,\ldots,F_{m-1}\) and a wider range of \(\kappa\), then the resulting OCF will become more complicated. On the other hand, the OCF only using addition and \(\kappa = 0\) is quite simple. It is easy to verify the following properties of \(\psi\):

1. For any ordinals \(\alpha\) and \(\beta\), \(\alpha < \beta\) implies \(\psi(\alpha) \leq \psi(\beta)\).
2. For any ordinal \(\alpha\), \(\psi(\alpha) < \Omega\).
3. For any ordinal \(\alpha\), \(\alpha < \varepsilon_0\) implies \(\psi(\alpha) = \omega^{\alpha}\).
4. For any ordinal \(\alpha\), \(\varepsilon_0 \leq \alpha \leq \Omega\) implies \(\psi(\alpha) = \varepsilon_0\).
5. \(\psi(\Omega + 1) = \varepsilon_0 \times \omega\).

It is important to compute examples in order to understand OCFs, and hence please verify the properties above by yourself.

Caution

First of all, one of the most awful mistakes in this community is the intuitive belief the function \((\alpha,n) \mapsto f_{\alpha}(n)\) given by a certain system of fundamental sequences associated to an OCF through FGH were computable. In fact, since an OCF itself is a set-theoretic stuff dealing with proper infinities, such a fucntion is not interpreted into a Turing machine, and hence is uncomputable. Therefore using OCF is insufficient for the purpose to construct a computable large number. What we actually need to create is an ordinal notation. Unfortunately, since many googologists comfound ordinals and strings given as their expressions, it is quite difficult to explain why it is uncomputable. Roughly speaking, an ordinal notation just uses finite strings in arithmetic, while an OCF actually use infinities.

Although it is irrelevant to an OCF, it is awful that there are several googologists who state something like "I know the names of a large ordinal such as \(\textrm{PTO}(\textrm{ZFC}+\textrm{I}0)\), and hence it directly means that I can create a computable ultimately large number! I win!" Then it is obvious that they do not even understand the defintions of what they are "using". Then unfortunately, they are unable to understand any explanation how they are wrong. In order to avoid such a pity, I strongly recommend googologists to use stuffs whose definitions they actually know.

Also, several googologists often "define" OCFs (or general functions related to ordinals) by using expressions, even though they have not defined appropriate normal forms in the sense above. Such OCFs are usually ill-defined.

For example, the following rule to define a function \(\psi\) related to ordinals does not make sense:

• For any limit ordinal \(\beta\) and any function \(f\) which assigns ordinals to ordinals (satisfying several conditions), \(\psi(f(\beta))\) is the limit of the fundamental sequence \((\psi(f(\beta))[n])_{n=0}^{\infty}\) defined as \((\psi(f(\beta[n])))_{n=0}^{\infty}\).

Since it is impossible to reconstruct \(f\) and \(\beta\) from the ordinal \(\gamma\) expressed as \(f(\beta)\), the use of \(f\) and \((\beta[n])_{n=0}^{\infty}\) in the definition of \(\psi(\gamma)\) and \((\psi(\gamma)[n])_{n=0}^{\infty}\) is completely invalid.

Of course, if you want to define an ordinal notation system associated to an OCF, the notion of a normal form should be defined in a recursive way. Although googologists often forget to set normal forms, this is one of the most important and difficult steps to study OCFs. Several conditions used in the recursive definitions of OCFs in mathematical paper are actally used for this purpose, while googologists "simplify" or "extend" those OCFs by removing such complicated conditions without understanding the reasons why the authors originally assumed those conditions. Then the resulting OCFs will be very weakened or the associate ordinal notation system will be ill-defined, even if they used larger cardinals or higher diagonalisations.

Ordinal Notation

An "ordinal notation" is a shorthand of an ordinal notation system, and is a notion which makes sense in arithmetic. Although there are several formulations, it is a sort of strictly well-ordered systems \((OT,<)\) of formal strings called ordinal terms consisting of fixed symbols such as \(0, \omega, \Omega, I, M, K, T, F_{0=1}, +, \varphi, \psi\). More precisely, \(OT\) is a recursive subset of \(\mathbb{N}\) or another set \(X\) with a fixed bijection \(i \colon X \to \mathbb{N}\) so that recursiveness of a partial function on \(OT^2\) makes sense, and \(<\) is a recursive strict well-ordering on \(OT\). Some author assumes that \(<\) is primitive recursive or that \(i\) is the identity map, but some author allows \(<\) to be non-recursive or a well-founded partial ordering. Also, some author refers to terms of an ordinal notation as an ordinal notation. I only consider a recursive well-ordering here in order to avoid uncomputable notations like Kleene's \(\mathcal{O}\), because an ordinal notation in googology is usually used in computable googology.

You can use any symbols as long as you fix them, because they can be regarded as the canonical basis of a countable free monoid, which is canonically bijective to a countable power of \(\mathbb{N}\). Of course, it is prefered to follow traditional customs. So \(0\) should be the smallest ordinal term, and \(I\) should play a role similar to weakly inaccessible cardinals. However, an ordinal notation is just a notion which makes sense in arithmetic, and hence there is no actual relation to set theory here even if you intend \(I\) to play a role similar to the least weakly inaccessible cardinal. Therefore a statement like "Since I use the symbol \(I\), it is stronger than a notation which does not use the least weakly inaccessible cardinal!" is a typical misundrstanding.

Purpose

We want a computable large number!

Constructing a large recursive countable ordinal is not sufficient. We also need a recursive system of fundamental systems, and a way to describe it in arithmetic, in order to define a computable large function. Therefore we need an ordinal notation in order to use it as a domain of a recursive system of fundamental sequences which will be defined in another step. Otherwise, enjoy Busy Beaver function. It is also cute, and far beyond computable large functions.

Construction

This is just an example of a strategy to construct an ordinal notation, and hence you do not have to obey the method here. To begin with, choose

• finitely many function symbols \(f_0,f_1,\ldots,f_m, f_{m+1}\), e.g. a constant term symbol \(0\) (i.e. a function symbol of arity \(0\)), the addition symbol \(+\) (i.e. a function sysmbol of arith \(2\)), and other function symbols such as \(D\), \(\psi\), \(\varphi\), \(\Phi\), \(\chi\), and so on,
• finitely many brace symbols, e.g. \((,),\{,\},\langle,\rangle\),
• finitely many separator symbols, e.g. comma, colon, and semicolon, and
• a recursive set \(T\) of formal strings called terms consisting of brace symbols, separator symbols, and \(f_0,f_1,\ldots,f_m,f_{m+1}\) satisfying syntax theoretic restrictions on the arity, e.g. if \(f_0\) is of arity \(0\) and \(f_3\) is of arity \(1\), \(f_3(f_0)\) and \(f_3(f_3(f_0))\) are allowed but \(f_3(f_3)\) or \(f_0(f_0)\) are not allowed.

There are essentially two ways to define an ordinal notation \((OT,<)\). One is purely arithmetic, and the other one is partially set theoretic.

1. Define a binary relation \(<\) on \(T\) by a (primitive) recursive computation using the syntax theoretic structure on terms, and a recursive subset \(OT \subset T\) to which the restriction of \(<\) is a strict well-order.
2. Define an OCF \(\psi\) by choosing other data \(F_0, F_1, \ldots, F_m\) and using a notion of expressions of normal form. Then denote by \(o\) the map from \(T\) to the class of ordinals associated to the correspondence \((f_0,f_1,\ldots,f_m,f_{m+1}) \mapsto (F_0,F_1,\ldots,F_m,\psi)\), and by \(OT \subset T\) the subset of terms \(a\) such that the canonical expression of \(o(a)\) by \(F_0,F_1,\ldots,F_m,\psi\) is of normal form. Finally, "interprete" the relation \(o(a) \in o(b)\) for terms \(a\) and \(b\) into a recursive relation \(<\) on \(T\). More Precisely, define a recursive relation \(<\) on \(T\) such that \(o(a) \in o(b)\) is equivalent to \(a < b\) for any \(a,b \in OT\) (not \(T\)).

The benefit of the first approach is that it is purely arithmetic. However, it is not so easy to prove that \((OT,<)\) is actually an ordinal notation, i.e. \(<\) is a well-order on \(OT\), and that it presents a sufficiently large countable ordinal. Of course, it does not mean that it were impossible.

For example, see my ordinal notation here. I directly defined an ordinal notation with \(\textrm{PTO}(\textrm{ZFC})\) without using set theory itself. If what Rathjen stated without proof on the provability of the well-foundedness of his ordinal notation with the smallest weakly Mahlo cardinal, then I guess that my ordinal notation goes beyond it.

The benefit of the second approach is that the well-foundedness immediately follows from that of ordinals. However, it is not so easy to define an OCF by using expressions of normal form. At least, defining the notion of normal forn and interpreting \(\in\) into a recursive order \(<\) is not uniquely done even if we have an OCF. Therefore there is no canonical way to define an ordinal notation from an OCF. Namely, an OCF is not actually a specific ordinal notation at all.

Example

I consider an ordinal notation associated to the example of an OCF. Since I set \(F_0\) as the addition \((\alpha,\beta) \mapsto \alpha+\beta\), the corresponding function symbol \(f_0 = \oplus\) is of arity \(2\). Since \(\psi\) is of aity \(1\), the corresponding function symbol \(f_1 = D\) is of arity \(1\).

---

I define a set \(T\) of finite strings of symbols \(0\), \(\Omega\), \(\oplus\), \(D\), \((\), and \()\) in the following recursive way:

1. \(0,\Omega \in T\).
2. For any \(s \in T\), \(D(s) \in T\).
3. For any \(s \in T\), \(\Omega \oplus s \in T\).
4. For any \(s,t \in T\), \(D(s) \oplus t \in T\).

I define a subset \(PT \subset T\) in the following recursive way:

1. \(\Omega \in PT\).
2. For any \(s \in T\), \(D(s) \in PT\).

I define a relation \(s < t\) on \(s,t \in T\) in the following recursive way:

1. If \(t = 0\), then \(s < t\) does not hold.
2. Suppose \(t \neq 0\).
   1. If \(s = 0\), then \(s < t\).
   2. If \(s = \Omega\), then \(s < t\) is equivalent to that there exists a \(t' \in T\) such that \(t = \Omega \oplus t'\).
   3. Suppose that there is an \(s' \in T\) such that \(s = D(s')\).
      1. If \(t = \Omega\), then \(s < t\).
      2. Suppose that there is a \(t' \in T\) such that \(t = D(t')\), then \(s' < t'\) and \(s < t\) are equivalent to each other.
      3. Suppose that there are a \(t_1 \in PT\) and a \(t_2 \in T\) such that \(t = t_1 \oplus t_2\), then "\(s < t_1\) or \(s = t_1\)" and \(s < t\) are equivalent to each other.
   4. Suppose that there are a \(s_1 \in PT\) and a \(s_2 \in T\) such that \(s = s_1 \oplus s_2\).
      1. If \(t \in PT\), then \(s < t\) is equivalent to \(s_1 < t\).
      2. Suppose that there are a \(t_1 \in PT\) and a \(t_2 \in T\) such that \(t = t_1 \oplus t_2\).
         1. If \(s_1 < t_1\), then \(s < t\).
         2. If \(s_1 < t_1\), then "\(s_1 = t_1\) and \(s_2 < t_2\)" and \(s < t\) are equivalent to each other.

I emphasise that the recursive relation \(<\) is just a total order on \(T\), which is not a strict well-ordering. It becomes a strict well-ordering when it is restricted to a subset \(OT \subset T\) defined below.

In order to define the notion of standard form, I introduce a \(2\)-ary relation \(s \triangleleft t\) on \((s,t) \in T\) in the following recursive way:

1. If \(s \in \{0,\Omega\}\), then \(s \triangleleft t\) is true.
2. If there is an \(s' \in T\) such that \(s = D(s')\), then \(s \triangleleft t\) is equivalent to \(s' \triangleleft t\) and \(s' < t\).
3. If there is an \((s_1,s_2) \in PT \times T\) such that \(s = s_1 \oplus s_2\), then \(s \triangleleft t\) is equivalent to \(s_1 \triangleleft t\) and \(s_2 \triangleleft t\).

I define a subset \(OT \subset T\) in the following recursive way:

1. \(0,\Omega \in OT\).
2. For any \(s \in T\), if \(s \triangleleft s\), then \(D(s) \in OT\).
3. For any integer \(m \geq 2\) and \((s_i)_{i=1}^{m} \in (OT \cap PT)^m\), if \((s_i)_{i=1}^{m}\) is non-strictly decreasing with respect to \(<\), then the concatenation of \((s_i)_{i=1}^{m}\) by the separator \(\oplus\) belongs to \(OT\). (In other words, for any \(s_1,\ldots,s_m \in OT \cap PT\) with \(m \geq 2\), if \(s_{i+1} < s_i\) or \(s_{i+1} = s_i\) holds for any positive integer \(i < m\), then \(s_1 \oplus \cdots \oplus s_m \in OT\).)

A term in \(T\) is said to be of standard form if it belongs to \(OT\).

In order to verify the well-foundedness of \(<\) restricted to \(OT\), I define an ordinal \(o(s)\) for an \(s \in T\) in the following recursive way:

1. If \(s = 0\), then \(o(s) = 0\).
2. If \(s = \Omega\), then \(o(s) = \omega_1\).
3. If there is an \(s' \in T\) such that \(s = D(s')\), then \(o(s) = \psi(o(s'))\).
4. If there are an \(s_1 \in PT\) and an \(s_2 \in T\) such that \(s = s_1 \oplus s_2\), then \(o(s) = o(s_1) + o(s_2)\).

Be careful that this recursion is not a transfinite recursion with respect to \(<\), but a transfinite recursion with respect to the tree structure on the syntax of \(T\) (or the length of strings). Indeed, since I have not verified the well-foundedness of \(<\) yet, using a transfinite recursion with respect to \(<\) in the definition of \(o\), which will be used to show the well-foundedness of \(<\) causes a critical circular logic. I also used transfinite recursions with respect to the tree structure (or the length) in the definitions of \(OT\) and \(<\). If you could not understand this remark, you might not sufficiently understand the notion of a recursive definition for strings. Then please consider why \(OT\) and \(<\) are actually recursively defined.

As a result, by the recursive definitions of \(\psi\) and \(OT\), \(s < t\) and \(o(s) \in o(t)\) are equivalent to each other for any \(s,t \in OT\). Therefore the well-foundedness of \(\in\) implies the well-foundedness of the restriction of \(<\) to \(OT\).

---

Thus I have directly defined a notation system \(T\) associated to an OCF, and a (primitive) recursive interpretation \(<\) of \(\in\) so that \((OT,<)\) forms an ordinal notation system. One of the most difficult things to understand might be why I defined \(OT\) and \(<\) in that way. In order to find the way, I tried the following steps in my mind:

1. I define an expression of ordinals by using (not necessarily descending-ordered) \(+\) and \(\psi\), and the notion of a normal form as an interpretation of the descending order of \(+\) in expressions in a recursive way.
2. I described \(\in\) by using relations of variables in \(+\) and \(\psi\) restricted to normal forms, and define \(<\) on \(T\) by interpreting the description into a recursive relation on strings. (Be careful that since the canonical expression of an ordinal corresponding to terms in \(T\) is not necessarily of normal form, \(s < t\) and \(o(s) \in o(t)\) are not equivalent to each other under this interpretation.)
3. I interpret the recursive property whether a given expression of an ordinal is of normal form or not into a recursive property on strings through \(o\), and define \(OT \subset T\) as the recursive subset of terms satisfying the interpretation.

Now you understand that defining an ordinal notation is not so trivial even if you already have an OCF. Nevertheless, many googologists state "I constructed a new ordinal notation!" even though they only have OCFs or weaker systems.

Strength

I need to add an explanation of what the strength of an ordinal notation \((OT,<)\) is. Almost all ordinal notations are constructed by using an OCF. and then we have a canonical map \(o\) as explained above. Be careful. The strength of \((OT,<)\) is not the limit of \(o(a)\)'s, but is the ordinal type of \((OT,<)\). Also, the strength of the segment \((\{b \in OT \mid b < a\},<)\) of \((OT,<)\) below \(a \in OT\) is not necessarily \(o(a)\) or \(\sup_{b < a} o(b)\), but is the ordinal type of the segment.

For example, consider the ordinal notation below:

ordinal term \(a\)	\(0\)	\(00\)	\(000\)	\(0000\)	\(00000\)	\(000000\)	\(0000000\)	\(\cdots\)
ordinal \(o(a)\)	\(0\)	\(\varepsilon_0\)	\(\varepsilon_0 \times 2\)	\(\varepsilon_0 \times 3\)	\(\varepsilon_0 \times 4\)	\(\varepsilon_0 \times 5\)	\(\varepsilon_0 \times 6\)	\(\cdots\)

The order \(<\) associated to \((o,\in)\) is just the comparison of the length, and hence the strength of \((OT,<)\) is \(\omega\), but not \(\varepsilon_0 \times \omega\).

In order to ensure that the strength of \((OT,<)\) is actually the limit of \(o(a)\)'s, we need to show that \(o\) gives a one-to-one correspondence to the limit. Recall that when we use cardinals, the limit obviously goes beyond \(\omega_1\), and hence is not bijective with a countable set \(OT\).

We often consider a segment of \((OT,<)\). Suppose that \(o(W) = \Omega\) for some \(W \in OT\). By the reason above, the strength of the segment below \(W\) is not \(\Omega\). Then you may expect that the strength of the segment below \(a \in OT\) is actually the limit of \(o(b)\)'s with \(b < a\). As I said above, it is also incorrect. Look at the table above again. The limit of \(o(b)\)'s with \(b < 000\) is \(\varepsilon_0\), but the ordinal type of the segment is just \(2\).

As a consequence, the limit of values of \(o\) is not necessarily the strength of the segment. At least, only when you proved that \(o\) gives a one-to-one correspondence between the segment below \(a\) and the limit of \(o(b)\)'s with \(b < a\), the strength coincides with the limit.

Remember that we used \(C_{\kappa}^0\) in the construction of an OCF. If \(C_{\kappa}^0\) contains a large ordinal \(\gamma\) as a subset, then values of \(\psi_{\kappa}\) always go beyond \(\gamma\). Then the system loses the presentability of ordinals by expressions of normal form using \(\psi\)'s. As a result, \(o\) enjoys awfully many skippings below \(\Omega_1\). Then the strength of \((OT,<)\) is seriously reduced, because \(o\) does not give a one-to-one correspondence between a segment and the limit.

Therefore in order to ensure the strength of \((OT,<)\), we need to be very careful to control the growth of an OCF, so that \(o\) spreads ordinal terms into sufficiently large countable ordinals without skippings. Also, this tells us why defining the notion of normal form is so useful to define an ordinal notation. If we have a canonical way to express sufficiently large countable ordinals, then it automatically ensures that \(o\) is surjective onto those.

Other Structures

Given an ordinal notation system \((OT,<)\), you can define a map \(o_{(OT,<)}\) just by assigning each \(s \in OT\) to the ordinal type of the segment below \(s\) as I explained above. Therefore, an ordinal notation system canonically forms a notation with a correspondence to ordinals.

For the purpose to apply FGH, it is better to equip a system of fundamental sequences with an ordinal notation system. If whether a term is successor or not can be determined in a recursive way, you can define a fundamental sequence of each non-zero limit term \(a\) by recursively numbering all terms and setting \(a[n]\) as the \(n\)-th successor of the greatest term below \(a\) which is zero or whose corresponding number is smaller than \(n\) with respect to the fixed numbering.

We note that this method works even when the numbering is a finitely multi-valued, and depends on \(a\). In other words, given a recursive map \begin{eqnarray*} S \colon OT \times \mathbb{N} & \to & \textrm{FinSub}(OT) \setminus \{\emptyset\} \\ (a,n) & \mapsto & S_{a,n} \end{eqnarray*} with \(\{a' \in OT \mid a' < a\} \subset \bigcup_{n \in \mathbb{N}} S_{a,n}\), where \(\textrm{FinSub}(OT)\) denotes the set of finite subsets of \(OT\), we can define a recursive system of fundamental sequence for \(OT\) as \begin{eqnarray*} [] \colon OT \times \mathbb{N} & \to & OT \\ (a,n) & \mapsto & a[n] := \max \{a' \in OT \mid a' < a \land a' \in S_{a,n}\} \end{eqnarray*} under a mild assumption which ensures that \(a[n]\) is strictly increasing on \(n \in \mathbb{N}\) for any \(a \in OT\) corresponding to a limit ordinal.

For example, a norm function gives a typical exmaple of such an \(S\). We can construct a norm function using the length map \(\textrm{Lng} \colon OT \to \mathbb{N}\), if it makes sense, i.e. the length of an expression is not ambiguous. The resulting map \(S\) is given as \begin{eqnarray*} OT \times \mathbb{N} & \to & \textrm{FinSub}(OT) \setminus \{\emptyset\} \\ (a,n) & \mapsto & \{a' \in OT \mid \textrm{Lng}(a') \leq \textrm{Lng}(a) + Nn\} \end{eqnarray*} for a constant \(N \in [1,\infty)\) under a mild condition. For example, I defined a recursive system of fundamental sequences for a side nesting notation here.

Of course, this construction of a system of fundamental sequences is not so intuitive that we can handle easily. Therefore it is better to define a system of fundamental sequences in more intuitive ways.

A similar construction works for an OCF, if we do not care about the computability of the resulting FGH. For example, I defined a system of fundamental sequences for an OCF based on a large cardinal given by applying \(\omega\) times the Mahlo operator for the class of weakly compact cardinals here.

Notation with a Correspondence to Ordinals

It is a pair \((OT,o)\) of a set of \(OT\) of formal strings and a map \(o\) which assigns each \(s \in OT\) to an ordinal. Many googologists are confounding it with an ordinal notation system, but these two notions are completely different to each other.

Purpose

Unlike an ordinal notation, a notation with a correspondence to ordinals does not necessarily yield a computable large function. FGH? No way! If you do not have a surjectivity of \(o\), then FGH does not work even if you fixed a system of fundamental sequences. Of course, creating a notation with a correspondence itself is attractive for other purposes. For example, we can shortly express a known ordinal.

I emphasise that I do not mean that it is impossible to create a computable large function using a notation with a correspondence to ordinals. I just meant a simple application of the FGH construction does not necessarily work.For example, my notation with a correspondence to ordinals and a system of fundamental sequences introduced in my Japanese blog post yields a computable large function, even though it is not derived from an ordinal notation system. A summary of the resulting computatble large function is available here.

At least, you need careful arguments on specific system of fundamental sequences containing transfinite inductions along specific strict well-orderings in order to define a computable large function using a notation with a correspondence to ordinals. Therefore if you stated "Since I defined a notation of ordinals, I can create a computable large function by FGH", then it would be completely incorrect.

Relation to an Ordinal Notation

An ordinal notation system \((OT,<)\) canonically forms a notation with a correspondence \(o_{(OT,<)}\) to ordinals. On the other hand, a notation system \(OT\) with a correspondence \(o\) to ordinals is not necessarily derived from an ordinal notation, i.e. there does not necessarily exists a (primitive) recursive strict well-ordering \(<\) on \(OT\) with \(o = o_{(OT,<)}\) does . For example, forgetting the strict well-ordering \(<\) from the notation system \((OT,<,o)\) above, you obtain a notation system with a correspondence to ordinals. Since the map \(o\) is not surjective onto \(\varepsilon_0 \times \omega\), it is not derived from an ordinal notation.

If you want to regard it as an ordinal notation, you need to define a (primitive) recursive strict well-ordering \(<\) on \(OT\) satisfying \(o = o_{(OT,<)}\) in an explicit way. As I emphasised above, defining the relation \(s_0 < s_1\) as \(o(s_1) < o(s_2)\) does not work. It is not necessarily recursive, and \(o\) does not necessarily coincide with \(o_{(OT,<)}\).

Caution

Many googologists abbreviate \(o\). For example, if an \(s \in OT\) corresponding to an ordinal \(\alpha\), they often write \(s = \alpha\). Some of them just deleted \(o\) in order to type fast, but this abbreviation might cause beginner's confusion. Say, some others confound ordinals with symbols, and hence they regard the equality as a true relation.

Moreover, such an abbreviation might cause serious errors in the definition of the system itself. Therefore I strongly recommend to distinguish the equality as formal strings and the equality of the image of \(o\).

UNOCF

UNOCF is a well-known but ill-defined system. It is not fully formalised. At least, it is not a map at all, and hence is not an OCF. One solution is to deal UNOCF as a notation (whose underlyiing set \(OT\) is just a finite set because of the finiteness of its defining table) with a correspondence to known ordinals. Then it is not an ordinal notation, either. Therefore it does not yield a new ordinal, or a new computable large function.

Notation with a System of Fundamental Sequences

It is a pair \((OT,[])\) of a set of \(OT\) of formal strings and a (primitive) recursive function \begin{eqnarray*} [] \colon OT \times \mathbb{N} & \to & OT \\ (s,n) & \mapsto & s[n] \end{eqnarray*} satisfying several desired properties. What are desired properties? I explain details in the next subsection.

Purpose

I would like to focus on two main reasons for googologists to define a notation with a system of fundamental sequences:

1. To generate a computable large number by applying FGH to it.
2. To express a recursive large ordinal through the notation.

In order to explain what conditions you need to assume for these purposes, I introduce terminology:

1. An \(s \in OT\) is said to be a zero if \(s = s[n]\) for any \(n \in \mathbb{N}\).
2. An \(s \in OT\) is said to be a successor if \(s \neq s[0] = s[n]\) for any \(n \in \mathbb{N}\).
3. An \(s \in OT\) is said to be a limit if \(s\) is not a successor.

For convenience, I would like to assume the following additinal conditions which helps us to determine whether an \(s \in OT\) is a successor or not:

1. For any \(s \in OT\), \(s = s[0]\) implies that \(s\) is a zero.
2. For any \(s \in OT\), \(s \neq s[0] = s[1]\) implies that \(s\) is a successor.

Now, it is time to consider what desired properties are.

To begin with, suppose that you want to generate a computable large number by applying FGH to it. For this purpose, you need to verify the termination of the resulting computable function. For this purpose, you need to construct a strict partial-ordering \(<\) on \(OT\) satisfying the following:

1. For any non-zero \(s \in OT\) and any \(n \in \mathbb{N}\), the relation \(s[n] < s\) holds.
2. The relation \(<\) is well-founded.

Otherwise, FGH does not work even if it is described as if it is "recursively defined". The resulting computable function might not terminate. It is not so difficult to define \(<\) satisfying the first condition, but is very difficult to ensure the second condition. How could you? There are essentially two solutions:

1. To create an ordinal notation \((OT,<)\) first, and define a system \([] \colon OT \times \mathbb{N} \to OT\) of fundamental sequences using the strict well-ordering itself such that for any non-zero \(s \in OT\) and any \(n \in \mathbb{N}\), the relation \(s[n] < s\) holds.
2. To create a map \(o \colon OT \to \textrm{On}\) such that for any non-zero \(s \in OT\) and any \(n \in \mathbb{N}\), the relation \(o(s[n]) \in o(s)\) holds.

In particular, you do not have to mind such a strict partial ordering if you have already acquired a well-defined ordinal notation or a well-defined correspondence to ordinals satisfying the condition above. But if you do not have, it is a serious problem.

Several googologists state "Do I need an ordinal notation? Ok. Since I defined a system of fundamental sequences, it expresses ordinals!" Wait. It is a serious circular logic. A system of fundamental sequence does not necessarily yield a structure of an ordinal notation, unless you have a desired strict partial ordering. Therefore it is impossible to use the resulting "ordinal notation" in order to define such a strict partial ordering. For more details, see the relation to an ordinal notation.

Several other googologists state "Since it is impossible for me to define an ordinal notation or a correspondence to ordinals, I just define a system of fundamental sequences. It is very strong, and yields a computable large function obviously larger than extensions of BEAF, BMS, DAN, and so on!" Wait. It is far from a solution. If you do not have a desired strict partial ordering, you have no evidence of the termination of FGH. Actually, there are many elementary counterexamples of a system of fundamental sequences (without such a desired strict partial ordering) such that FGH is ill-defined. Is that what you really want? Even though you have an analysis table with \(10000\) entries, it can never be an evidence of the termination because sufficiently complicated system of fundamental sequences might yield an infinite loop after \(10^{100}\) entries. Nevertheless, should we search for an explicit infinite loop in order to point out the absence of the evidence of the termination?

Next, suppose that you want to express a recursive large ordinal through the notation. Then you need a strict partial-ordering \(<\) on \(OT\) satisfying the same conditions above, too. For more details, see the relation to a notation with a correspondence to ordinals.

Several googologists state "Since it is impossible for me to define an ordinal notation or a correspondence to ordinals, I just define a system of fundamental sequences. It is very strong, and goes beyond any notations which I know!" Wait. As I wrote above, a system of fundamental sequences without a desired strict partial ordering does not necessarily express ordinals. In addition, even if you have a desired ordinal notation or a desired correspondence to ordinals, the notation with a system of fundamental system does not express ordinals beyond the expression limit of the stuff. Therefore, it is impossible for you to express all ordinals below a fixed ordinal beyond the limits of existing well-defined notations.

By the reason above, a notation with a system of fundamental sequence (without a proof of the specific property above) rarely yields a computable large function. On the other hand, an ordinal notation (NOT just a notation) with a fundamental sequence is great. By the well-foundedness of the ordering, it gives a well-defined FGH as long as the system of fundamental sequences satisfies the desired properties above. Such a system of fundamental sequences always exists by the construction here, and hence ordinal notation system is very useful in googology.

Of course, I do not mean that it is impossible to create a computable large function from a notation with fundamental sequences which is not equipped with a suitable well-founded partial ordering. As I wrote above, I created a computable large function using a notation with a correspondence to ordinals and a system of fundamental sequences.

At least, you need careful arguments containing transfinite inductions along specific desired strict partial orderings. Therefore if you stated "Since I defined a system of fundamental sequence, I can generate a computable large number by FGH" without such arguments, then the logic is completely incorrect.

Relation to an Ordinal Notation

An ordinal notation system \((OT,<)\) (canonically and non-canonically) forms a notation with a system of fundamental sequences. On the other hand, does it naturally form an ordinal notation system? For example, how about defining the relation \(s_0 < s_1\) by the property that there exists a finite sequence \((n_0,n_1,\ldots,n_k)\) of natural numbers satisfying \(s_0 = s_1[n_0][n_1] \cdots [n_k]\)? Unfortunately, the relation does not necessarily recursive, because the searching process does not necessarily terminates. On the other hand, if the relation is a strict total ordering as a result, then it is recursive. Therefore you need to show that the relation is a total ordering first. In order to verify it, you need to show the anti-symmetry, which is equivalent to the non-existence of an infinite loop, i.e. \(s \neq s[n_0][n_1] \cdots [n_k]\) for any non-zero \(s \in OT\) and any finite sequence \((n_0,n_1,\ldots,n_k)\) of natural numbers. We only have the following two generic strategies to verify the property:

1. Define another (not necessarily recursive) strict well-ordering \(\prec\) on \(OT\) satisfying \(s[n] \prec s\) for any \(s \in OT\) with \(s \neq z\) and any natural number \(n\).
2. Define a map \(f \colon OT \to OT'\) to another notation \(OT'\) with a system of fundamental sequences whose halting problem has already been solved satisfying that for any \(s \in OT\) and any natural number \(n\), there is a natural number \(n'\) with \(f(s[n]) = f(s)[n']\).

In the first strategy, you need a correspondence \(o\) to ordinals and an OCF compatible to your system in the sense that \([]\) actually gives the system of fundamental sequences of the image of \(o\). Then it would be better to define an ordinal notation from the beginning. Well, since you did not choose the way (you have created a notation with fundamental sequences but not an ordinal notation), I guess that you do not have such a compatible OCF.

In the second case, we need to use a known halting system. Therefore even if you can show the halting problem in this way, the resulting large function obtained by FGH seems not to go beyond a known one.

As a conclusion, if you could verify that \(<\) is a strict well-ordering, then your function does not grow so fast unless you are a set theorist who can create a new OCF. Therefore defining \(<\) in this way is not a good strategy for the use of googology. Instead, it is better to define \(<\) in another distinct way, and to verify the two properties which I listed here.

Relation to a Notation with a Correspondence to Ordinals

Let \((OT,[])\) be a notation with a system of fundamental sequences satisfying several desired properties. Then does the following "recursive definition" of a map \(o \colon OT \to \textrm{On}, \ s \mapsto o(s)\) work?

1. If \(s\) is a zero, then \(o(s) := 0\).
2. If \(s\) is a successor, then \(o(s) := o(s[0]) + 1\).
3. If \(s\) is a non-zero limit, then \(o(s) := \sup_{n \in \mathbb{N}} o(s[n])\).

The answer depends on what "desired" properties are. If you have a partial well-ordering on \(OT\) satisfying desired properties explained in the beginning of this section. then \(o\) is well-defined. Otherwise, \(o\) might be ill-defined. Actually, there are many elementary counterexamples. Several googologists state "Of course, I have a desired partial ordering defined by \(s < t \Leftrightarrow o(s) \in o(t)\)." Wait. It is a circular logic. You need a desired partial ordering in order to verify the well-definedness of \(o\), and hence defining a partial ordering using \(o\) itself is obviously invalid for this purpose.

For example, if \((OT,[])\) forms a tree in the sense explained here, then the binary relation \(<\) defined in the previous section forms a well-founded strict partial orderring, and hence the transfinite induction along \(<\) proves the well-definedness of \(o\). Therefore the "corresponding ordinal" always makes sense as long as we assume that \((OT,[])\) forms a tree. Of course, it is quite difficult to show that \((OT,[])\) forms a tree. Needless to say, using the well-foundedness of \(o\) in the proof that \((OT,[])\) forms a tree is an obvious circular logic, because we used the assumption that \((OT,[])\) forms a tree in order to ensure the well-definedness of \(o\).

Caution

The system of fundamental sequences should be defined as a map \(OT \times \mathbb{N} \to OT\), but not a function symbol which is used in order to define \(OT\). The following is a bad example:

1. Every natural number \(n\) belongs to \(OT\).
2. For any integer \(n > 1\) and any finite sequence \(s_0,\ldots,s_{n-1}\) of length \(n\) in \(OT\), \(s_0 + \cdots + s_{n-1}\) belongs to \(OT\).
3. For any \(s \in OT\), \(\omega^s\) belongs to \(OT\).
4. For any \(s \in OT\) and any natural number \(n\), if \(s\) is expressed as \(\omega^t\) for some \(t \in OT\), then \(s[n]\) belongs to \(OT\).
5. For any \(s \in OT\) and any natural number \(n\), if \(s\) is the sum of a finite sequence of length \(> 1\) whose rightmost entry is expressed as \(\omega^t\) for some \(t \in OT\), then \(s[n]\) belongs to \(OT\).

You might regard \((s[0],s[1],s[2],\ldots)\) as a fundamental sequence of \(s\), it does not work because they are just formal strings.

For example, you might add the follwing "rules":

1. For any \(s \in OT\) and any natural number \(n\), \(\omega^{s + 1}[n] = \underbrace{\omega^s + \cdots + \omega^s}_n\).
2. For any \(s \in OT\) and any natural number \(n\) such that \(s[n]\) is defined, \(\omega^s[n] = \omega^{s[n]}\).

They do not work, because the equalities are false. Both hand sides are just formal strings, and hence the equalities hold only when they coincide with each other as formal strings. If you want to state the coincidence of the "corresponding values as ordinals" in your mind, you need to define a correspondence \(o\) in a recursive way so that the following rules actually hold:

1. For any \(s \in OT\) and any natural number \(n\), \(o(\omega^{s + 1}[n]) = o \left( \underbrace{\omega^s + \cdots + \omega^s}_n \right)\).
2. For any \(s \in OT\) and any natural number \(n\) such that \(s[n]\) is defined, \(o(\omega^s[n]) = o(\omega^{s[n]})\).

The abbreviation of \(o\) is quite harmful as long as you deal with equalities of distinct formal strings. For more details, see the explanation here.

System of Fundamental Sequences for Ordinals

It is a map which assigns an ordinal \(\beta[n]\) to each pair \((\beta,n)\) of an ordinal \(\beta\) below a fixed ordinal \(\alpha\) and an ordinal \(n\) below the cofinality of \(\beta\) satisfying similar conditions above.

Purpose

We want a large number!

Constructing a large countable ordinal below \(\alpha\) is not sufficient. We also need a system of fundamental sequences for ordinals below \(\alpha\) in oder to define (possibly uncomputable) large functions through FGH for ordinals below \(\alpha \cap \omega_1\).

Relation to a notation

A system of fundamental sequences for ordinals below \(\alpha\) naturally corresponds to a notation with a correspondence to ordinals in the case where \(\alpha \subset \omega_1\). Namely, the identity map forms a correspondence to ordinals.

On the other hand, a notation with a system of fundamental sequences in the sense above is required to be recursively defined. Therefore a system of fundamental sequences for ordinals below \(\alpha\) does not necessarily corresponds to a notation with a system of fundamental sequences even if we assume \(alpha \subset \omega_1\).

Caution

If you want to define a computable large number, you need to interpret a system of fundamental sequences for ordinals into a notation with a system of fundamental sequences. Otherwise, the resulting large function is uncomputable unless you only use finite ordinals, because Turing machines are unable to deal with actual infinities.

Also, "defining" a system of fundamental sequences by using expressions without defining appropriate normal forms does not make sense by the same reason as why "defining" OCFs by using expressions without defining appropriate normal forms does not make sense explained here.

One example is the following rule to "define" a system of fundamental sequences:

• For any non-zero countable limit ordinal \(\beta\) and any strictly increasing continuous function \(f\), the fundamental sequence \((f(\beta)[n])_{n=0}^{\infty}\) is defined as \((f(\beta[n]))_{n=0}^{\infty}\).

Since it is impossible to reconstruct \(f\) and \(\beta\) from the ordinal \(\gamma\) expressed as \(f(\beta)\), the use of \(f\) and \((\beta[n])_{n=0}^{\infty}\) in the definition of \((\gamma[n])_{n=0}^{\infty}\) is completely invalid.

Another example is the following rule to "define" of a system of fundamental sequences below \(\varepsilon_0\), which does not work:

1. \((\alpha + \beta)[n] := \alpha + (\beta[n])\) for any ordinal \(\alpha\) and any non-zero limit ordinal \(\beta\)
2. \((\alpha \times \beta)[n] := \alpha \times (\beta[n])\) for any ordinal \(\alpha\) and any non-zero limit ordinal \(\beta\)
3. \(\omega[n] = n\)
4. \(\omega^{\alpha + 1}[n] = \omega^{\alpha} \times n\) for any ordinal \(\alpha\)
5. \(\omega^{\alpha}[n] = \omega^{\alpha[n]}\) for any non-zero limit ordinal \(\alpha\)

Since the right hand sides heavily depend on the non-canonical expressions of the left hand sides, which are not necessarily unique, the system is completely ill-defined. In order to avoid such a problem derived from the non-uniqueness, we usually restrict expressions to Cantor normal forms. Similarly, when you use expressions of ordinals by functions such as operators, Veblen functions, and OCFs, then you need to define the notion of a normal form which gives you a unique way to express a given ordinal by them.

Of course, if you want to define a recursive system of fundamental sequences, the notion of a normal form should also be defined in a recursive way. Although googologists often forget to set normal forms, this is one of the most important and the most difficult steps to study a recursive system of fundamental sequences by the same reason explained here.