Non-restricted 三 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/%E4%B8%89%E9%96%A2%E6%95%B0%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B2%E6%AE%B5%E9%9A%8E%E6%AD%A3%E5%89%87%E5%9F%BA%E6%95%B0%E3%81%AE%E5%88%B6%E9%99%90%E3%81%AE%E9%99%A4%E5%8E%BB

Overview

This notation has a high possibility of being broken.

See this blog post.

三 function is defined by p進大好きbot. As you can see, 三 function has the restriction in the definition of \(\textrm{dom}\) in order to define 三 function easier.

In this blog post, I attempt to get rid of the restriction. To do that, I introduce original algorithms, and hence I'm not sure if this work.

I appreciate p進大好きbot and Mrna den helping my work.

I appreciate Naruyoko making Non-restricted 三 function calculator.

Non-restricted 三 function

Notation

Let \(T\) and \(PT\) are sets of formal strings consisting of \(0\), \(+\), \(\textrm{三}\), \((\), 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\), \(\textrm{三}_a(b) \in PT \cap T\).

Abbreviation

\(0\) is abbreviated as \($0\), \(\textrm{三}_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 \(\textrm{三}_0($1)\) is abbreviated as \($\omega\).

Ordering

\(2\)-ary relations \(s \leq t\) and \(s < t\) on \(T\) are simultaneously defined in the following recursive way:

Definition of \(s \leq t\)

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

Definition of \(s < t\)

1. If \(t = 0\), then \(s < t\) is false.
2. If \(t \neq 0\) and \(s = 0\), then \(s < t\) is true.
3. Suppose that \(t \neq 0\) and \(s = a+b\) for some \((a,b) \in PT \times (T \setminus \{0\})\).
   1. If \(t = c+d\) for some \((c,d) \in PT \times (T \setminus \{0\})\), then \(s < t\) is equivalent to that either one of the following holds:
      1. \(a < c\).
      2. \(a = c\) and \(b < d\).
   2. If \(t = \textrm{三}_c(d)\) for some \((c,d) \in T^2\), then \(s < t\) is equivalent to \(a < t\).
4. Suppose that \(t \neq 0\) and \(s = \textrm{三}_a(b)\) for some \((a,b) \in T^2\).
   1. If \(t = c+d\) for some \((c,d) \in PT \times (T \setminus \{0\})\), then \(s < t\) is equivalent to \(s \leq c\).
   2. If \(t = \textrm{三}_c(d)\) for some \((c,d) \in T^2\), then \(s < t\) is equivalent to that either one of the following holds:
      1. \(a < c\).
      2. \(a = c\) and \(b < d\).

Cofinality

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

1. If \(s = 0\), then \(\textrm{dom}(s) := 0\).
2. If \(s = a+b\) for some \((a,b) \in PT \times (T \setminus \{0\})\), then \(\textrm{dom}(s) := \textrm{dom}(b)\).
3. Suppose that \(s = \textrm{三}_a(b)\) for some \((a,b) \in T^2\).
   1. Suppose that \(\textrm{dom}(b) = 0\).
      1. If \(\textrm{dom}(a) \in \{0,$1\}\), then \(\textrm{dom}(s) := s\).
      2. If \(\textrm{dom}(a) \notin \{0,$1\}\), then \(\textrm{dom}(s) := \textrm{dom}(a)\).
   2. If \(\textrm{dom}(b) = $1\), then \(\textrm{dom}(s) := $\omega\).
   3. Suppose that \(\textrm{dom}(b) \notin \{0,$1\}\).
      1. If \(\textrm{dom}(b) \lt s\), then \(\textrm{dom}(s) := \textrm{dom}(b)\).
      2. If \(s \le \textrm{dom}(b)\), then there is \((c,d) \in T^2\) satisfying that \(\textrm{dom}(b) = \textrm{三}_c(d)\).
         1. If \(\textrm{dom}(d) = 0\), then \(\textrm{dom}(s) := s\).
         2. If \(\textrm{dom}(d) \neq 0\), then \(\textrm{dom}(s) := $\omega\).

Search function

A computable total map \begin{eqnarray*} \textrm{BP} \colon T^2 & \to & T \\ (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 = \textrm{三}_a(b)+s'\) for some \((a,b,s') \in T^2 \times (T \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 = \textrm{三}_a(b)\) for some \((a,b) \in T^2\).
   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 total map \begin{eqnarray*} [ \ ] \colon T^2 & \to & T \\ (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 PT \times (T \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 = \textrm{三}_a(b)\) for some \((a,b) \in T^2\).
   1. Suppose that \(\textrm{dom}(b) = 0\).
      1. If \(\textrm{dom}(a) \in \{0,$1\}\), then \(s[t] := t\).
      2. If \(\textrm{dom}(a) \notin \{0,$1\}\), then \(s[t] := \textrm{三}_{a[t]}(b)\).
   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] := \textrm{三}_a(b[0])\).
   3. Suppose that \(\textrm{dom}(b) \notin \{0,$1\}\).
      1. If \(\textrm{dom}(b) \lt s\), then \(s[t] := \textrm{三}_a(b[t])\).
      2. If \(s \le \textrm{dom}(b)\), then there is \((c,d) \in T^2\) satisfying that \(\textrm{dom}(b) = \textrm{三}_c(d)\).
         1. Suppose that \(\textrm{dom}(d) = 0\).
            1. If \(t = 0\), then \(s[t] := \textrm{三}_a(b[\textrm{三}_{c[0]}(0)])\).
            2. If \(t = $i\) for some \(i \in (\mathbb{N} \setminus \{0\})\) and \(s[t[0]] = \textrm{三}_a(\Gamma)\) for some \(\Gamma \in T\), then \(s[t] := \textrm{三}_a(b[\textrm{三}_{c[0]}(\Gamma)])\).
            3. If neither of above, then \(s[t] := \textrm{三}_a(b[t])\).
         2. Suppose that \(\textrm{dom}(d) = \textrm{三}_e(0)\) for some \(e \in (T \setminus \{0\})\).
            1. If \(t = 0\), then \(s[t] := \textrm{三}_a(b[0])\).
            2. If \(t = $i\) for some \(i \in (\mathbb{N} \setminus \{0\})\) and \(s[t[0]] = \textrm{三}_a(\Gamma)\) for some \(\Gamma \in T\), then \(s[t] := \textrm{三}_a(b[\textrm{三}_{e[0]}(\textrm{BP}(\Gamma,e[0]))])\).
            3. If neither of above, then \(s[t] := \textrm{三}_a(b[t])\).

FGH

A computable partial map \begin{eqnarray*} f \colon T \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))\).

Limit function

A computable total map \begin{eqnarray*} \Lambda \colon \mathbb{N} & \to & PT \\ n & \mapsto & \Lambda(n) \end{eqnarray*} is defined in the following recursive way:

1. If \(n = 0\), then \(\Lambda(n) := \textrm{三}_0(0)\).
2. If \(n \neq 0\), then \(\Lambda(n) := \textrm{三}_{\Lambda(n-1)}(0)\).

Standard form

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

1. For any \(n \in \mathbb{N}\), \(\textrm{三}_0(\textrm{三}_0(\Lambda(n))) \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.