Taranovsky's C

Taranovsky's \(\textrm C\) is a series of recursively ordered sets described by Dmytro Taranovsky in a self-published web page. The following general frame work to construct a binary function \(C\) from a well-ordered set \((S,<)\) equipped with an additional structure \(D \subset S \times S\) satisfying a suitable condition is explained later. Whether the recursively ordered sets form ordinal notations or not, i.e. the well-foundedness of them, is an unsolved problem in mathematics. However, according to personal communication of C7X with Kingarthur and , one such notation by Taranovsky, i.e. main system with passthrough, has been shown to be ill-foundedPersonal communication of C7X with Kingarthur and hyp cos: For strings \(a,b,c\) with \(b\) a substring of \(a\) (distinguishing distinct positions), let \(R(a,b,c)\) denote \(a\) with the rightmost substring of \(b\) replaced with the string \(c\). Put \(a_0:=``00\Omega_2\Omega_2\textrm C0\Omega_20\Omega_2\Omega_2\textrm {CC}\Omega_2\textrm {CCCC}0\Omega_20\Omega_2\Omega_2\textrm {CC}0\Omega_2\Omega_2\textrm C0\Omega_20\Omega_2\Omega_2\textrm {CC}\Omega_2\textrm {CCCCCCCCCCC}\!"\) and \(a_{i+1}:=R(a_i,``0\Omega_20\Omega_2\Omega_2\textrm {CC}\Omega_2\textrm {CCCC}\!",``0\Omega_20\Omega_2\Omega_2\textrm {CC}0\Omega_2\Omega_2\textrm C0\Omega_20\Omega_2\Omega_2\textrm {CC}\Omega_2\textrm {CCCCCCCC}\Omega_20\Omega_2\Omega_2\textrm {CC}0\Omega_2\Omega_2\textrm C0\Omega_20\Omega_2\Omega_2\textrm {CC}\Omega_2\textrm {CCCCCCCCC}\!"\); the set given by Kingarthur with no least element under Taranovsky's lexicographic relation is \(\{a_i:i\in\omega\}\).
== Explanation ==
Let \(0_S\) denote the least element of \((S,<)\). For an \(a \in S\), we put \(C_a := \{c \in S : (c,a) \in D\}\), \(a+1 := \min \{c \in S : a < c\}\) (assume the existence), and \((a) := \{c \in S : c < a\}\). For an \(S' \subset S\), we denote by \(\lim(S') \subset S\) the subset of limits of elements of \(S'\) in \((S,<)\). We say that \(D\) is a degree for \((S,<)\) if the following hold:
*\(C_{0_S} = S\)
*\(\forall a \in S: a \neq 0_S \Rightarrow 0_S \notin C_a\)
*\(\forall a \in \lim(S): C_a = \bigcup_{b < a} C_b\).
*\(\forall a \in S: C_{a+1} = \lim(C_a) \lor \exists d \in \lim(S) \cap (a+1) \land C_{a+1} = \lim(C_a) \cup (d+1)\)
If \(D\) is a degree for \((S,<)\), then set \(C(a,b) := \min\{c \in C_a : b < c\}\). In particular, this construction works for a limit ordinal \(\eta\) equipped with a degree \(D \subset \eta \times \eta\) for \((\eta,\in)\). Since \(D\) is not unique, the resulting function \(C\) heavily depends on the choice of \(D\). Taranovsky introduced several explicit examples of degrees.
Define a partial ordinal notation system \(O\) as a partial mapping from ordinals below \(\eta\) to finite strings comprised of symbols and ordinals such that \(O(a)\) is undefined if \(a\) occurs in a string in the range of \(O\). Given a partial ordinal notation system \(O\) and a degree \(D\) for \((\eta,\in)\), we define Taranovsky's notation for \(a\):
* If \(O(a)\) is defined, then we simply use the string \(O(a)\) to notate \(a\).
* Otherwise, let \(b,c\) be ordinals so that \(a = C(b, c) \wedge b'>b \Rightarrow C(b', c) > C(b, c) \wedge c' < c \Rightarrow C(b, c') < C(b, c)\). We then use the string "\(C(b,c)\)."
== Second-order arithmetic ==
One implementation Taranovsky conjectures to reach further than the proof-theoretic ordinal of second-order arithmetic, which if true would make it an exceptionally strong system. This notation is also referred to as the "main ordinal notation system" on the page.
For \(k\in\mathbb{N}\), define the binary relation "\(a\) is \(k\)-built from below by \(b\)" over ordinals as follows:
* \(a\) is \(0\)-built from below by \(b\) iff \(a < b\).
* \(a\) is \(k+1\)-built from below by \(b\) iff the standard representation of \(a\) does not contain ordinals above \(a\), except those that are a nonstrict subterm of some ordinal that is \(k\)-built from below by \(b\).
Taranovsky's notation, then, is a countably infinite family of notations indexed by positive integer \(n\) defined individually as follows:
* The language consists of constants "\(0\)" and "\(\Omega_n\)" and a binary function "\(\textrm C\)" written in "postfix form" (\(``C(x,y)\!"\mapsto``yxC\!"\)).
* Ordering is lexicographic with "\(\textrm C\)" < "\(0\)" < "\(\Omega_n\)".
* The strings "\(0\)" and "\(\Omega_n\)" are in standard form.
* The string "\(ab\textrm C\)" is in standard form iff all the following are true:
** "\(a\)" and "\(b\)" are in standard form.
** If "\(a\)" is of the form "\(de\textrm C\)" (i.e. "\(ab\textrm C\)" is of the form "\(de\textrm Cb\textrm C\)"), \(b \leq e\) according to the aforementioned lexicographic ordering.
** "\(b\)" is \(n\)-built from below by "\(ab\textrm C\)".
For the standardness, a Japanese Googology Wiki user rpakr implemented it into yabasic (cf. #Computation programs).
For \(n = 1\), Taranovsky showed that the system reaches the Bachmann-Howard ordinal, and noted that the full system shows superficial similarity to another system defined by Taranovsky called "Degrees of Reflection".
===Properties of built-from-below===
In order to make the \(\prec_n\) relations more clear, we list some facts about them:
*For any terms \(a,b\) of the notation and \(n\in\omega\), \(a\prec_n b\rightarrow a\prec_{n+1}b\).
*For any natural \(n>0\) and any term \(b\) (in the \(n\)th system), the statement "\(\Omega_n\) is \(n\)-built-from-below by \(b\)" is vacuously true.
*More generally, for a natural \(n>0\), a term \(a\) (in the \(n\)th system) where \(\forall(a'\sqsubseteq a)(a'\le a)\), and any term \(b\) (in the \(n\)th system), the statement "\(a\) is \(n\)-built-from-below by \(b\)" is vacuously true. This more general property applies to \(a\) whose parse tree is entirely \(\le a\), such as \(C(\Omega_2,\Omega_2)\) and \(C(C(0,\Omega_5),\Omega_5)\).
== Large numbers ==
Although Taranovsky has not coined a specific large number, a Googology Wiki user Denis Maksudov coined several large numbers based on Taranovsky's \(C\) known as Tar series, using the fast-growing hierarchy with fundamental sequences for Taranovsky's notation.My system of number names (FGS) - Traveling To The Infinity. The definition heavily depends on the well-foundedness of Taranovsky's \(C\), and hence the well-definedness of those numbers is unknown. If they are actually well-defined, then they are expected to be very large.
== Computation programs ==
* rpakr, TON Stanardness, Github. (A yabasic program for determining standardness of an expression.)
== See also ==
* List of systems of fundamental sequences#Taranovsky's C
== Sources ==
Category:Ordinal notations
Category:Unsolved problems
ja:タラノフスキーのC
Category:Numbers by Denis Maksudov
Category:Higher computable level
Category:Numbers
Category:Incomplete