Googology Wiki
Advertisement
Googology Wiki

Original on my site

We will define functions \(\psi, \chi\) by exclusion \(\varphi, \Phi\) in the definition of Rathjen's original functions [1]. That simplifies creation of recursive ordinal notation and system of fundamental sequences. Application of this recursive notation to FGH or extended arrows allows to generate large computable numbers.

Basic Notions

Small greek letters \(\alpha, \beta, \gamma, \delta, \xi, \eta\) denote ordinals. Each ordinal \(\alpha\) is identified with the set of its predecessors \(\alpha=\{\beta|\beta<\alpha\}\). The least ordinal is zero and it is identified with the empty set.

\(\omega\) is the first transfinite ordinal and the set of all natural numbers.

Every ordinal \(\alpha\) is either zero, or a successor (if \(\alpha=\beta+1\)), or a limit.

An ordinal \(\alpha\) is a limit ordinal if for all \(\beta<\alpha\) there exists an ordinal \(\gamma\) such that \(\beta<\gamma<\alpha\)

\(S\) denotes the class of successor ordinals and \(L\) denotes the class of limit ordinals.

An ordinal \(\alpha\) is an additive principal number if \(\alpha>0\) and \(\xi+\eta<\alpha\) for all \(\xi,\eta<\alpha\).

\(P=\{\alpha>0|\forall\beta,\gamma<\alpha(\beta+\gamma<\alpha)\}\) is the class of additive principal numbers.

For every ordinal \(\alpha\notin P\cup\{0\}\) there exist unique \(\alpha_1,..., \alpha_n\in P\) such that \(\alpha=\alpha_1+\cdots+\alpha_n\) and \(\alpha>\alpha _{1}\geq \cdots \geq \alpha _{n}\)

\(\alpha=_{NF}\alpha _{1}+\cdots +\alpha _{n}\) iff \( \alpha =\alpha _{1}+\cdots +\alpha _{n}\wedge \alpha>\alpha _{1}\geq \cdots \geq \alpha _{n}\wedge \alpha _{1},... ,\alpha _{n}\in P\)

The cofinality of a limit ordinal \(\alpha\) is the least length of increasing sequence such that the limit of this sequence is the ordinal \(\alpha\).

\(\text{cof}(\alpha)\) denotes the cofinality of an ordinal \(\alpha\).

An ordinal \(\alpha\) is uncountable regular cardinal if it is a limit ordinal larger than \(\omega\) and \(\text{cof}(\alpha)=\alpha\).

\(R=\{\alpha\in L|\alpha>\omega\wedge\text{cof}(\alpha)=\alpha\}\) is the class of uncountable regular cardinals.

The fundamental sequence for a limit ordinal number \(\alpha\) with cofinality \(\text{cof}(\alpha)=\beta\) is a strictly increasing sequence \((\alpha[\eta])_{\eta<\beta}\) with length \(\beta\) and with limit \(\alpha\), where \(\alpha[\eta]\) is the \(\eta\)-th element of this sequence.

  • If \(\alpha\) is a limit ordinal then \(\alpha\geq\text{cof}(\alpha)\geq\omega\) and \(\alpha=\sup\{\alpha[\eta]|\eta<\text{cof}(\alpha)\}\).
  • If \(\alpha\) is a successor ordinal then \(\text{cof}(\alpha)=1\) and the fundamental sequence has only one element \(\alpha[0]=\alpha-1\).
  • If \(\alpha=0\) then \(\text{cof}(\alpha)=0\) and \(\alpha\) has not fundamental sequence.

\(\kappa\) is weakly Mahlo iff \(\kappa\) is a cardinal such that for every function \(f: \kappa\rightarrow\kappa\) there exists a regular cardinal \(\pi < \kappa\) such that \(\forall\alpha<\pi(f(\alpha)< \pi)\).

\(M\) is the least weakly Mahlo cardinal and \(\varepsilon_{M+1}=\min\{\alpha>M|\alpha=\omega^\alpha\}\)

The variables \(\pi\), \(\rho\), \(\kappa\) are reserved for regular uncountable cardinals less than \(M\).

Enumeration function \(F\) of class of ordinals \(X\) is the unique increasing function such that \(X=\{F(\alpha)|\alpha\in\text{dom}(F)\}\) where domain of \(F\), \(\text{dom}(F)\) is an ordinal number. We use \(\text{Enum}(X)\) to denote \(F\).

\(cl(X) \) is closure of \(X\)

\(cl_M(X)=X\cup\{\alpha<M|\alpha=\sup(X\cap\alpha)\} \)

Definition of functions \(\chi_\alpha(\beta) \) and \(\psi_\pi(\gamma) \)

Inductive Definition of functions \(\chi_\alpha: M\rightarrow M\) for \(\alpha <\varepsilon_{M+1}\)

  1. \(\{0,M\}\cup\beta\subset B^n(\alpha, \beta)\)
  2. \(\gamma=_{NF}\gamma_1+\cdots+\gamma_k\wedge\gamma_1,...,\gamma_k\in B^n(\alpha, \beta)\Rightarrow\gamma\in B^{n+1}(\alpha, \beta)\)
  3. \(\gamma=\chi_\eta(\xi)\wedge\eta,\xi\in B^n(\alpha, \beta)\wedge\eta<\alpha\wedge\xi<M\Rightarrow\gamma\in B^{n+1}(\alpha, \beta)\)
  4. \(\gamma=\omega^\delta \wedge M<\delta\wedge\delta\in B^n(\alpha, \beta)\Rightarrow\gamma\in B^{n+1}(\alpha, \beta)\)
  5. \(\gamma<\pi\wedge\pi\in B^n(\alpha, \beta)\Rightarrow\gamma\in B^{n+1}(\alpha, \beta)\)
  6. \(B(\alpha,\beta)=\bigcup_{n<\omega}B^{n}(\alpha, \beta)\)
  7. \(\chi_\alpha=\text{Enum}(cl_M(\{\kappa|\kappa\notin B(\alpha,\kappa)\wedge\alpha\in B(\alpha,\kappa)\}))\)

Below we write \(\chi(\alpha,\beta)\) for \(\chi_\alpha(\beta)\)

Properties of \(\chi\)-functions:

  1. \(\chi(\alpha,\beta)<M\)
  2. \(\beta>\gamma\geq 0 \Rightarrow \chi(\alpha,\beta)>\chi(\alpha,\gamma)\)
  3. \(\alpha>\gamma\geq 0 \Rightarrow \chi(\alpha,\beta)=\chi(\gamma,\chi(\alpha,\beta))\)
  4. \(\chi(\alpha,0),\chi(\alpha,\beta+1) \in R\)
  5. \(\chi(0,\alpha)=\aleph_{1+\alpha}\)

Relationship between \(\chi\) and Jäger's function

\(I_\alpha=\text{Enum}(cl_M(\{\kappa|\forall\delta<\alpha(I_\delta(\gamma)=\gamma)\}))\) is Jäger's function enumerating \(\alpha\)-weakly inaccesibble cardinals and their limits [2]. We write \(I(\alpha,\beta)\) for \(I_\alpha(\beta)\). Then, \(\chi(\alpha,\beta)=I(\alpha,\beta)\) for all \(\alpha<\gamma\) where \(\gamma=\sup\{\delta(n)|n<\omega\}\) with \(\delta(0)=0\) and \(\delta(n+1)=\chi(\delta(n),0)\)

Definition: \(\alpha=_{NF}\chi(\beta,\gamma) \Leftrightarrow\alpha=\chi(\beta,\gamma)\wedge\gamma<\alpha\)

Let \(\Pi\) be the set of uncountable regular cardinals of the form \(\chi(\alpha,0)\) or \(\chi(\alpha,\beta+1)\)

\(\Pi=\{\chi(\alpha,0)|\alpha<\varepsilon_{M+1}\}\cup\{\chi(\alpha,\beta+1)|\alpha<\varepsilon_{M+1}\wedge\beta<M\}\)

Definition of \(P_M\) and \(\alpha^*\)

  1. \(P_M(0)=P_M(M)= \emptyset\)
  2. \(P_M(\alpha)=\{\alpha\}\) if \(\alpha < M\) and \(\alpha \in P\)
  3. \(P_M(\alpha)=P_M(\alpha_1)\cup ... \cup P_M(\alpha_n)\) if \(\alpha = _{NF}\alpha_1+\cdots +\alpha_n\)
  4. \(P_M(\alpha)=P_M(\beta)\) if \(\alpha = \omega^\beta\) and \(\beta > M\)

\(\alpha^*=\sup(P_M(\alpha)\cup\{0\})\)

Definition of \(\kappa^-\)

\(\kappa^-=\left\{\begin{array}{lcr} \chi(\alpha, \beta) \text{ if }\kappa=\chi(\alpha, \beta+1)\\ \alpha^* \text{ if } \kappa=\chi(\alpha, 0)\\ \end{array}\right. \)

Inductive Definition of functions \(\psi_\pi: M\rightarrow \pi\) for \(\pi\in \Pi\)

  1. \(\kappa^-\cup\{\kappa^-, M\}\subset C_\kappa^n(\alpha)\)
  2. \(\gamma=_{NF}\gamma_1+\cdots+\gamma_k\wedge\gamma_1,...,\gamma_k\in C_\kappa^n(\alpha)\Rightarrow\gamma\in C_\kappa^{n+1}(\alpha)\)
  3. \(\gamma=\omega^\delta \wedge M<\delta\wedge\delta\in C_\kappa^n(\alpha)\Rightarrow\gamma\in C_\kappa^{n+1}(\alpha)\)
  4. \(\pi\in C_\kappa^n(\alpha)\cap\kappa\wedge\gamma<\pi\wedge\pi\in\Pi \Rightarrow\gamma\in C_\kappa^{n+1}(\alpha)\)
  5. \(\gamma=_{NF}\chi(\delta, \eta) \wedge\delta,\eta\in C_\kappa^n(\alpha)\Rightarrow\gamma\in C_\kappa^{n+1}(\alpha)\)
  6. \(\beta<\alpha\wedge\pi,\beta\in C_\kappa^n(\alpha)\wedge\beta\in C_\pi(\beta)\Rightarrow\psi_\pi(\beta)\in C_\kappa^{n+1}(\alpha)\)
  7. \(C_\kappa(\alpha)=\bigcup\{C_\kappa^n(\alpha)|n \in \omega\}\)
  8. \(\psi_\kappa(\alpha)=\min\{\xi|\xi\notin C_\kappa(\alpha)\}\)

Definition: \(\alpha=_{NF}\psi_\pi(\beta)\Leftrightarrow\alpha=\psi_\pi(\beta) \wedge\beta\in C_\pi(\beta)\)

A system of fundamental sequences

Inductive definition of \(T\)

  1. \(0 \in T\) and \(M \in T\)
  2. \(\alpha=_{NF}\alpha_1+\cdots+\alpha_k\wedge\alpha_1,...,\alpha_k\in T\Rightarrow\alpha\in T\)
  3. \(\alpha=_{NF}\chi(\beta,\gamma)\wedge\beta,\gamma\in T\Rightarrow\alpha\in T\)
  4. \(\alpha=_{NF}\psi_\pi(\beta)\wedge\pi,\beta\in T \wedge\beta<M \Rightarrow\alpha\in T\)
  5. \(\alpha=\omega^\beta\wedge M<\beta<\varepsilon_{M+1}\wedge\beta\in T\Rightarrow\alpha\in T\)

Definition of fundamental sequences for non-zero ordinals \(\alpha\in T\):

  1. If \(\alpha=\alpha_1+\cdots+\alpha_k \) then \( \text{cof} (\alpha)= \text{cof} (\alpha_k) \wedge \alpha[\eta]=\alpha_1+\cdots+(\alpha_k[\eta])\)
  2. If \(\alpha=0\) then \( \text{cof}(\alpha)=0\)
  3. If \(\alpha=\psi_{\chi(0,0)}(0)\) then \(\text{cof}(\alpha)=\alpha=1 \wedge \alpha[0]=0\)
  4. If \(\alpha=\psi _{\chi(0,\beta+1)}(0) \) then \( \text{cof}(\alpha)=\omega \wedge \alpha[n]=\chi(0,\beta)\times n\)
  5. If \(\alpha=\psi_{ \chi(0,\beta)}(\gamma+1) \) then \( \text{cof}(\alpha)=\omega \wedge \alpha[n]=\psi_{\chi(0,\beta)}(\gamma)\times n\)
  6. If \(\alpha=\psi _{\chi(\beta+1,0)}(0) \) then \( \text{cof}(\alpha)=\omega \wedge \alpha[0]=0 \wedge \alpha[n+1]=\chi(\beta,\alpha[n])\)
  7. If \(\alpha=\psi _{\chi(\beta+1,\gamma+1)}(0) \) then \( \text{cof}(\alpha)=\omega \wedge \alpha[0]=\chi(\beta+1,\gamma)+1 \wedge \alpha[n+1]=\chi(\beta,\alpha[n])\)
  8. If \(\alpha=\psi_{\chi(\beta+1,\gamma)}(\delta+1) \) then \( \text{cof}(\alpha)=\omega \wedge \alpha[0]= \psi_{\chi(\beta+1,\gamma)}(\delta)+1 \wedge \alpha[n+1]=\chi(\beta,\alpha[n])\)
  9. If \(\alpha=\psi _{\chi(\beta,0)}(0) \wedge M>\text{cof}(\beta)\geq\omega \) then \( \text{cof} (\alpha)= \text{cof} (\beta) \wedge \alpha[\eta]=\chi(\beta[\eta],0)\)
  10. If \(\alpha=\psi_{ \chi(\beta,\gamma+1)}(0) \wedge M>\text{cof}(\beta)\geq\omega \) then \( \text{cof}(\alpha)=\text{cof}(\beta)\wedge \alpha[\eta]=\chi(\beta[\eta],\chi(\beta,\gamma)+1)\)
  11. If \(\alpha=\psi_{ \chi(\beta,\gamma)}(\delta+1) \wedge M>\text{cof} (\beta)\geq\omega \) then \( \text{cof}(\alpha)=\text{cof}(\beta) \wedge \alpha[\eta]=\chi(\beta[\eta],\psi_{\chi(\beta,\gamma)}(\delta)+1)\)
  12. If \(\alpha=\psi_{\chi(\beta,0)}(0) \wedge \text{cof}(\beta)=M\) then \( \text{cof}(\alpha)= \omega \wedge \alpha[0]=0 \wedge \alpha[n+1]=\chi(\beta[\alpha[n]],0)\)
  13. If \(\alpha=\psi_{ \chi(\beta,\gamma+1)}(0) \wedge \text{cof} (\beta)=M \) then \( \text{cof} (\alpha)= \omega \wedge \alpha[0]=\chi(\beta,\gamma)+1 \wedge \alpha[n+1]=\chi(\beta[\alpha[n]],0)\)
  14. If \(\alpha=\psi_{\chi(\beta,\gamma)}(\delta+1) \wedge \text{cof} (\beta)=M \) then \( \text{cof} (\alpha)= \omega \wedge \alpha[0]= \psi_{ \chi(\beta,\gamma)}(\delta)+1 \wedge \alpha[n+1]=\chi(\beta[\alpha[n]],0)\)
  15. If \(\alpha=\omega^\beta\wedge \beta = M+1\) then \(\text{cof}(\alpha)= \omega \wedge \alpha[n] = M \times n\)
  16. If \(\alpha=\omega^\beta \wedge \beta=\gamma +1 \wedge M<\gamma\) then \(\text{cof}(\alpha) = \omega\wedge \alpha[n]=\omega^\gamma\times n\)
  17. If \(\alpha=\omega^\beta\wedge M<\beta\wedge \omega\le \text{cof}(\beta) \le M\) then \(\text{cof}(\alpha)= \text{cof}(\beta)\wedge \alpha[\eta]=\omega^{\beta[\eta]}\)
  18. If \( \alpha=\chi(\beta,0) \vee \alpha=\chi(\beta,\gamma+1) \vee \alpha=M\) then \( \text{cof}(\alpha)=\alpha \wedge \alpha[\eta]=\eta\)
  19. If \(\alpha=\chi(\beta,\gamma) \wedge M>\text{cof}(\gamma)\geq\omega \) then \( \text{cof} (\alpha)=\text{cof}(\gamma)\wedge \alpha[\eta]=\chi(\beta,\gamma[\eta])\)
  20. If \(\alpha=\psi_\pi(\beta) \wedge \pi>\text{cof}(\beta)\geq\omega \) then \( \text{cof} (\alpha)= \text{cof}(\beta) \wedge \alpha[\eta]=\psi_\pi(\beta[\eta])\)
  21. If \(\alpha=\psi_\pi(\beta) \wedge \text{cof}(\beta)=\rho\geq\pi \) then \( \text{cof} (\alpha)=\omega \wedge \alpha[n]=\psi _\pi(\beta[\gamma[n]])\) where \(\gamma[0]=\psi_\rho(0)\) and \(\gamma[k+1]=\psi_\rho(\beta[\gamma[k]])\)

Ordinal notation

We define a recursive set \(\mathcal{T}\) and a recursive relation \(\triangleleft\) such that \((\mathcal{T},\triangleleft)\) is isomorphic to \((T,<)\). Below we simultaneously define:

  1. Sets of terms \(\mathcal{T}, \mathcal{P}, \mathcal{R}, \mathcal{L}\)
  2. Operation \(a\widetilde{\times}n\) for \(a\in \mathcal{P} \) and \(n\in \mathbb{N}\)
  3. Functions \(^{\star}:\mathcal{T}\rightarrow \mathcal{T}, ^{\ominus}:\mathcal{R}\rightarrow \mathcal{T}, V:T\rightarrow \mathcal{T}, o:\mathcal{T}\rightarrow T, G:\mathcal{T}\times\mathcal{T}\rightarrow \mathbb{N}\)
  4. Coefficient sets \(K_r(a) \) for \(r\in \mathcal{R}\) and \(a\in \mathcal{T} \)
  5. A linear ordering \(\triangleleft \) on \(\mathcal{T}\times\mathcal{T}\)
  6. Cofinality type \(\text{tp}(a)\) and fundamental sequence \((a[x])_{x\triangleleft \text{tp}(a)}\) for \(a\in \mathcal{T}\)

We assume that \( \langle ... \rangle \) is a primitive recursive coding function on finite sequences of natural numbers.

1. Definition of \(V:T\rightarrow \mathcal{T}\)

  1. \(V(0) = 0\)
  2. \(V(M) = \langle 1,0\rangle \)
  3. \(V(\alpha_1+\cdots+ \alpha_n) = \langle 2,V(\alpha_1),...,V(\alpha_n) \rangle \)
  4. \(V(\psi_\rho(\alpha)) =\langle 3,V(\rho),V(\alpha)\rangle \)
  5. \(V(\chi(\alpha,\beta)) = \langle 4,V(\alpha),V(\beta)\rangle \)
  6. \(V(\omega^\alpha) = \langle 5,V(\alpha)\rangle \)

2. Definition of \(o:\mathcal{T}\rightarrow T\)

  1. \(o(0) = 0\)
  2. \(o(\langle 1,0\rangle ) = M\)
  3. \(o(\langle 2,a_1,...,a_n\rangle ) = o(a_1)+\cdots+o(a_n) \)
  4. \(o(\langle 3,r,a\rangle ) = \psi_{o(r)}(o(a)) \)
  5. \(o(\langle 4,a,b\rangle ) = \chi(o(a),o(b)) \)
  6. \(o(\langle 5,a\rangle ) = \omega^{o(a)} \)

3. Abbreviations and conventions

Element of \(\mathcal{T}\) Abbreviation
\(\langle 1,0\rangle \) \(\widetilde{M}\)
\(\langle 2,a_1,...,a_n\rangle \) \(a_1\widetilde{+}\cdots\widetilde{+}a_n\)
\(\langle 3,r,a\rangle \) \(\widetilde{\psi}_r(a)\)
\(\langle 4,a,b\rangle \) \(\widetilde{\chi}(a,b)\)
\(\langle 5,a\rangle \) \(\widetilde{\omega}^{a}\)
\(\widetilde{\psi}_{ \widetilde{\chi}(0,0)}(0) \) \(\widetilde{1} \)
\( \widetilde{\psi}_{ \widetilde{\chi}(0,0)}(\widetilde{1}) \) \(\widetilde{\omega}\)

We also use the following abbreviations and conventions:

  1. Small Latin letters \(a, b, c, d, e, x\) range over elements of \(\mathcal{T}\)
  2. The letters \(p, r\) are reserved for elements of \(\mathcal{R}\)
  3. \(\mathbb{N}=\{0,1,2,3,...\} \) is the set of natural numbers
  4. The letters \(i,k,m,n\) denote elements of \(\mathbb{N}\)
  5. \(a = b\) iff \(a\) and \(b\) are the same strings of symbols
  6. \(a \trianglelefteq b :\Leftrightarrow a \triangleleft b\) or \(a = b\)
  7. If \(A\) is a subset of \(\mathcal{T} \) then \(A\triangleleft a :\Leftrightarrow \forall x\in A(x\triangleleft a) \)

4. Definition of \(a\widetilde{\times}n \) for \(a\in \mathcal{P}\) and \( n\in \mathbb{N}\)

  1. \(a\widetilde{\times}0 = 0\)
  2. \(a\widetilde{\times}1 = a \)
  3. If \(n \geq 2\) then \(a\widetilde{\times}n = \underbrace{a\widetilde{+}\cdots\widetilde{+}a}_{n\text{ copies of }a}\)

We use \(\widetilde{n}\) as an abbreviation for \(\widetilde{1}\widetilde{\times}n\)

5. Definition of sets \(\mathcal{T}, \mathcal{P}, \mathcal{R}, \mathcal{L}\)

  1. \(\mathcal{R}\subset \mathcal{P}\subset \mathcal{T}\)
  2. \(\mathcal{R}\subset \mathcal{L}\subset \mathcal{T}\)
  3. \(0 \in \mathcal{T}\)
  4. \(\widetilde{1}\in \mathcal{P} \)
  5. \(\widetilde{M}\in \mathcal{P}\cap\mathcal{L}\)
  6. If \(a_1,...,a_n \in \mathcal{P} \wedge n\geq 2 \wedge a_n \trianglelefteq \cdots \trianglelefteq a_1 \wedge a_n =\widetilde{1} \) then \( a_1\widetilde{+}\cdots\widetilde{+}a_n \in \mathcal{T}\)
  7. If \(a_1,...,a_n \in P \wedge n\geq 2 \wedge a_n \trianglelefteq \cdots \trianglelefteq a_1 \wedge \widetilde{1} \triangleleft a_n \) then \( a_1\widetilde{+}\cdots\widetilde{+}a_n \in \mathcal{L}\)
  8. If \(a,b \in \mathcal{T} \wedge G(a,b)=1 \wedge b \triangleleft \widetilde{M}\wedge b \in \mathcal{L} \) then \( \widetilde{\chi}(a,b ) \in \mathcal{P} \cap \mathcal{L}\)
  9. If \(a,b \in \mathcal{T} \wedge G(a,b)=1 \wedge b \triangleleft \widetilde{M}\wedge b \notin \mathcal{L}\) then \( \widetilde{\chi}(a,b )\in \mathcal{R}\)
  10. If \(a\in \mathcal{T} \wedge p \in \mathcal{R} \wedge K_p (a) \triangleleft a \wedge a \triangleleft \widetilde{M}\wedge \neg(p=\widetilde{\chi}(0,0)\wedge a=0) \) then \( \widetilde{\psi}_p(a)\in \mathcal{P} \cap \mathcal{L}\)
  11. If \( a\in \mathcal{T} \wedge \widetilde{M}\triangleleft a\) then \( \widetilde{\omega}^{a}\in \mathcal{P} \cap \mathcal{L}\)

6. Definition of \(r^{\ominus}\) for \(r\in \mathcal{R}\)

  1. if \(r= \widetilde{\chi}(a,0) \) then \(r^{\ominus} = a^{\star} \)
  2. if \(r= \widetilde{\chi}(a, b)\) and \(\text{tp}(b)=\widetilde{1}\) then \( \left\{\begin{array}{lcr} r^{\ominus} = \widetilde{\chi}(a, b[0]) \text{ if } G(a,b[0])=1 \\ r^{\ominus} = b[0] \text{ if } G(a,b[0])=0 \\ \end{array}\right. \)

7. Definition of \(K_r(a) \) for \(r\in \mathcal{R}\) and \(a\in \mathcal{T}\)

  1. \(K_r(0)= K_r(\widetilde{M})=\emptyset \)
  2. \(K_r (b_1\widetilde{+}\cdots\widetilde{+} b_n) = K_r(b_1) \cup ... \cup K_r(b_n) \)
  3. \(K_r (\widetilde{\chi}(b, c )) = K_r(b) \cup K_r(c ) \)
  4. \(K_r (\widetilde{\psi}_p (b)) = \left\{\begin{array}{lcr} \emptyset \text{ if } \widetilde{\psi}_p (b) \trianglelefteq r^{\ominus}\\ K_r(p) \text{ if } r^{\ominus} \triangleleft \widetilde{\psi}_p (b) \wedge p \triangleleft r \\ \{b\} \cup K_r(p) \cup K_r(b) \text{ if } r^{\ominus} \triangleleft \widetilde{\psi}_p (b) \wedge r \trianglelefteq p \\ \end{array}\right. \)
  5. \(K_r (\widetilde{\omega}^{b}) = K_r(b) \)

\(K_ r(c ) \triangleleft e \Leftrightarrow o(c )\in C_{o(r)}(o(e )) \)

8. Definition of function \(a^{\star}\) for \(a\in \mathcal{T}\)

  1. \(0^{\star} =\widetilde{M}^{\star} = 0\)
  2. \(a^{\star}= \max(a_1^{\star},...,a_n^{\star})\) if \(a= a_1\widetilde{+}\cdots\widetilde{+}a_n\)
  3. \(a^{\star}= b^{\star}\) if \(a= \widetilde{\omega}^{b}\)
  4. \(a^{\star}= a \) if \( a\in \mathcal{P}\) and \(a \triangleleft \widetilde{M}\)

9. Definition of \(G(a,b)\) for \(a\in \mathcal{T}\) and \( b\triangleleft \widetilde{M}\)

\(G(a,b)=1\) iff one of the following cases holds:

  1. \(b\notin \mathcal{P}\),
  2. \(b = \widetilde{\chi}(c, d) \wedge (c \trianglelefteq a \vee b\trianglelefteq a^{\star})\),
  3. \(b = \widetilde{\psi}_r(e ) \wedge r = \widetilde{\chi}(c ,d ) \wedge (c \trianglelefteq a \vee r \trianglelefteq a^{\star} \vee \exists x \in K_r (a) (e \trianglelefteq x) ) \),

otherwise \(G(a,b)=0\)

10. Definition of \(a\triangleleft b\) for \(a,b\in \mathcal{T}\)

  1. \(0 \triangleleft a\) iff \(a\neq 0\).
  2. \(\widetilde{M}\triangleleft c \Rightarrow \widetilde{M}\triangleleft \widetilde{\omega}^{c }\)
  3. \(\widetilde{M}\triangleleft a\triangleleft b \Rightarrow \widetilde{\omega}^{a}\triangleleft \widetilde{\omega}^{b}\)
  4. \(\widetilde{M}\trianglelefteq a\Rightarrow \widetilde{\psi}_p (b) \triangleleft a\) and \(\widetilde{\chi}(b,c ) \triangleleft a\)
  5. \(\widetilde{\chi}(a,b) \triangleleft \widetilde{\chi}(c ,d ) \) iff one of the following cases holds:
    1. \(a \triangleleft c \) and \(b \triangleleft \widetilde{\chi}(c, d ) \) and \(a^{\star}\triangleleft \widetilde{\chi}(c ,d ) \),
    2. \(a = c \) and \(b \triangleleft d \),
    3. \(c \triangleleft a\) and \( (\widetilde{\chi}(a,b) \trianglelefteq d \vee \widetilde{\chi}(a,b) \triangleleft c ^{\star})\).
  6. \(\widetilde{\chi}(a,b) \triangleleft \widetilde{\psi}_r(e ) \) iff \(\widetilde{\chi}(a,b) \triangleleft r\) and \(K_ r(\widetilde{\chi}(a,b)) \triangleleft e \), otherwise \(\widetilde{\psi}_r(e ) \triangleleft \widetilde{\chi}(a,b) \).
  7. \(\widetilde{\psi}_p (b) \triangleleft \widetilde{\psi}_r(a) \) iff one of the following cases holds:
    1. \(p \triangleleft r\) and \(p \triangleleft \widetilde{\psi}_r(a) \),
    2. \(p = r\) and \(b \triangleleft a\),
    3. \(r \triangleleft p \) and \(\widetilde{\psi}_p (b) \triangleleft r\).
  8. \(a_1\widetilde{+}\cdots\widetilde{+}a_m \triangleleft b_1\widetilde{+}\cdots\widetilde{+}b_n (2 \le m, 2 \le n) \) iff one of the following cases holds:
    1. \(m < n\) and \(a_i = b_i\) for \(1 \le i \le m\),
    2. there exists a \(k\) such that \(1 \le k \le \min(m,n)\) and \(a_k \triangleleft b_k\) and \(a_i = b_i\) for \(1 \le i < k\).
  9. Let \(b \in \mathcal{P}\) and \(2 \le n\). Then:
    1. \(a_1\widetilde{+}\cdots\widetilde{+}a_n \triangleleft b\) if \(a_1 \triangleleft b\),
    2. \(b \triangleleft a_1\widetilde{+}\cdots\widetilde{+}a_n\) if \(b \trianglelefteq a_i\) for some \(1 \le i \le n\).
  10. If no one of rules 10.1-10.9 can be applied, then use the property \(a \trianglelefteq b \Leftrightarrow\neg ( b \triangleleft a)\)

Note: \(a\triangleleft b\) and \(a,b\in \mathcal{T} \Leftrightarrow o(a)<o(b) \)

11. Definition of \(\text{tp}(a)\) and \(a[x]\) for \(a \in \mathcal{T}\) and \(x \triangleleft \text{tp}(a)\)

  1. If \(a=a_1\widetilde{+}\cdots\widetilde{+}a_n \wedge a_n[x]=0 \) then \( \text{tp}(a)= \text{tp}(a_n) \wedge a[x]= \left\{\begin{array}{lcr} a_1 \text{ if } n=2\\ a_1\widetilde{+}\cdots\widetilde{+}a_{n-1}\text{ if } n>2\\ \end{array}\right.\)
  2. If \(a=a_1\widetilde{+}\cdots\widetilde{+}a_n \wedge 0\triangleleft a_n[x]\) then \( \text{tp}(a)= \text{tp}(a_n) \wedge a[x]= \left\{\begin{array}{lcr} a_1\widetilde{+}(a_2[x]) \text{ if } n=2\\ a_1\widetilde{+}\cdots\widetilde{+}a_{n-1}\widetilde{+}(a_n[x])\text{ if } n>2\\ \end{array}\right.\)
  3. If \(a=0\) then \(\text{tp}(a)=0\)
  4. If \(a=\widetilde{1}\) then \(\text{tp} (a)=\widetilde{1} \wedge a[0]=0\)
  5. If \(a=\widetilde{\psi} _{\widetilde{\chi}(0,b)}(0) \wedge \text{tp}(b)=\widetilde{1}\) then \( \text{tp}(a)=\widetilde{\omega} \wedge a[\widetilde{n}]= \widetilde{\chi}(0,b)^{\ominus}\widetilde{\times}n\)
  6. If \(a=\widetilde{\psi}_{\widetilde{\chi}(0,b)}(c)\wedge \text{tp}(c)=\widetilde{1} \) then \(\text{tp}(a)=\widetilde{\omega} \wedge a[\widetilde{n}]=\widetilde{\psi}_{\widetilde{\chi}(0,b)}(c[0]) \widetilde{\times}n \)
  7. If \(a=\widetilde{\psi} _{\widetilde{\chi}(b,0)}(0) \wedge \text{tp}(b)=\widetilde{1}\) then \(\text{tp}(a)=\widetilde{\omega} \wedge a[0]=0 \wedge a[\widetilde{n}]=\widetilde{\chi}(b[0],a[\widetilde{n}[0]])\) for \(n>0\)
  8. If \(a=\widetilde{\psi} _{\widetilde{\chi}(b,c)}(0)\wedge \text{tp}(b)=\text{tp}(c)=\widetilde{1} \) then \(\text{tp}(a)=\widetilde{\omega} \wedge a[0]=\widetilde{\chi}(b,c)^{\ominus}\widetilde{+}\widetilde{1} \wedge a[\widetilde{n}]=\widetilde{\chi}(b[0],a[\widetilde{n}[0]])\) for \(n>0\)
  9. If \(a=\widetilde{\psi}_{\widetilde{\chi}(b,c)}(d) \wedge \text{tp}(b)=\text{tp}(d)=\widetilde{1} \) then \(\text{tp}(a)=\widetilde{\omega} \wedge a[0]= \widetilde{\psi}_{\widetilde{\chi}(b,c)}(d[0])\widetilde{+}\widetilde{1} \wedge a[\widetilde{n}]=\widetilde{\chi}(b[0],a[\widetilde{n}[0]])\) for \(n>0\)
  10. If \(a=\widetilde{\psi} _{\widetilde{\chi}(b,0)}(0) \wedge \widetilde{\omega} \trianglelefteq \text{tp}(b) \triangleleft \widetilde{M} \) then \( \text{tp} (a)= \text{tp} (b) \wedge a[x]=\widetilde{\chi}(b[x],0)\)
  11. If \(a=\widetilde{\psi}_{ \widetilde{\chi}(b,c)}(0) \wedge \text{tp}(c)=\widetilde{1}\wedge \widetilde{\omega} \trianglelefteq \text{tp}(b) \triangleleft \widetilde{M} \) then \(\text{tp}(a)=\text{tp}(b)\wedge a[x]=\widetilde{\chi}(b[x],\widetilde{\chi}(b,c)^{\ominus}\widetilde{+}\widetilde{1})\)
  12. If \(a=\widetilde{\psi}_{ \widetilde{\chi}(b,c)}(d)\wedge \text{tp}(d)=\widetilde{1} \wedge \widetilde{\omega} \trianglelefteq \text{tp}(b) \triangleleft \widetilde{M}\) then \( \text{tp}(a)=\text{tp}(b) \wedge a[x]=\widetilde{\chi}(b[x],\widetilde{\psi}_{\widetilde{\chi}(b,c)}(d[0])\widetilde{+}\widetilde{1})\)
  13. If \(a=\widetilde{\psi}_{\widetilde{\chi}(b,0)}(0) \wedge \text{tp}(b)=\widetilde{M}\) then \(\text{tp}(a)= \widetilde{\omega} \wedge a[0]=0 \wedge a[\widetilde{n}]=\widetilde{\chi}(b[a[\widetilde{n}[0]]],0)\) for \(n>0\)
  14. If \(a=\widetilde{\psi}_{ \widetilde{\chi}(b,c)}(0) \wedge \text{tp}(c)=\widetilde{1}\wedge \text{tp} (b)=\widetilde{M} \) then \(\text{tp} (a)= \widetilde{\omega} \wedge a[0]=\widetilde{\chi}(b,c)^{\ominus}\widetilde{+}\widetilde{1} \wedge a[\widetilde{n}]=\widetilde{\chi}(b[a[\widetilde{n}[0]]],0)\) for \(n>0\)
  15. If \(a=\widetilde{\psi}_{\widetilde{\chi}(b,c)}(d) \wedge \text{tp}(d)=\widetilde{1}\wedge \text{tp} (b)=\widetilde{M} \) then \( \text{tp} (a)= \widetilde{\omega} \wedge a[0]= \widetilde{\psi}_{ \widetilde{\chi}(b,c)}(d[0])\widetilde{+}\widetilde{1} \wedge a[\widetilde{n}]=\widetilde{\chi}(b[a[\widetilde{n}[0]]],0)\) for \(n>0\)
  16. If \(a=\widetilde{\omega}^{b}\wedge b=\widetilde{M}\widetilde{+}\widetilde{1} \) then \(\text{tp}(a)= \widetilde{\omega}\wedge a[\widetilde{n}]=\widetilde{M}\widetilde{\times}n\)
  17. If \(a=\widetilde{\omega}^{b}\wedge b=c\widetilde{+}\widetilde{1} \wedge \widetilde{M}\triangleleft c\) then \(\text{tp}(a)= \widetilde{\omega}\wedge a[\widetilde{n}]=\widetilde{\omega}^{c}\widetilde{\times}n\)
  18. If \(a=\widetilde{\omega}^{b}\wedge \widetilde{M}\triangleleft b\wedge \widetilde{\omega}\trianglelefteq \text{tp}(b) \trianglelefteq \widetilde{M} \) then \(\text{tp}(a)= \text{tp}(b)\wedge a[x]=\widetilde{\omega}^{b[x]}\)
  19. If \((a=\widetilde{\chi}(b, c) \wedge \text{tp}(c)\in \{0,\widetilde{1}\}) \vee a=\widetilde{M}\) then \(\text{tp} (a)=a \wedge a[x]=x\)
  20. If \(a=\widetilde{\chi}(b,c) \wedge \widetilde{\omega} \trianglelefteq \text{tp}(c)\triangleleft\widetilde{M}\) then \(\text{tp} (a)=\text{tp}(c)\wedge a[x]=\widetilde{\chi}(b,c[x])\)
  21. If \(a=\widetilde{\psi}_p(b) \wedge \widetilde{\omega} \trianglelefteq \text{tp}(b) \triangleleft p \) then \(\text{tp} (a)= \text{tp}(b) \wedge a[x]=\widetilde{\psi}_p(b[x])\)
  22. If \(a=\widetilde{\psi}_p(b) \wedge p \trianglelefteq \text{tp}(b)=r \) then \(\text{tp} (a)=\widetilde{\omega} \wedge a[\widetilde{n}]=\widetilde{\psi} _p(b[c_n])\) where \(c_0 =\widetilde{\psi}_r (0)\) and \(c_{m+1}=\widetilde{\psi}_r(b[c_m]) \) for \(m\in \mathbb{N} \)

Note: if \(a \in \mathcal{T}\) and \(x \triangleleft \text{tp}(a)\) then \(a[x]\in \mathcal{T}\) and \(a[x]\triangleleft a\)


12. Definition of \(f(a,n) \) for \(a\in \mathcal{T}\) and \(n\in \mathbb{N}\)

  1. If \(\text{tp} (a)=0\) then \(f(a,n)=n+1\)
  2. If \(\text{tp} (a)=\widetilde{1}\) then \(f(a,n)= s_n\) where \(s_0=n\) and \(s_{m+1}= f(a[0],s_m) \) for \(m\in \mathbb{N}\)
  3. If \(\text{tp} (a)=\widetilde{\omega}\) then \(f(a,n)= f(a[\widetilde{n}],n) \)

If \(a = V(\beta) \) then for the function of fast-growing hierarchy \(f_\beta(n) = f(a,n) \)

13. Definition of \(F(n) \) for \(n\in \mathbb{N}\)

\(F(n) = f(a_n,n) \) where \(a_n =\widetilde{\psi}_{\widetilde{\chi}(0,0)}(\widetilde{\chi}(b_n,0)) \) with \(b_0=\widetilde{M}\widetilde{+}\widetilde{1} \) and \(b_{m+1}=\widetilde{\omega}^{b_m}\) for \( m\in \mathbb{N}\)

14. Definition of \(h(n,a,k) \) for \(a\in \mathcal{T}\) and \(n,k\in \mathbb{N}\backslash \{0\}\)

  1. If \(\text{tp} (a)\in \{0,\widetilde{1}\}\) then \(h(n,a,1)=n \)
  2. If \(\text{tp} (a)=0\) then \(h(n,a,k+1)=h(n,a,k)+n\)
  3. If \(\text{tp} (a)=\widetilde{1}\) then \(h(n,a,k+1)=h(n,a[0],h(n,a,k)) \)
  4. If \(\text{tp} (a)=\widetilde{\omega}\) then \(h(n,a,k)= h(n,a[\widetilde{k}],n) \)

If \(a = V(\beta) \) then for extended arrows \(n\uparrow^{\beta}k = h(n,a,k) \)

References

  1. M. Rathjen (1990). Ordinal Notations Based on a Weakly Mahlo Cardinal. Arch. Math. Logic (1990) 29: 249-263
  2. G. Jäger (1984). ρ-inaccessible ordinals, collapsing functions and a recursive notation system. Arch. Math. Logik Grundlagenforsch, Vol. 24, 49-62
  3. M. Rathjen (1991). Proof-theoretic analysis of KPM. Arch. Math. Logic (1991) 30: 377-403
Advertisement