Weak K-psi function

Japanese version: https://googology.wikia.org/ja/wiki/%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:Kanrokoti/%E5%BC%B1K-%CF%88%E9%96%A2%E6%95%B0

Overview

We define Weak K-psi function. This notation extends Ordinal Notation Associated to Extended Buchholz's OCF.

This notation has a high possibility of being broken.

Weak K-psi function calculator by Naruyoko

Special thanks: p進大好きbot

Weak K-psi function

Notation

Let \(T\) and \(PT\) are sets of formal strings consisting of \(0\), \(+\), \(\psi\), \((\), and \()\), which are simultaneously defined in the following recursive way:

1. \(0 \in T\).
2. For any \((a,b) \in PT \times (T \setminus \{0\})\), \(a+b \in T\).
3. For any \((a,b) \in T^2\), \(\psi_a(b) \in PT \cap T\).

\(0\) is abbreviated as \($0\), \(\psi_0(0)\) is abbreviated as \($1\), for \(n \in (\mathbb{N} \setminus \{0,1\})\), \(\underbrace{$1+ \dots +$1}_{n ~ $1's}\) is abbreviated as \($n\), and \(\psi_0($1)\) is abbreviated as \($\omega\).

Subsets \(RT \subset T\) and \(RPT \subset PT\) are simultaneously defined in the following recursive way:

1. \(0 \in RT\).
2. For any \((a,b) \in RPT \times (RT \setminus \{0\})\), \(a+b \in RT\).
3. For any \((a,b) \in \mathbb{N} \times RT\), \(\psi_{$a}(b) \in RPT \cap RT\).

Ordering

\(2\)-ary relations \(s \le t\) and \(s \lt t\) on \(RT\) are simultaneously defined in the following recursive way:

Definition of \(s \le t\)

1. If \(s = t\), then \(s \le t\) is true.
2. If \(s \neq t\), then \(s \le t\) is equivalent to \(s \lt t\).

Definition of \(s \lt t\)

1. If \(t = 0\), then \(s \lt t\) is false.
2. If \(t \neq 0\) and \(s = 0\), then \(s \lt t\) is true.
3. Suppose that \(t \neq 0\) and \(s = a+b\) for some \((a,b) \in RPT \times (RT \setminus \{0\})\).
   1. If \(t = c+d\) for some \((c,d) \in RPT \times (RT \setminus \{0\})\), then \(s \lt t\) is equivalent to that either one of the following holds:
      1. \(a \lt c\).
      2. \(a = c\) and \(b \lt d\).
   2. If \(t = \psi_{$c}(d)\) for some \((c,d) \in \mathbb{N} \times RT\), then \(s \lt t\) is equivalent to \(a \lt t\).
4. Suppose that \(t \neq 0\) and \(s = \psi_{$a}(b)\) for some \((a,b) \in \mathbb{N} \times RT\).
   1. If \(t = c+d\) for some \((c,d) \in RPT \times (RT \setminus \{0\})\), then \(s \lt t\) is equivalent to \(s \le c\).
   2. If \(t = \psi_{$c}(d)\) for some \((c,d) \in \mathbb{N} \times RT\), then \(s \lt t\) is equivalent to that either one of the following holds:
      1. \(a \lt c\).
      2. \(a = c\) and \(b \lt d\).

Cofinality

Computable total maps \begin{eqnarray*} \textrm{dom} \colon RT & \to & RT \\ s & \mapsto & \textrm{dom}(s) \\ \\ \textrm{rank} \colon RT & \to & \mathbb{N} \\ s & \mapsto & \textrm{rank}(s) \\ \end{eqnarray*} are simultaneously defined in the following recursive way:

1. If \(s = 0\), then \(\textrm{dom}(s) := 0\) and \(\textrm{rank}(s) := 0\).
2. If \(s = a+b\) for some \((a,b) \in RPT \times (RT \setminus \{0\})\), then \(\textrm{dom}(s) := \textrm{dom}(b)\) and \(\textrm{rank}(s) := \textrm{rank}(b)\).
3. Suppose that \(s = \psi_{$a}(b)\) for some \((a,b) \in \mathbb{N} \times RT\).
   1. If \(\textrm{dom}(b) = 0\), then \(\textrm{dom}(s) := s\) and \(\textrm{rank}(s) := a\).
   2. If \(\textrm{dom}(b) = $1\), then \(\textrm{dom}(s) := $\omega\) and \(\textrm{rank}(s) := 0\).
   3. Suppose that \(\textrm{dom}(b) \notin \{0,$1\}\).
      1. If \(\textrm{dom}(b) \lt s\), then \(\textrm{dom}(s) := \textrm{dom}(b)\) and \(\textrm{rank}(s) := \textrm{rank}(b)\).
      2. Suppose that \(s \le \textrm{dom}(b)\).
         1. If \(\textrm{rank}(b) = 0\), then \(\textrm{dom}(s) := $\omega\) and \(\textrm{rank}(s) := 0\).
         2. If \(\textrm{rank}(b) \neq 0\), then \(\textrm{dom}(s) := s\) and \(\textrm{rank}(s) := \textrm{rank}(b)-1\).

Search function

A computable total map \begin{eqnarray*} \textrm{CP} \colon RT & \to & RT \\ s & \mapsto & \textrm{CP}(s) \end{eqnarray*} is defined in the following recursive way:

1. If \(s = 0\), then \(\textrm{CP}(s) := 0\).
2. If \(s = a+b\) for some \((a,b) \in RPT \times (RT \setminus \{0\})\), then \(\textrm{CP}(s) := \textrm{CP}(b)\).
3. Suppose that \(s = \psi_{$a}(b)\) for some \((a,b) \in \mathbb{N} \times RT\).
   1. If \(\textrm{CP}(b) = 0\), then \(\textrm{CP}(s) := s\).
   2. If \(\textrm{CP}(b) \neq 0\), then \(\textrm{CP}(s) := \textrm{CP}(b)\).

A computable total map \begin{eqnarray*} \textrm{BP} \colon RT^2 & \to & RT \\ (s,t) & \mapsto & \textrm{BP}(s,t) \end{eqnarray*} is defined in the following recursive way:

1. If \(s = 0\), then \(\textrm{BP}(s,t) := 0\).
2. Suppose that \(s = \psi_{$a}(b)+s'\) for some \((a,b,s') \in \mathbb{N} \times RT \times (RT \setminus \{0\})\).
   1. If \(t \lt $a\), then \(\textrm{BP}(s,t) := s\).
   2. If \($a \le t\), then \(\textrm{BP}(s,t) := \textrm{BP}(s',t)\).
3. Suppose that \(s = \psi_{$a}(b)\) for some \((a,b) \in \mathbb{N} \times RT\).
   1. If \(t \lt $a\), then \(\textrm{BP}(s,t) := s\).
   2. Suppose that \($a \le t\).
      1. If \(b \lt s\), then \(\textrm{BP}(s,t) := s\).
      2. If \(s \le b\), then \(\textrm{BP}(s,t) := \textrm{BP}(b,t)\).

Fundamental sequence

A computable partial map \begin{eqnarray*} [ \ ] \colon RT^2 & \to & RT \\ (s,t) & \mapsto & s[t] \end{eqnarray*} is defined in the following recursive way:

1. If \(s = 0\), then \(s[t] := 0\).
2. If \(s = a+b\) for some \((a,b) \in RPT \times (RT \setminus \{0\})\), then put \(b' := b[t]\).
   1. If \(b' = 0\), then \(s[t] := a\).
   2. If \(b' \neq 0\), then \(s[t] := a+b'\).
3. Suppose that \(s = \psi_{$a}(b)\) for some \((a,b) \in \mathbb{N} \times RT\).
   1. If \(\textrm{dom}(b) = 0\), then \(s[t] := t\).
   2. Suppose that \(\textrm{dom}(b) = $1\).
      1. If \(t = t[0]+$1\), then \(s[t] := s[t[0]]+s[$1]\).
      2. If \(t \neq t[0]+$1\), then \(s[t] := \psi_{$a}(b[0])\).
   3. Suppose that \(\textrm{dom}(b) \notin \{0,$1\}\).
      1. If \(\textrm{dom}(b) \lt s\), then \(s[t] := \psi_{$a}(b[t])\).
      2. If \(s \le \textrm{dom}(b)\), then there is a \(c \in (\mathbb{N} \setminus \{0\})\) satisfying that \(\textrm{CP}(b) = \psi_{$c}(0)\).
         1. Suppose that \(t = 0\).
            1. If \(\textrm{rank}(b) = c\), then \(s[t] := \psi_{$a}(b[\psi_{$c[0]}(0)])\).
            2. If \(\textrm{rank}(b) \neq c\), then \(s[t] := \psi_{$a}(b[0])\).
         2. If \(t = $i\) for some \(i \in (\mathbb{N} \setminus \{0\})\) and \(s[t[0]] = \psi_{$a}(\Gamma)\) for some \(\Gamma \in RT\), then \(s[t] := \psi_{$a}(b[\psi_{$c[0]}(\textrm{BP}(\Gamma,$c[0]))])\).
         3. If neither of above, then \(s[t] := \psi_{$a}(b[t])\).

FGH

A computable partial map \begin{eqnarray*} f \colon RT \times \mathbb{N}^2 & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} is defined in the following recursive way:

1. If \(m = 0\), then \(f_s^m(n) := n\).
2. Suppose that \(m = 1\).
   1. If \(\textrm{dom}(s) = 0\), then \(f_s^m(n) := n+1\).
   2. If \(\textrm{dom}(s) = $1\), then \(f_s^m(n) := f_{s[0]}^n(n)\).
   3. If \(\textrm{dom}(s) \notin \{0,$1\}\), then \(f_s^m(n) := f_{s[$n]}^1(n)\).
3. If \(m \notin \{0,1\}\), then \(f_s^m(n) := f_s^1(f_s^{m-1}(n))\).

Standard form

A subset \(OT \subset RT\) is defined in the following recursive way:

1. For any \(n \in \mathbb{N}\), \(\psi_0(\psi_{$n}(0)) \in OT\).
2. For any \((s,n) \in OT \times \mathbb{N}\), \(s[$n] \in OT\).

My expectation is that \((OT,\lt)\) is an ordinal notation, or \(OT\) is recursive and the restriction of \(\lt\) to \(OT\) is well-ordered.

Naming

A computable partial map \begin{eqnarray*} F \colon \mathbb{N} & \to & \mathbb{N} \\ n & \mapsto & F(n) \end{eqnarray*} is defined as \(F(n) := f_{\psi_0(\psi_{$n}(0))}(n)\).

I name \(F^{10^{100}}(10^{100})\) "Weak K-ψ number".

I name an ordinal which correspond to the limit of Weak K-psi function "Weak K-psi ordinal" (WKPO).