Si function 四

My second notation thingy (not sure what it classifies as). Hopefully it will be well-defined this time.

Thanks to Kanrokoti, P-adic

Parts of this were copied from Kanrokoti's non-restricted 三 function because I'm sorta lazy, go check out the original here.

Notation[]

Here, I will define the character string which I will use for defining the notation. I define two sets $T$ and $PT$ of formal strings consisting of $0$, $\textrm{四}$, $+$, $($, $)$ and commas in the following recursive way:

$0 \in T$.
For any $(a, b) \in T^2$, $\textrm{四}_a(b) \in PT \cap T$.
For any $(a_1, a_2, ..., a_m) \in PT^m$ such that $2 \leq m < \infty$, $a_1 + a_2 + ... + a_m \in T$.

To differentiate between strings and ordinals, I will write $0$ as $\$0$, $\textrm{四}_0(0)$ as $\$1$, $\underbrace{$1 + $1 ... + $1}_n$ as $\$n$ and $\textrm{四}_0(\$1)$ as $\$\omega$.

Relation[]

Next, I will define the binary "less than" relation for defining the notation. For $X, Y \in T^2$, I define a binary relation $X < Y$ in the following recursive way:

If $X = 0$, $X < Y$ is equivalent to $Y \neq 0$.
If $Y = 0$, $X < Y$ is false.
Suppose $X = \textrm{四}_a(b)$ for some $(a, b) \in T^2$.
- Suppose $Y = \textrm{四}_c(d)$ for some $(c, d) \in T^2$.
  - If $a = c$, $X < Y$ is equivalent to $b < d$.
  - If $a \neq c$, $X < Y$ is equivalent to $a < c)$.
- If $Y = a_1 + a_2 + ... + a_m$ for some $(a_1, a_2, ..., a_m) \in PT^m$ and $2 \leq m < \infty$, $X < Y$ is equivalent to $X = Y_1$ or $X < Y_1$.
Suppose $X = a_1 + a_2 + ... + a_m$ for some $(a_1, a_2, ..., a_m) \in PT^m$ and $2 \leq m < \infty$.
- If $Y = \textrm{四}_c(d)$ for some $(c, d) \in T^2$, $X < Y$ is equivalent to $c < Y$ and $d < Y$.
- Suppose $Y = b_1 + b_2 + ... + b_{m'}$ for some $(a_1, a_2, ..., a_m) \in PT^m$ and $2 \leq m < \infty$.
  - Suppose $a_1 = b_1$.
    - If $m = 2$ and $m' = 2$, $X < Y$ is equivalent to $a_2 < b_2$.
    - If $m = 2$ and $m' > 2$, $X < Y$ is equivalent to $a_2 < b_2 + ... + b_{m'}$.
    - If $m > 2$ and $m' = 2$, $X < Y$ is equivalent to $a_2 + ... + a_m < b_2$.
    - If $m > 2$ and $m' > 2$, $X < Y$ is equivalent to $a_2 + ... + a_m < b_2 + ... + b_{m'}$.
  - If $a_1 \neq b_1$, $X < Y$ is equivalent to $a_1 < b_1$.

Cofinality[]

Next, I will define a computable total map $\textrm{dom}: T \rightarrow T$, $s \rightarrow \textrm{dom}(s)$ in the following recursive way:

If $s = 0$, $\textrm{dom}(s) = 0$.
If $s = a + b$ for some $(a, b) \in PT \times (T \textrm{\} \lbrace 0 \rbrace)$, $\textrm{dom}(s) = \textrm{dom}(b)$.
Suppose $s = \textrm{四}_a(b)$ for some $(a, b) \in T^2$.
- Suppose $\textrm{dom}(b) = 0$.
  - If $\textrm{dom}(a)$ is $0$ or $\$1$, $\textrm{dom}(s) = s$.
  - Otherwise, $\textrm{dom}(s) = \textrm{dom}(a)$.
- If $\textrm{dom}(b) = \$1$, $\textrm{dom}(s) = \$\omega$.
- Otherwise:
  - If $\textrm{dom}(b) < s$, $\textrm{dom}(s) = \textrm{dom}(b)$.
  - If $s \leq \textrm{dom}(b)$, there is guaranteed to be some $(c, d) \in T^2$ such that $\textrm{dom}(b) = \textrm{四}_c(d)$. Then:
    - If $\textrm{dom}(d) = 0$, $\textrm{dom}(s) = s$.
    - Otherwise, $\textrm{dom}(s) = \$\omega$.

Fundamental sequences[]

Next, using cofinality, I will define some fundamental sequences. I define a total recursive map $[]: T^2 \rightarrow T$, $(X, Y) \rightarrow X[Y]$.

If $X = 0$, $X[Y] = 0$.
Suppose $X = \textrm{四}_a(b)$ for some $(a, b) \in T$.
- Suppose $\textrm{dom}(b) = 0$.
  - If $\textrm{dom}(a) = 0$, $X[Y] = 0$.
  - If $\textrm{dom}(a) = \$1$, $X[Y] = Y$.
  - Otherwise, $X[Y] = \textrm{四}_{a[Y]}(b)$.
- Suppose $\textrm{dom}(b) = \$1$, $X[Y] = Y$.
- Otherwise:
  - If $\textrm{dom}(b) < X$, $X[Y] = \textrm{四}_a(b[Y])$.
  - Otherwise, there exist unique $P, Q \in T$ such that $\textrm{dom}(b) = \textrm{四}_P(Q)$.
    - Suppose $Q = 0$.
      - If $Y = \$h$ for $1 \leq h < \infty$ and $X[Y[0]] = \textrm{四}_a(\Gamma)$ for unique $\Gamma \in T$, $X[Y] = \textrm{四}_a(b[\textrm{四}_{P[0]}(\Gamma)])$.
      - Otherwise, $X[Y] = \textrm{四}_a(b[\textrm{四}_{P[0]}(Q)])$ .
    - Otherwise, $X[Y] = \textrm{四}_a(b[\textrm{四}_P(Q[0])])$.
Suppose $X = a_1 + ... + a_m$ for some $(a_1, ..., a_m) \in PT^m$ and $2 \leq m < \infty$.
- If $a_m[Y] = 0$ and $m = 2$, $X[Y] = a_1$.
- If $a_m[Y] = 0$ and $m > 2$, $X[Y] = a_1 + ... + a_{m-1}$.
- Otherwise, $X[Y] = a_1 + ... + a_{m-1} + (a_m)[Y]$.

Fast-growing hierarchy[]

Next, I'll define a computable partial map $f: T \times \mathbb{N}^2 \rightarrow \mathbb{N}$, $(s, m, n) \rightarrow f_s^m(n)$ in the following way:

If $m = 0$, $f_s^m(n) = n$.
Suppose $m = 1$.
- If $\textrm{dom}(s) = 0$, $f_s^m(n) = n+1$.
- If $\textrm{dom}(s) = \$1$, $f_s^m(n) = f_{s[0]}^n(n)$.
- Otherwise, $f_s^m(n) = f_{s[\$n]}^1(n)$.
Otherwise, $f_s^m(n) = f_s^1(f_s^{m-1}(n))$.

Fast-growing function[]

First of all, we define a computable total map $\Lambda: \mathbb{N}^2 \rightarrow PT$, $(m, n) \rightarrow \Lambda_m(n)$ like so:

$\Lambda_0(0) = 1$.
$\Lambda_0(n+1) = \textrm{四}_{\Lambda_0(n)}(0)$.
$\Lambda_{n+1}(0) = \Lambda_n(1)$.
$\Lambda_{m+1}(n+1) = \Lambda_m(\textrm{四}_{\Lambda_m(n)}(0))$.

Next, we define a total recursive map $g: \mathbb{N}^2 \rightarrow PT$, $n \rightarrow g(n)$ like so:

$g_0(0) = 1$.
$g_0(n+1) = \Lambda_{g(n)}(0)$.
$g_{n+1}(0) = g_n(1)$.
$g_{m+1}(n+1) = g_m(\Lambda_{g_m(n)}(0))$.

Lastly, we define a total recursive map $F: \mathbb{N}^2 \rightarrow \mathbb{N}$, $((m, n) \rightarrow F_m(n))$ like so:

$F_0(n) = f_{\Lambda_{0}(g_0(n))}^1(n)$.
\(F_{n+1}(0) = F_n(1).
$F_{m+1}(n+1) = F_m(\Lambda_{F_m(n)}(0))$.

Normal form[]

We define a subset $OT \subset T$ like so:

For any $n \in \mathbb{N}$, $\textrm{四}_0(\textrm{四}_0(\Lambda(n))) \in OT$.
For any $(s, n) \in OT \times \mathbb{N}$, $s[\$n] \in OT$.

I think that $(OT, <)$ is an ordinal notation, though I'm not sure.

Example #1[]

Let's find the fundamental sequence for $\textrm{四}_2(1)$.

Before we do anything, we need to find the cofinality of $1$. This satisfies rule 3, with $(a, b) = (0, 0)$. Since $\textrm{dom}(0) = 0$, $\textrm{dom}(1) = 1$.$\textrm{四}_2(1)$ satisfies rule 2, with $(a, b) = (2, 1)$. $\textrm{dom}(b) = 1$, so $X[Y] = Y$.

Example #2[]

Let's do something a lot more complicated. Let's find the fundamental sequence of $\textrm{四}_2(0)+\textrm{四}_1(\textrm{四}_2(0))$.

Before we do anything, we need to find the cofinality of $\textrm{四}_2(0)+\textrm{四}_1(\textrm{四}_2(0))$. It satisfies rule Rule 2 with $(a, b) = (\textrm{四}_2(0), \textrm{四}_1(\textrm{四}_2(0)))$. Therefore $\textrm{dom}(\textrm{四}_2(0)+\textrm{四}_1(\textrm{四}_2(0))) = \textrm{dom}(\textrm{四}_1(\textrm{四}_2(0)))$. $\textrm{四}_1(\textrm{四}_2(0))$ satisfies rule 3 with $(a, b) = (1, \textrm{四}_2(0))$, so we have to find $\textrm{dom}(\textrm{四}_2(0))$. This satisfies rule 3 with $(a, b) = (2, 0)$, so $\textrm{dom}(\textrm{四}_2(0)) = \textrm{四}_2(0)$. Since $\textrm{dom}(\textrm{四}_2(0))$ is neither $0$ or $\$1$, $\textrm{dom}(\textrm{四}_1(\textrm{四}_2(0))) = \textrm{四}_2(0)$. We have $\textrm{dom}(\textrm{四}_2(0)+\textrm{四}_1(\textrm{四}_2(0))) = \textrm{四}_2(0)$.

Now that we have cofinality of $\textrm{四}_2(0)+\textrm{四}_1(\textrm{四}_2(0))$, we can calculate the fundamental sequence. It satisfies rule 3 with $(a_1, a_2) = (\textrm{四}_2(0), \textrm{四}_1(\textrm{四}_2(0)))$. We need to now calculate the fundamental sequence for $\textrm{四}_1(\textrm{四}_2(0))$. It satisfies rule 2 with $(a, b) = (1, \textrm{四}_2(0))$. So, we need to calculate the cofinality of $\textrm{四}_2(0)$, which we already know is $\textrm{四}_2(0)$, which is neither $0$ or $\$1$. $\textrm{dom}(\textrm{四}_2(0)) < \textrm{四}_2(0)+\textrm{四}_1(\textrm{四}_2(0))$, so $(\textrm{四}_1(\textrm{四}_2(0)))[Y] = \textrm{四}_1((\textrm{四}_2(0))[Y])$.

Let's find the fundamental sequence for $\textrm{四}_2(0)$ now. It satisfies rule 2, with $(a, b) = (2, 0)$. $\textrm{dom}(0) = 0$, therefore we need to find $\textrm{dom}(2)$. We already know that this equals $1$, and therefore $\textrm{四}_2(0)[Y] = Y$, and therefore $X[Y] = \textrm{四}_1(Y)$.