Talk: Ordinal notation

Anyone know why the definition of \(C(\alpha, \beta)\) starts with \(n = 1\) and not 0? FB100Z • talk • contribs 09:32, December 8, 2013 (UTC)

That doesn't change the definition, as \(C_0(\alpha, \beta)\) is subset of \(C_1(\alpha, \beta)\), but I think definition will look nicier if we take union over all these sets. LittlePeng9 (talk) 21:31, December 8, 2013 (UTC)

But \(\vartheta(1) = \zeta_0\) Wythagoras (talk) 06:15, March 27, 2014 (UTC)

has anyone managed to locate the source for weiermann's \(\vartheta\) in the final section? it's vel time 01:34, September 22, 2014 (UTC)

note to self: [1] it's vel time 01:46, September 22, 2014 (UTC)

The version of Taranovsky's C that is shown in the page is not the strong one. The strong version is defined on comparisons. {hyp/^,cos} (talk) 09:55, October 9, 2014 (UTC)

Why Feferman's \(\theta\) function has limit ordinal "N/A"? {hyp/^,cos} (talk) 10:00, December 3, 2014 (UTC)

Because I was not able to find its limit in my sources. I doubt that it is an unsolved problem, just one with an answer I haven't found yet. it's vel time 15:26, December 3, 2014 (UTC)

Extended veblen function[]

Okay so the paper is here and I'm very confused on a few things...

what does rule C mean? i think it has to do with enumerating functions
why are people saying \(\phi(1, 0, 0) = \Gamma_0\) when zeros don't even seem to be allowed?
why is the \(\phi_\alpha(\beta)\) called the Veblen function when it doesn't look at all like what we see here?

it's vel time 17:05, October 12, 2014 (UTC)

It's kind of like the situation with the Ackermann function, whcih generally refers to a specific function that is different from Ackermann's original construction. Ackermann's original construction is more complicated than need be, and Veblen's original Veblen function seems rather poor, actually. I think it's better to start from 0, and to have it so that adding or removing entries of value 0 don't change the value of the function, which are properties of the modern construction. Deedlit11 (talk) 17:27, October 12, 2014 (UTC)

Theta function[]

It's actually defined here up to BHO. Ikosarakt1 (talk ^ contribs) 05:17, February 12, 2015 (UTC)

Klammersymbole[]

JACKPOT. I found Schütte's original paper. -- v e l! 15:10, March 10, 2015 (UTC)

Hm, looks interesting. I can help you with the translation, if you want, but not now. Wythagoras (talk) 19:41, March 10, 2015 (UTC)

Page 20 of http://www.cs.man.ac.uk/~hsimmons/TEMP/OrdNotes.pdf has an english translation, but it might not be an exact description -- v e l! 23:33, March 10, 2015 (UTC)

Stegert's notation[]

What's the definition? And how strong is it? {hyp/^,cos} (talk) 23:53, May 3, 2015 (UTC)

¯\_(ツ)_/¯ -- v e l! 03:47, May 4, 2015 (UTC)

Where have you heard of it? LittlePeng9 (talk) 04:17, May 4, 2015 (UTC)

Stegert's dissertation, which is way too advanced for me to work through. -- v e l! 05:29, May 4, 2015 (UTC)

Oh, it's too difficult for me to understand the dissertation and find the definition and strength. {hyp/^,cos} (talk) 13:02, May 4, 2015 (UTC)

I can work through it but it'll take a lot of time and patience -- v e l! 01:12, May 5, 2015 (UTC)

Confusing[]

This is sooo confusing: for example, look at here: http://googology.wikia.com/wiki/Large_Veblen_ordinal

Wich "Psi" function? There is lot of them! Most of articles on huge ordinals doesn't precise wich notation is used, and that confuse me a lot Fluoroantimonic Acid (talk) 11:54, June 30, 2015 (UTC)

I'm not sure if there is a single user on the wiki who knows what psi and theta functions are used all over the articles... LittlePeng9 (talk) 12:11, June 30, 2015 (UTC)

Rathjen's notation[]

We'd need a ruleset for the Rathjen's psi collapsing functions right in this article. I don't know its definition well enough, could someone help? ;A; Fluoroantimonic Acid (talk) 09:21, October 20, 2015 (UTC)

Out of curiosity, why is it easier to manage values in Rathjen's notation if it is defined with two collapsing functions instead of one? Deedlit11 (talk) 00:18, May 17, 2016 (UTC)

Intuitively speaking, the notation works a lot 'smoother', as we don't need to simultaneously manage \(\psi_\pi(\alpha)\) for \(\alpha\geq\text M\), which then feeds back into the function and makes it more difficult to make exact relations. We could just restrict \(\psi_\pi\) to values \(<\text M\), as done in the original text, but this also makes the definition of \(\chi\) more opaque. In addition, it becomes harder to prove that the behavior of \(\chi\) goes long the hyper-inaccessible hierarchy with the addition of the \(\psi_\pi\) functions to the definition - I think it's a lot more intuitively understandable with \9\chi\), at the least, defined separately.

Case in point: me and another wiki user were discussing the behavior of the ordinals leading up to the PTO of KPM in relation to Hollom's new notation, and they claimed that the behavior of the \(\chi\) function doesn't work like that of the \(\psi_\pi\) functions, as we both completely missed that the definition of \(\psi_\pi\) had a restriction on \(\chi_\mu\), which made us both (afaik) think that \(\psi_{\omega_1}(\chi_{\Gamma_{\text M+1}}(0))=\psi_{\omega_1}(\text M)\). Separating this into two collapsing functions, although not strictly necessary, removes much of this apparent opacity in the definitions. ~εmli 09:18, May 17, 2016 (UTC)

Comparing Veblen and Feferman[]

In Ferermen's \(\theta\), it is written that for countable arguments, \(\theta_\alpha(\beta) = \varphi_\alpha(\beta)\). Is it true for \(\alpha = \Gamma_1\)?

Obviously \(\theta_{\Gamma_1}(0) = \Gamma_0\). However normally \(\varphi_{\Gamma_1}(0) = \Gamma_1\). Therefore I think it is different.

I think that Veblen function can be written as

\begin{eqnarray*} C_0(\alpha, \beta) &=& \beta \cup \{0\}\\ C_{n+1}(\alpha, \beta) &=& \{\gamma + \delta, \varphi_\xi(\eta) | \gamma, \delta, \eta \in C_n(\alpha, \beta); \xi < \alpha\} \\ C(\alpha, \beta) &=& \bigcup_{n < \omega} C_n (\alpha, \beta) \\ \varphi_\alpha(\beta) &=& \min\{\gamma | \gamma \not\in C(\alpha, \gamma) \wedge \forall \delta < \beta: \varphi_\alpha(\delta) < \gamma\} \\ \end{eqnarray*}

Definition of the Ferman's \(\theta\) is different from the Veblen's function in 2 ways.

Including the uncountables
Imposing \(\xi \in C_n(\alpha, \beta)\) in the definition of \(C_{n+1}(\alpha, \beta)\)

The first point is irrelevant in the countable arguments. The second point restricts the \(\theta\) function to grow no further than \(\Gamma_0\) below \(\Omega\), which is very important for making the collapsing mechanism to work. 🐟 Fish fish fish ... 🐠 18:47, May 13, 2018 (UTC)

As no one opposes, I corrected the text. 🐟 Fish fish fish ... 🐠 12:59, May 17, 2018 (UTC)

Proposal to separate the article into two[]

We have so many ordinal collapsing functions in the article, while there is no main article focussing on ordinal collapsing functions. I think that it is better to create a new article on ordinal collapsing functions, and move the related contents in the article of ordinal notations to the new article. If nobody disagrees with it, I will do it. Please give me opinions.

p-adic 01:27, December 26, 2019 (UTC)

Yes, I think it's reasonable. Triakula (talk) 05:02, December 26, 2019 (UTC)

Thank you. I will wait a week for other opinions.

p-adic 05:53, December 26, 2019 (UTC)

Now a week has passed. I will separare the article into two later.

p-adic 07:15, January 4, 2020 (UTC)

Cantor's Attic[]

Is the site inaccessible? If so, I will tag the web page as dead link. ARsygo (talk) 00:51, June 25, 2020 (UTC)

Right. Since we have many articles based on descriptions in Cantor's Attic, we need to fix many articles...

p-adic 01:10, June 25, 2020 (UTC)

Conjecture about Arai's and Stegert's[]

I conjecture that the recursive limit of Arai's OCF using reflecting ordinals is smaller than the countable limit of Stegert's first OCF C7X (talk) 02:04, 2 November 2020 (UTC)

Please share a theoretic reasoning. Otherwise, one person can state that Arai's one is bigger, and another personal can state that Stegert's one is bigger. If the comparison will be solved, then either one of the two will win. It does not have much meanings.

p-adic 02:10, 2 November 2020 (UTC)

In the original conjecture I meant to say "smaller or equal". I don't have a formal reason or proof that supports this conjecture, but I remember that Alwe said that some properties of ordinals such as "weakly compact and stationary on weakly compacts" are definable in Stegert's OCF, but their recursive analogues (e.g. ordinals that are "Π₃-rfl. and Π₂-rfl. on set of &Pi:₃-rfl. ordinals below") aren't definable in Arai's OCF. I assume that less definability for complicated structures likely means that the limit is less or equal, but I don't have a formal proof. C7X (talk) 02:38, 2 November 2020 (UTC)

The notion of the definability of a predicate in a structure heavily depends on a theory which the structure models. What theory are you considering? The theory of posets? (An OCF is not astructure, and hence I assumed that you are talking about an associated ordinal notaion.) In that case, how could you interprete the properties of non-recursive ordinals into predicates on terms in an ordinal notation? If you do not fix the interpretation, the definability does not make sense, either. Or are you using another formulation of the definability? Then could you tell me what the definability means in your context?

p-adic 02:49, 2 November 2020 (UTC)

I must have used ambiguous terminology in my last edit. I didn't mean a structure either, so here is an attempt of a formalization:

A predicate \(\phi\) on \(\textrm{Ord}\) is "definable in Arai's OCF" iff \(\exists(l,k\in\mathbb{N})\exists(\vec\xi\in\textrm{Ord}^l)(\textrm{min}(Mh_k(\vec\xi))=\textrm{min}(\{\alpha:\phi(\alpha)\})\)
WIP

C7X (talk) 05:13, 2 November 2020 (UTC)

Strength and ordinal analysis[]

Here Taranovsky notes that the system for BHO mimics the quantifiers of some sort of induction (I don't know) for KP and that also the system for ε₀ does the same with induction in PA. How does this apply to other notations? For example, can BM4 or main system TON be shown to correspond to some sort of induction? C7X (talk) 18:56, 18 February 2021 (UTC)

Edit: It seems that my guess I made in my previous comment was "ordinal notations are strong because they have similar structure to strong schema in set theories", but the converse "some schemata in set theories are strong because they have similar structure to strong ordinal notations" seems to be more of the case (either way I don't know)

Pull-buck[]

> unless the pull-buck of the ∈-relation is verified to be primitive recursive

What is a pull-buck of a relation, is it terminology for the interpretation of ∈ in the scope of the ordinal notation? C7X (talk) 03:39, 15 March 2021 (UTC)

Given a map f:M→N and a binary relation < on N, the pull-back of < by f is the binary relation f^*<on M defined as m_0 f*< m_1 ⇔ f(m_0) < f(m_1). (The terminology is not special in ordinal notations, but is widely used in mathematics in various situations.)

p-adic 04:31, 15 March 2021 (UTC)

I uodated the article. By the way, I added a link to my blog post in order to help readers to avoid common misconceptions. Although my blog post is not a valid source of the mathematical description, it is a valid source that I pointed out the common misconceptions, if I correctly understand the policy. (The policy dies not prohibids to refer to a blog post if the cited information is not on a name of something.)

p-adic 04:46, 15 March 2021 (UTC)

Technical complexity of Arai's OCF[]

Why does Arai use sequences of ordinals in CNF with base Λ to encode structure of reflecting ordinals? To my knowledge Taranovsky's system from "Degrees of Reflection with O being CNF with base Ω" is easier to work with and encodes a structure of reflection no weaker than Arai's structure. Is there a proof-theoretical consideration that prevents Taranovsky's approach from working here? C7X (talk) 20:18, 22 April 2021 (UTC)

I am sorry if I misunderstand, but Ω in TON is not ω_1. Usually. CNF for ω_1 is not effective in a construction of ordinal notation beyond ε_0, while CNF for a large cardinal is useful to describe a hierarchy of cardinals with respect to some degree structure (in terms of Taranovsky) or level structure (in terms of Rathjen). My 三関数 and 二関数 also use recursive analogues of CNF for a large cardinal by the reason.

p-adic 22:42, 22 April 2021 (UTC)

> Ω in TON is not ω_1

Unless I misunderstand what you wrote, any mention of Ω in my first message meant Taranovsky's constant term symbol.

> while CNF for a large cardinal is useful to describe a hierarchy of cardinals with respect to some degree structure (in terms of Taranovsky)

I agree with this, in this case I was thinking of using \(\Lambda\) as the basis to form a degree structure above \(\mathbb K\), which seems superficially simpler than Arai's approach based on sequences of ordinals. I was wondering if there was a reason why Arai didn't take this simpler approach.

> Usually. CNF for ω_1 is not effective in a construction of ordinal notation beyond ε_0

What about an ordinal notation such as one associated to Bachmann's ψ? Even if one isn't explicitly published, I can't imagine a way to make an ordinal notation associated to Bachmann's ψ that isn't either stronger than \(\varepsilon_0\) or doesn't use CNF for ω₁ (CNF with base ω₁ would be a different but similar matter) C7X (talk) 23:22, 22 April 2021 (UTC)

> Unless I misunderstand what you wrote, any mention of Ω in my first message meant Taranovsky's constant term symbol.

Then I misunderstood your intention. What I am not understanding is how you could compare a "CNF" for a constant term symbol with an actual CNF for an ordinal Λ. Generally speaking, it is really difficult to encode NF for a fixed sufficently large base, and hence we cannot freely use CNF.

> I was wondering if there was a reason why Arai didn't take this simpler approach.

Could you tell me the detail of the approach? For example, given an actual ordinal α, is there a way to express α using some constant term symbol Ω?

One of the most important benefits to use ordinals instead of formal symbols is that it automatically provides the well-foundedness of the corresponding notation system. For if you do not have a "recursive" method to express an ordinal in terms of formal strings, we lose the provability of the well-foundedness. On the other hand, if we work in ordinals and expressions based on ordinal arithmetic, then we frequently obtain a well-founded notation.

Of course, we can label formal strings by names of reflection properties. However, since the symbols themselves are irrelevant to actual ordinals unless we explicitly define an OCF corresponding to the labeling, the labeling is just a table of names irrelevant to actual strength. Indeed, we can label formal strings in our own notation system by name of reflection properties, but the resulting system can be ill-founded. Therefore your phrase "encodes a structure of reflection no weaker than Arai's structure" is a little confusing for me. (I know that Taranovsky gave ways to label terms in various TONs by names of reflections, but it does not mean that all of TONs give OCFs based on reflections. Therefore the situation is different from that for ordinal notations asssociated to OCFs based on reflection properties.)

> What about an ordinal notation such as one associated to Bachmann's ψ?

Sorry for the ambiguity. If an OCF directly uses powers of ω_1 and there is no greater cardinal in standard expressions, then it is natural to use CNF for ω_1.

p-adic 01:16, 23 April 2021 (UTC)

> Generally speaking, it is really difficult to encode NF for a fixed sufficently large base, and hence we cannot freely use CNF.

This was my mistake, Taranovsky didn't necessarily use CNF base Ω if O is CNF. He wrote text such as "Ω^{Ω^Ω}" as a shorthand for other terms, for this example C(C(C(C(Ω,Ω),Ω),Ω),Ω) (as you have mentioned, Taranovsky often uses semantic language for syntactic objects)

> One of the most important benefits to use ordinals instead of formal symbols is that it automatically provides the well-foundedness of the corresponding notation system.

Does this mean that a degree structure using set-theoretic ordinals is necessarily well-founded as well?

> What I am not understanding is how you could compare a "CNF" for a constant term symbol with an actual CNF for an ordinal Λ.

> given an actual ordinal α, is there a way to express α using some constant term symbol Ω?

Although Taranovsky uses "Ω" as a constant term symbol while Arai uses Λ as a set-theoretic ordinal, I am using Λ as a set-theoretic ordinal that behaves similarly in some ways to the constant term symbol "Ω" behaves in Taranovsky's notation. One example of such similar behavior is the formation of a degree structure, however "Ω" forms this by being enclosed in formal strings which are compared lexicographically, while Λ may form this in a (not necessarily computable) way by closure under some set-theoretic ordinal functions. I am comparing behavior not by directly comparing the set-theoretic ordinals and formal strings, but by examining richness of the resulting structure on either side. Is this a correct way to compare notions?

> Could you tell me the detail of the approach?

Before I explain details of my idea, I think I realized why Arai didn't use a DoR-like degree structure, as it could cause proof-theoretic concerns: there are two ways to do this for \(\Pi_N\)-reflection, which are either:

Limit the exponentiation with base \(\Lambda\) in degrees to towers of height at most \(N-2\), remove the constant \(\mathbb K\), and include an extra constant \(\Upsilon>\Lambda\). \(\Upsilon\) may be hard to deal with proof-theoretically, but IDK enough proof theory to tell
Limit the exponentiation with base \(\Lambda\) in degrees to towers of height at most \(N-2\) but with topmost exponent \(<\Lambda\), and include the constant \(\mathbb K\). Even though this doesn't require larger structure, proving well-foundedness of the degree structure would require induction along exponential orderings of height \(>N-3\), which may cause problems (see Iterating the recursively Mahlo operations, Arai2010). These concerns may have no point as Arai has already used exponential towers with base above \(\Lambda\) in the original anyway.

However, if we were to proceed, details of my idea would be similar to as follows. If \(d\) is a degree, the following conditions should characterize the ordinals \(\psi^d_\pi(\alpha)\):

\(d=0\) would represent singularity
\(d=1\) would represent uncountable regularity
\(d=2\) would represent Mahloness
\(d=3\) would represent 1-Mahlo
From here we must make a choice.
- If we follow a more Taranovsky-like way:
  - \(d=\omega\) would represent for all \(n\in\omega\), being a limit of n-Mahlo cardinals below
  - \(d=\omega+1\) would represent ω-Mahloness
  - \(d=\omega2\) would represent for all \(n\in\omega2\), being a limit of n-Mahlo cardinals below
  - \(d=\omega2+1\) would represent ω2-Mahloness
- If we follow a more Buchholz's-Mahlo-OCF-like way:
  - \(d=\omega\) would represent \(\omega\)-Mahloness
  - \(d=\omega+1\) would represent \(\omega+1\)-Mahloness
  - \(d=\omega2\) would represent \(\omega2\)-Mahloness
Jumping ahead some, the notions converge on some of the following cases:
- \(d=\Lambda\) would represent weakly-compactness
- \(d=\Lambda+1\) would represent being stationary on weakly compacts below
- \(d=\Lambda+2\) would represent being stationary on "ordinals stationary on weakly compacts below" below
- \(d=\Lambda\times2\) would represent being weakly compact and stationary on weakly compacts below. I'm not sure how Arai's original OCF handles cases like these
- \(d=\Lambda^2\) would represent being \(\Pi_1^1\)-indesc. on \(\Pi_1^1\)-indesc. cardinals below
- \(d=\Lambda^\Lambda\) would represent being \(\Pi_2^1\)-indesc.
- \(d=\Lambda^{\Lambda^\Lambda}\) would represent being \(\Pi_3^1\)-indesc.

To formalize this, I would need to make a general definition, but I won't develop this specific idea further, because this OCF has issues preventing use in a proof-theoretic settings (AFAIK the original purpose of Arai's OCF). C7X (talk) 17:15, 23 April 2021 (UTC)

> Does this mean that a degree structure using set-theoretic ordinals is necessarily well-founded as well?

No. A degree structure just classifies terms or ordinals, and is not related to the well-foundedness. Therefore "encoding a degree structure" itself does not ensure the strength. This is the point.

For example, you can create a notation T whose terms are alphabetical words meaning reflection properties. Then by the definition, it encodes reflectin properties. However, the well-foundedness depends on how you define an ordering.

> Is this a correct way to compare notions?

If you are not interested in the strength, then it is one of a correct way. Similarly, you can compare Arai's notation with the T above without using an ordering.

> Limit the exponentiation with base Λ in degrees to towers of height at most N−2, remove the constant K, and include an extra constant

I am not certain about your intention. Do you intend a replacement like the one in Goodstein theorem?

> d = Λ×2

Then your system does not include the Λ-th iteration of Mahlo oeprator applied to the class of weakly compact cardinal, does't it? Then I guess that the resulting system does not work as you intend.

Instead of using CNF for Λ, it is better to use CNF for ε_{T+1}, where T is the Upsilon you used in the alteration. Another choice is to change two or more bases. (This is the base strategy of 二関数, which I call double CNF.)

p-adic 22:51, 23 April 2021 (UTC)

> the Λ-th iteration of Mahlo oeprator applied to the class of weakly compact cardinal

My understanding is that since α<β → "(predicate for the βth iteration of Mahlo operator) is a strict subset of (predicate for the αth iteration)", then the least ordinal in "the Λ-th iteration of Mahlo operator applied to the class of weakly compact cardinals" would be a Mahlo cardinal larger than Λ, which is beyond my intention for this concept.

> Therefore "encoding a degree structure" itself does not ensure the strength.

> If you are not interested in the strength, then it is one of a correct way.

I sort of see why, but it seems like to me that for most degree structures, richness of structure directly implies an increase of strength in the notation. Do you have an explanation as to why it doesn't necessarily add significant strength to the notation?

> I am not certain about your intention. Do you intend a replacement like the one in Goodstein theorem?

After writing it out I realized the first choice makes less sense than the second. Its original intention was to end the hierarchy of degrees at \(\underbrace{\Lambda^{\Lambda^{\cdots^{\Lambda}}}}_{N-2}\), setting \(d\) equal to this ordinal should correspond to \(\Pi_{N-2}^1\)-indescribability, the intended strength of Arai's system. My extra constant \(\Upsilon>\Lambda\) (this restriction was too weak and needed to be changed, for example "\(\Upsilon\) is regular cardinal after Λ" could be a sufficient condition) is required as a "large" constant to collapse below, for example collapses like \(\psi^{\left(\underbrace{\Lambda^{\Lambda^{\cdots^{\Lambda}}}}_{N-2}\right)}_\Upsilon(\alpha)\) require \(\Upsilon\). However #1 had problems C7X (talk) 02:27, 24 April 2021 (UTC)

> the least ordinal in "the Λ-th iteration of Mahlo operator applied to the class of weakly compact cardinals" would be a Mahlo cardinal larger than Λ, which is beyond my intention for this concept.

Maybe I am still not getting what youmeant. Could you tell me th intended definition of Λ? It depends on authors, but we tend to use it to express an ordinal closed under given operations. For example, when we deal with EBOCF, it stands for the least OFP. When we consider Rathjen's \chi, then it stands for the least non-zero ordinal closed under \chi. When we deal with CNF beyond K, then it stands for \varepsilon_{K+1}. Therefore I guessed that it is \varepsilon_{K+1}, but your explanation implies that your definition is different. Could you tell me the definition of Λ in your alternative definition of a notation?

> Do you have an explanation as to why it doesn't necessarily add significant strength to the notation?

Then please consider the example which I wrote above (i.e. the notation with alphabets). Since it does not have any fixed ordering, you can fix any ordering. Then the well-foundedness of the system is the well-foundedness of the fixed ordinal, which is irrelevant to the degree.　As long as we deal with a formal notation, "encoding properties" has nothing to do with the strength.

p-adic 03:20, 24 April 2021 (UTC)

> Could you tell me the definition of Λ in your alternative definition of a notation?

I am using Arai's definition of Λ here, which is the least epsilon number after \(\mathbb K\), which is the least \(\Pi_{N-2}^1\)-indesc. cardinal. About "the ε_K+1-th iteration of Mahlo operator applied to the class of weakly compact cardinals" where K denotes the least weakly compact cardinal, I think the degree corresponding to this predicate is \(\Lambda+\varepsilon_{K+1}=\Lambda+\varphi 1(K+1)\), which is less than \(\Lambda\times 2\) if \(N>3\).

> Then please consider the example which I wrote above (i.e. the notation with alphabets).

OK, it makes more sense now. To solve the problem of pathological orderings, what if we use terms of the notation themselves for degrees, like in DoR, and use the convention that the ordering on the degree structure must be the same as the ordering on terms? (On the set-theoretic side, we can do a similar thing by letting ordinals themselves represent degrees, like in my example notion) C7X (talk) 03:32, 24 April 2021 (UTC)

Thank you for the explanation. Then the difference of your alternative formulation and Arai's formulation are the following, right?

You use a CNF with base Λ, while Prof. Arai uses a sequence below ε_{Λ+1}. (Then your notation does not deal with sequences above Λ, right? Also, you need to add a recusive way to check the comparison of CNFs without using the map x→Λ^x, because the map is not a portion of your notation.)

> what if we use terms of the notation themselves for degrees, like in DoR, and use the convention that the ordering on the degree structure must be the same as the ordering on terms?

I think that the definition of the ordering includes a circular logic, or the definition inclused an error like "the least 10-Mahlo cardinal < the least 3-Mahlo cardinal above the least 11-Mahlo cardinal". Using "collapsing below" method, we cannot use the degree itself to create a desired property. (On the other hand, as Taranovsky implicitly recommends, Buchholz's method os "collapsing above" partially allow it. This is why I prefer Buchholz's method, and several Japanese googologists discovers merits to use Buchholz's method.) You might not do a similar mistake, but I cannot judge unless I see an explicit definition. —Preceding unsigned comment added by p進大好きbot (talk • contribs)

> Also, you need to add a recusive way to check the comparison of CNFs without using the map x→Λ^x

I don't understand why it has to be recursive, since this is an OCF that isn't recursive, instead of a recursive ordinal notation.

> I think that the definition of the ordering includes a circular logic, or the definition inclused an error like "the least 10-Mahlo cardinal < the least 3-Mahlo cardinal above the least 11-Mahlo cardinal".

To make sure I understand why there could be a circular logic, I think it's because "collapsing below" always requires a higher ordinal, sometimes requiring an infinite increasing sequence of ordinals to be present in the Skolem hull. (In the source of this page is a commented-out explanation that was not strictly relevant.) But in this case, there may be a method of collapsing below \(\mathbb K\) that solves this issue (although I haven't studied Arai's OCF enough to know if this would work) C7X (talk) 18:50, 24 April 2021 (UTC)

> I don't understand why it has to be recursive, since this is an OCF that isn't recursive, instead of a recursive ordinal notation.

You are trying to create an ordinal notation, aren't you? If no, then it is meaningless to discuss how to define an ordering, because ordinals are ordered from the beginning. If you want to create an ordinal notation associated to your OCF, then you need to recursively interprete CNF. It is not so easy, as the OF does not include the map x→Λ^x as a base function. This is the point why my notations using CNF are quite complicated.

> To make sure I understand why there could be a circular logic, I think it's because "collapsing below" always requires a higher ordinal, sometimes requiring an infinite increasing sequence of ordinals to be present in the Skolem hull.

Right. Moreover, the recusive interpretation of the ordering requires the comparison of higher ordinals when we compare two values of OCFs. Therefore it does not generally work. Maybe it is good for you to create one ordinal notation in order to understand problems.

p-adic 23:17, 24 April 2021 (UTC)

> You are trying to create an ordinal notation, aren't you?

This was the problem, my "Arai concept" was an OCF and not an ordinal notation.

> If you want to create an ordinal notation associated to your OCF, then you need to recursively interprete CNF. It is not so easy, as the OF does not include the map x→Λ^x as a base function. This is the point why my notations using CNF are quite complicated.

This makes sense, for example it seems like Madore's OCF vs. Bachmann's OCF, an ordinal notation for Bachmann's won't necessarily be easy to translate for Madore's OCF because Bachmann's OCF doesn't have maps like λξ.Ω^ξ, is this right?

> Moreover, the recusive interpretation of the ordering requires the comparison of higher ordinals when we compare two values of OCFs.

Interesting, I'd never thought about this. So should I explicitly write that the recursive implementation of \(\in\) is defined by induction along the tree-like structure of terms (tree-like in the way "terms of the form "ψab", "terms of the form "χab", etc. connect subterms together), avoiding this problem, since the comparison of smaller, lower terms will be defined before the comparison of simpler, higher terms that appear as subterms of them? C7X (talk) 23:25, 24 April 2021 (UTC)

> This was the problem, my "Arai concept" was an OCF and not an ordinal notation.

Oh, I see. You wanted to work in uncomputable googology then.

> an ordinal notation for Bachmann's won't necessarily be easy to translate for Madore's OCF because Bachmann's OCF doesn't have maps like λξ.Ω^ξ, is this right?

Well, the question is ambiguous when you are only interested in an OCF but not in an ordinal notation. When you deal with an OCF, a term α in Buchmann's OCF is an ordinal, and hence itself a term in Madore's OCF. Therefore the translation is trivial. If you are interested in a recursive way to express ordinals using a recursive interpretation of normal form, then the translation will be non-trivial.

> So should I explicitly write that the recursive implementation of \(\in\) is defined by induction along the tree-like structure of terms (tree-like in the way "terms of the form "ψab", "terms of the form "χab", etc. connect subterms together), avoiding this problem, since the comparison of smaller, lower terms will be defined before the comparison of simpler, higher terms that appear as subterms of them?

Right, if you are interested in an ordinal notation. If you are interested only in ordinals, you do not need to define a recursive interpretation.

p-adic 04:12, 26 April 2021 (UTC)

The form of an ordinal notation[]

This article seems to say that an ordinal notation is just "a (primitive) recursive well-ordering [on a recursive set of finite strings]", but to my understanding an ordinal notation is the pair \((OT,<)\) of the ordering and its domain (for example, Buchholz refers to \((OT,<)\) itself as an ordinal notation in section 2 here). Also, Wikipedia's article claims without a source that an ordinal notation is the partial function mapping each term to an ordinal in a countable set of ordinals, for example Buchholz's o-function. Which is correct? (I doubt Wikipedia's is) C7X (talk) 21:41, 6 May 2021 (UTC)

It depends on the formulation, and both are correct in my opinion. For example, there are three formulations of a function: (1) the graph, (2) the pair of the domain and the graph, and (3) the triad of the domain, the codomain, and the graph. So if a function f:X→Y is given by the convention (1), the corresponding function in the convention (2) is described as (X,f). The same conversion is true for a relation such as an ordering.

One special point is that the domain of a TM (regarded as an unary function) is always a subset of N, and the domain can be automatically determined if we fix an algorithm. Therefore some author likes to use < instead of (OT,<).

p-adic 22:52, 6 May 2021 (UTC)

I found a source saying that the pair of a set of terms and its order is called an "ordinal notation system", should I add this or are both correct enough for "ordinal notation" for this article as you said?

Both are correct. An ordinal notation is the same as an ordinal notation system. (For example, I used to use "ordinal notation system" here, but I recently use "ordinal notation" more often.)

p-adic 09:55, 17 June 2021 (UTC)