Talk: Rathjen's psi function

Omega fixed point

What is omega fixed point using this function? I got \(\psi_{\chi_1(0)}(0)\), which is "the usual \(\psi_I(0)\)".

And what is that ordinal using this function? I still got \(\psi_{\chi_0(0)}(\psi_{\chi_1(0)}(0))\), which is "the usual \(\psi(\psi_I(0))\)". {hyp/^,cos} (talk) 13:43, 15 November 2020 (UTC)

> I got \(\psi_{\chi_1(0)}(0)\)

No, the least omega fixed point is \(\Phi_{\varphi_0(0)}(0) = \Phi_1(0)\) in this notation, and \(\psi_{\chi_1(0)}(0)\) is the limit \(\Phi_{\Phi_{\cdots}(0)}(0)\), which is much bigger than \(\Phi_1(0)\).

> I still got \(\psi_{\chi_0(0)}(\psi_{\chi_1(0)}(0))\)

No. Although there is no formal proof, the countable limit of Extended Buchholz's function is expected to be \(\psi_{\chi_0(0)}(\Phi_1(0))\) at least in Japanese googology community. The ordinal \(\psi_{\chi_0(0)}(\psi_{\chi_1(0)}(0)\) is much bigger than it.

p-adic 13:57, 15 November 2020 (UTC)

Where is \(\Phi\) in this notation? {hyp/^,cos} (talk) 14:21, 15 November 2020 (UTC)

It is a portion of the original notation. I guess that you are confounding the original notation and the simplified notation in the article. Should we change the explanation in the article in order to avoid the confusion? (I added bold warnings, but they might not be so effective here.)

p-adic 14:34, 15 November 2020 (UTC)

I saw the \(\Phi\) in the definition of \(C_{n+1}(\alpha,\beta)\) from the source. For this simplification, \(\Phi\) doesn't improve final strength so it is omitted. But it affects specific values such as \(\psi_{\chi_1(0)}(0)\). {hyp/^,cos} (talk) 14:59, 15 November 2020 (UTC)

Right. (Also, if you feel the article confusing, I appreciate your improvement of the article.)

p-adic 15:14, 15 November 2020 (UTC)

Question

Is the following true?

"Ordinals in Rathjen's OCF obey this description:

Veblen φ generates from M large cardinals such as ε_{M+1}.

Internal χ collapses big large cardinals such as M into smaller higher weakly inaccessible cardinals.

External χ with smaller inputs enumerates higher weakly inaccessible cardinals and their limits. For example, χ_0(β) = Omega_{1+β} - smallest uncountable ordinals and χ_1(β) = I_{1+β} - weakly inaccessible cardinals.

Internal ψ collapses higher weakly inaccessible cardinals into smaller fixed points of capital Φ.

Capital Φ iteratedly enumerates uncountable cardinals. For example, Φ_0(β) = Omega_{1+β}, Φ_1(β) = (1+β)-th omega fixed point, and Φ_2(β) = (1+β)-th fixed point of Φ_1.

External ψ collapses accessible cardinals into smaller Γ-numbers.

They collapse cardinals in the same way as other OCFs, i.e. take the least element which does not belong to the set of elements "describable" from below.

When χ appears as an index of ψ, it is regular. If it is singular, then just take the fundamental sequence of the second variable. Φ admits a similar fundamental sequence as φ, because they are defined in a parallel way.

The fundamental sequence of ψ is very difficult and it requires to write down an algorithm to check cofinality." Tetramur (talk) 10:38, 29 January 2021 (UTC)

What do "external" and "internal" formally mean? The answer depends on the meaning. Also, you are omitting quatification, and hence the question is quite ambiguous. Please add appropriate quantifications.

p-adic 10:46, 29 January 2021 (UTC)

> take the least element which does not belong to the set of elements "describable" from below.

It differs in some cases, for example \(\psi_{\Omega_2}(1)\) C7X (talk) 14:18, 29 January 2021 (UTC)

Edit: I had forgotten about the downward closure under cardinals in C

Three parts of a system of (recursively) Mahlo OCFs

For convenience, here I will use Rathjen's weakly Mahlo OCF except replacing M with \(\mu_0\), \(\textrm{Reg}\) with \(\textrm{Adm}\) - the set of admissible ordinals in the interval \((\omega,\mu_0)\), and restricting \(\textrm{SC}\) to \(\mu_0\).

Let \(S:\mathcal P(\mu_0)\rightarrow\mathcal P(\mu_0)\) denote the operator mapping each \(A\in\mathcal P(\mu_0)\) to \(\{\beta\in\mu_0:\beta\textrm{ is }\Pi_2\textrm{-reflecting and }\Pi_1\textrm{-reflecting on }A\}\). For example, \(S(\textrm{Adm})\) is the set of recursively inaccessible ordinals \(<\mu_0\).

To my understanding, this sufficiently strong system of (recursively) Mahlo OCFs will have three parts to it, described here in terms of reflection:

• Iterated \(\Pi_1\)-reflection on \(\textrm{SC}\). These are outputs of \(\alpha\mapsto\psi_{\omega_1^{CK}}(\alpha)\). For example, values such as \(\psi_{\omega_1^{CK}}(10)\) and \(\psi_{\omega_1^{CK}}(\varepsilon_{\mu_0+1})\)
• Iteration of \(S\) onto SC (for example, \(\textrm{Adm}\subseteq S(\textrm{SC})\), or \(S(S(S(\textrm{SC})))\)). These are outputs of functions \((\alpha,\beta)\mapsto\chi_\alpha(\beta)\). For example, values such as \(\chi_1(0)\) and \(\chi_{\mu_0}(1)\)
• Iterated \(\Pi_1\)-reflection on (iteration of \(S\) onto \(\textrm{SC}\)). These are outputs of functions such as \((\alpha,\pi)\mapsto\psi_\pi(\alpha)\) for \(\pi\) in the interval \((\omega_1^{CK},\mu_0)\), and also functions \((\alpha,\beta)\mapsto\Phi\alpha\beta\) if \(S\) is only iterated once. For example, values such as \(\psi_{\omega_2^{CK}}(\omega_\omega^{CK})\) or \(\psi_{\nu}(0)\) where \(\nu\) denotes the least recursively inaccessible; also values such as \(\Phi 20\) in the case that the iteration of \(S\) in question is \(S(\textrm{SC})\).

If this is wrong, does Rathjen's system encode extra strength in comparison to the hierarchy of reflection given here? If so, where is the weakness in my understanding? C7X (talk) 14:41, 23 March 2021 (UTC)

I do not understand your interpretation. What does "Π_1-reflection on SC" means? You seem to be referring to a function, but I have no idea about how Π_1-reflection of SC gives a recursive anlogue of ψ_Ω. Rathjen omitted how to give such a recursive analogue in the original paper. So I guess that you are referring to another paper specialising to the explicit method to give a recursive analogue.　Could you give the precise definition of ψ_{ω_1^CK} in terms of the reflecting property?

p-adic 15:21, 23 March 2021 (UTC)

Rathjen has written another paper with an OCF using recursive analogues such as \(\omega_1^{CK}\), however I don't know what paper this is. I'm working under the assumption that Rathjen's OCF using weakly Mahlo cardinals also generalizes to recursive analogues such as the replacement I gave (my method seems naive, but since I haven't studied the OCF I won't know if it doesn't work). \(\psi_{\omega_1^{CK}}\) isn't defined in terms of a reflecting property, but it seems to coincide with reflection on \(\textrm{SC}\) often. For example:

• \(\psi_{\omega_1^{CK}}(\omega)\) (under my assumption) is the least ordinal that is \(\Pi_1\)-reflecting on SC
• \(\psi_{\omega_1^{CK}}(\omega2)\) (under my assumption) is the second ordinal that is \(\Pi_1\)-reflecting on SC
• \(\psi_{\omega_1^{CK}}(\omega^2)\) (under my assumption) is the least ordinal that is \(\Pi_1\)-reflecting on ordinals \(\Pi_1\)-reflecting on SC
• \(\psi_{\omega_1^{CK}}(\omega^3)\) (under my assumption) is the least ordinal that is \(\Pi_1\)-reflecting on ordinals \(\Pi_1\)-reflecting on ordinals \(\Pi_1\)-reflecting on SC

C7X (talk) 18:00, 23 March 2021 (UTC)

> ψ_{ω_1^CK} isn't defined in terms of a reflecting property, but it seems to coincide with reflection on SC often.

OK. Then what is the definition of ψ_{ω_1^CK}? I am asking you the precise definition instead of what you guessed from the definition in your mind. (Without sharing the precise definition, others cannot point out what is wrong.)

p-adic 23:52, 23 March 2021 (UTC)

Let \(\textrm{Adm}\) denote the set of admissible ordinals in the interval \((\omega,\mu_0)\), let \(\textrm{SC}\) denote the set of \(\Gamma\)-ordinals in the interval \((0,\mu_0)\), and restrict \(\pi,\kappa\) to \(\textrm{Adm}\).

For a function \(f\) let \(\textrm{dom}\) denote the domain of \(f\), let \(\textrm{cl}_{\mu_0}(X)\) denote \(X\cup\{\alpha:\alpha\textrm{ limit point of }X\}\), and let \(\textrm{enum}(X)\) denote the unique strictly increasing function with domain exactly \(X\).

For \(\alpha\in\Gamma_{\mu_0+1}\) and \(\beta\in\mu_0\): \(\beta\cup\{0,\mu_0\}\subseteq B^n(\alpha,\beta) \\ \gamma=\gamma_1+\cdots\gamma_k\land\gamma_1,\cdots,\gamma_k\in B^n(\alpha,\beta)\rightarrow\gamma\in B^{n+1}(\alpha,\beta) \\ \gamma=\varphi_{\gamma_0}(\gamma_1)\land\gamma_0,\gamma_1\in B^n(\alpha,\beta)\rightarrow\gamma\in B^{n+1}(\alpha,\beta) \\ \pi\in B^n(\alpha,\beta)\land\gamma<\pi\rightarrow\gamma\in B^{n+1}(\alpha,\beta) \\ \delta,\eta\in B^n(\alpha,\beta)\land\delta<\alpha\land\eta\in\textrm{dom}(\chi_\delta)\rightarrow\chi_\delta(\eta)\in B^{n+1}(\alpha,\beta) \\ B(\alpha,\beta):=\bigcup\{B^n(\alpha,\beta):n<\omega\} \\ \chi_\alpha=\textrm{enum}(\textrm{cl}(\{\kappa:\kappa\notin B(\alpha,\kappa)\land\alpha\in B(\alpha,\kappa)\}))\)

If \(\kappa=\chi_\alpha(\beta+1)\), define \(\kappa^-:=\chi_\alpha(\beta)\), otherwise if \(\kappa=\chi_\alpha(0)\), then define \(\kappa^-:=\textrm{sup}(\textrm{SC}_{\mu_0}(\alpha)\cup\{0\})\), where \(\textrm{SC}_{\mu_0}\) denotes the intersection of \(\textrm{SC}\) with the set of pieces with respect to binary Veblen function.

For \(\alpha\in\Gamma_{\mu_0+1}\): \(\kappa^-\cup\{\kappa^-,\mu_0\}\subset C_\kappa^n(\alpha) \\ \gamma=\gamma_1+\cdots\gamma_k\land\gamma_1,\cdots,\gamma_k\in C^n(\alpha)\rightarrow\gamma\in C^{n+1}(\alpha) \\ \gamma=\varphi_{\gamma_0}(\gamma_1)\land\gamma_0,\gamma_1\in C^n(\alpha,\beta)\rightarrow\gamma\in C^{n+1}(\alpha) \\ \pi\in C^n_\kappa(\alpha)\cap\kappa\land\gamma<\pi\land\pi\in\textrm R\rightarrow\gamma\in C^{n+1}_\kappa(\alpha) \\ \gamma=\chi_\delta(\eta)\land\delta,\eta\in C^n_\kappa(\alpha)\rightarrow\gamma\in C^{n+1}_\kappa(\alpha) \\ \gamma=\Phi_\delta(\eta)\land\delta,\eta\in C^n_\kappa(\alpha)\land 0<\delta\land\delta,\eta<\mu_0\rightarrow\gamma\in C^{n+1}_\kappa(\alpha) \\ \beta<\alpha\land\pi,\beta\in C^n_\kappa(\alpha)\land\beta\in C_\pi(\beta)\rightarrow\psi_\pi(\beta)\in C^{n+1}_\kappa(\alpha) \\ C_\kappa(\alpha):=\bigcup\{C^n_\kappa(\alpha):n<\omega\} \\ \psi_\kappa(\alpha):=\textrm{min}(\{\xi:\xi\notin C_\kappa(\alpha)\})\)

C7X (talk) 03:35, 24 March 2021 (UTC)

1. I guess that you are confounding cl and cl_{μ_0}. (You did not use μ_0 in the definition of cl_{μ_0}, and you used cl instead of cl_{μ_0} in the definition of χ.)
2. I guess that you are confounding the domain and the range, as enum(X) is usually the enumeration of X.
3. Is the Φ the usual Φ? If no, please define it.
4. In the definition of C, you used χ_0(μ_0) but it is ill-defined.
5. You said "I think the notion is ill-defined without normal forms, but Rathjen specified normal forms for φ", but SC_{μ_0}(α) is ill-defined if you just define normal form for Veblen functions.
6. Could you tell me the well-definedness of κ^-? I guess that it is not necessarily well-defined if μ_0 is an arbitrary recursively Mahlo ordinal.

By the reasons above, the current function is ill-defined.

p-adic 09:25, 24 March 2021 (UTC)

I'm letting \(\mu_0\) be the least recursively Mahlo ordinal. #1 and #2 were problems with the definition in the article that I copy+pasted, I will define Φ by transfinite recursion on \(\alpha\), letting \(\Phi_\alpha\) enumerate \(\{\gamma:\forall(\alpha'\in\alpha)\Phi_{\alpha'}\gamma=\gamma\}\). I don't understand ill-definedness of \(\chi_0(\mu_0)\) (my understanding was that \(\textrm{dom}(\chi_0)\subseteq\mu_0\) due to ill-definedness of \(B(\alpha,\kappa)\) for \(\alpha\in\gamma_{\mu_0+1}\) and \(\kappa>\mu_0\)). C7X (talk) 17:40, 24 March 2021 (UTC)

Restarting this thread, I found a more concise and clear way to phrase what I was asking, in terms of Taranovsky's ordinal notation "Degrees of Reflection".

Let \(ST\) be the set of standard terms. A sub-Mahlo term is a term that is less than "00ΩΩΩCCC0ΩΩΩCCCΩCCC" using Taranovsky's lexicographic comparison of terms.

Conjecture 1: The order type of standard terms below "00ΩΩΩCCC0ΩΩΩCCCΩCCC" is \(\psi_\Omega(\psi_{\chi_{\varepsilon_{M+1}}0}(0))\).

For the second conjecture, classify sub-Mahlo terms in the following way:

• A "sub-Mahlo term of the first kind" is either "0" or one of the form C(a,0) for some shorter sub-Mahlo term a of the first kind.
  • To avoid circular reference, this can be defined using induction on the length of terms.
• A "sub-Mahlo term of the second kind" is one of the form C(C(a,b),0) for some term a<"Ω", and some term b of the third kind.
• A "sub-Mahlo term of the third kind" is one of the form C(a,b) for some term \(a\ge``\Omega\!"\) and some term b, and also \(\forall(a_0,a_1\in ST)(a\textrm{ is of the form }C(a_0,a_1)\rightarrow(a_0\ge\Omega\land a_1\ge\Omega))\)

Conjecture 2: For n∈{1,2,3}, let SM_n be an arbitrary sub-Mahlo term of the nth kind. Then:

• C(SM₁,0) in Taranovsky's notation corresponds to \(\psi_\Omega(\alpha)\) for some ordinal \(\alpha\) of the form \(\psi_\Omega(\beta)\)
• C(SM₂,0) in Taranovsky's notation corresponds to \(\psi_\Omega(\alpha)\) for some ordinal \(\alpha\) of the form \(\psi_\pi(\beta\) for some ordinal \(\beta\) and some uncountable regular \(\pi\), or \(\alpha\) of the form \(\Phi\gamma\beta\) for some ordinals \(\beta,\gamma\)
• C(SM₃,0) in Taranovsky's notation corresponds to \(\psi_\Omega(\chi\alpha\beta)\) for some ordinals \(\alpha,\beta\)

C7X (talk) 18:11, 24 March 2021 (UTC)

What is the relation between your new conjectures and your past questions? I know that TON is related to reflection in some sense, but does not precisely interprete an oCF based on refection properties. For example, if you construct an OCF, then the associated notation is always well-founded. On the other hand, we do not know the well-foundedness of TON. Also, since notations based not on additions, e.g. TON and Weak Extended Buchholz OCF, are very hard to analyse, I have no idea about the justification of the cojecture. (I know that there are many "analyses" of TON in this community, but none of them are based on theoretic reasonings. I mean that they are based on guesses of the intended behaviour. Basically, notations without hydra-like FSs are quite difficult.)

p-adic 22:54, 24 March 2021 (UTC)

> I know that TON is related to reflection in some sense, but does not precisely interprete an oCF based on refection properties.

Degrees of Reflection (DoR) is a weaker notation than TON that was defined earlier (both chronologically and in an earlier section of the paper), and its correspondence with reflection is more well-understood. Taranovsky gives an assignment of reflecting properties that a given term satisfies in section 4.3. However, the well-foundedness of DoR is an open problem AFAIK, and the terms are based on Taranovsky's own understanding of the notation.

> What is the relation between your new conjectures and your past questions?

For n∈{1,2,3} the nth kind of sub-Mahlo terms in my 2nd conjecture corresponds to the three "parts" of the representation system that I described in terms of reflection (using the ill-defined version of the system using recursive analogues). To translate my reflection-based questions to DoR, I made comparisons to Taranovsky's assignment of degrees from section 4.3. In fact, in [Rathjen14, Proof Theory: From Arithmetic to Set Theory (p.30)], Rathjen says that a certain weakly Mahlo notation has two "layers" to it, consisting of that which is singular and that which is regular. My concept of three parts are similar, except I split Rathjen's "singular" layer into two smaller parts, consisting of "that which is singular and not limit of uncountable regulars below", and "that which is singular and limit of uncountable regulars below". (I wrote these parts in terms of recursive analogues in the reflection questions, and in terms of Taranovsky's degrees in the DoR conjectures.)

> notations based not on additions, e.g. TON

In the section "General framework for ordinal notations", Taranovsky gives a relation between all of the ordinal notations (those which are based on function symbols C) in the paper and the map of addition on the corresponding ordinals to terms. C7X (talk) 18:32, 27 March 2021 (UTC)

Maybe you are misunderstanding a point. We can always describe the addition of corresponding ordinals even when we have no addition symbol in an ordinal notation. The point is that if we do not have addition or some other bases used in "collapsing" of some degree structure such as a recursive interpretation of regularity or reflection, then the behaviour will be completely different from another ordinal notation using those bases. For example, Rathjen's psi "minus Veblen φ" behaves completely differently from Rathjen's psi, although we can describe Veblen φ using the former one up to the limit, which isstrictly smaller than the limit of the latter one.

p-adic 22:32, 27 March 2021 (UTC)

It turned out that Rathjen's paper answered the original question I had in mind, but I am now interested in whether notations not based on addition behave differently as you mentioned. Letting \(\psi^-\) denote the function in your "Rathjen's psi without Veblen" example and \(C^-\) denoting its definition's Skolem hulls, I'm trying to compare their Skolem hulls which I can hopefully do in the future (I originally had written an inefficient and unfinished proof sketch in this edit) C7X (talk) 07:12, 28 March 2021 (UTC)

Denis has described the algorithm to compute the membership relation of the recursive interpretation of C for Rathjen's psi minus φ and Φ but with restricted ω^x. It might be helpful.

p-adic 07:51, 28 March 2021 (UTC)