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 \(Y = \textrm{四}_c(d)\) for some \((c, d) \in T^2\).
- 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\).
- Suppose \(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\).
- Suppose \(\textrm{dom}(b) = 0\).
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 \(Q = 0\).
- Suppose \(\textrm{dom}(b) = 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)\).