- Not to be confused with C function.
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.[1] 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 hyp cos, one such notation by Taranovsky, i.e. main system with passthrough, has been shown to be ill-founded[2].
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[1]. 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.[3]. 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[]
Omega-multiplication series: Bultom · Trultom · Quadrultom · Quintultom · Sextultom · Septultom · Octultom · Nonultom · Dekultom · Hektultom · Kilultom · Megultom · Gigultom · Terultom · Petultom · Exultom · Zettultom · Yottultom
Omega-exponetation series: Bexom · Trexom · Quadrexom · Quintexom · Sextexom · Septexom · Octexom · Nonexom · Dekexom · Hektexom · Kilexom · Megexom · Gigexom · Terexom · Petexom · Exexom · Zettexom · Yottexom
Omega-tetration series: Bitetrom · Tritetrom · Quadritetrom · Quintitetrom · Sextitetrom · Septitetrom · Octitetrom · Nonitetrom · Dekotetrom · Hektotetrom · Kilotetrom · Megotetrom · Gigotetrom · Terotetrom · Petotetrom · Exotetrom · Zettotetrom · Yottotetrom
Epsilon(0)-multiplication series: Bultep · Trultep · Quadrultep · Quintultep · Sextultep · Septultep · Octultep · Nonultep · Dekultep · Hektultep · Kilultep · Megultep · Gigultep · Terultep · Petultep · Exultep · Zettultep · Yottultep
Epsilon(0)-exponentiation series: Bexep · Trexep · Quadrexep · Quintexep · Sextexep · Septexep · Octexep · Nonexep · Dekexep · Hektexep · Kilexep · Megexep · Gigexep · Terexep · Petexep · Exexep · Zettexep · Yottexep
Epsilon(0)-tetration series: Bitetrep · Tritetrep · Quadritetrep · Quintitetrep · Sextitetrep · Septitetrep · Octitetrep · Nonitetrep · Dekotetrep · Hektotetrep · Kilotetrep · Megotetrep · Gigotetrep · Terotetrep · Petotetrep · Exotetrep · Zettotetrep · Yottotetrep
Epsilon(1)-addition series: Unaddunep · Baddunep · Traddunep · Quadraddunep · Quintaddunep · Sextaddunep · Septaddunep · Octaddunep · Nonaddunep · Dekaddunep · Hektaddunep · Kiladdunep · Megaddunep · Gigaddunep · Teraddunep · Petaddunep · Exaddunep · Zettaddunep · Yottaddunep
Inserted epsilon series: Uninep · Binep · Trinep · Quadrinep · Quintinep · Sextinep · Septinep · Octinep · Noninep · Dekinep · Hektinep · Kilinep · Meginep · Giginep · Terinep · Petinep · Exinep · Zettinep · Yottinep
Inserted phi series: Uninphi · Binphi · Trinphi · Quadrinphi · Quintinphi · Sextinphi · Septinphi · Octinphi · Noninphi · Dekinphi · Hektinphi · Kilinphi · Meginphi · Giginphi · Terinphi · Petinphi · Exinphi · Zettinphi · Yottinphi
Theta- tetration series: Bitetrommthet · Tritetrommthet · Quadritetrommthet · Quintitetrommthet · Sextitetrommthet · Septitetrommthet · Octitetrommthet · Nonitetrommthet · Dekotetrommthet · Hektotetrommthet · Kilotetrommthet · Megotetrommthet · Gigotetrommthet · Terotetrommthet · Petotetrommthet · Exotetrommthet · Zettotetrommthet · Yottotetrommthet
Omega- subscript series: Bommthet · Trommthet · Quadrommthet · Quintommthet · Sextommthet · Septommthet · Octommthet · Nonommthet · Dekommthet · Hektommthet · Kilommthet · Megommthet · Gigommthet · Terommthet · Petommthet · Exommthet · Zettommthet · Yottommthet
Inserted omega series: Binommwil · Trinommwil · Quadrinommwil · Quintinommwil · Sextinommwil · Septinommwil · Octinommwil · Noninommwil · Dekinommwil · Hektinommwil · Kilinommwil · Meginommwil · Giginommwil · Terinommwil · Petinommwil · Exinommwil · Zettinommwil · Yottinommwil
Inserted \(I_\alpha\) series: Uninotos · Binotos · Trinotos · Quadrinotos · Quintinotos · Sextinotos · Septinotos · Octinotos · Noninotos · Dekinotos · Hektinotos · Kilinotos · Meginotos · Giginotos · Terinotos · Petinotos · Exinotos · Zettinotos · Yottinotos
Inserted \(I(\alpha,\beta)\) series: Uninimah · Binimah · Trinimah · Quadrinimah · Quintinimah · Sextinimah · Septinimah · Octinimah · Noninimah · Dekinimah · Hektinimah · Kilinimah · Meginimah · Giginimah · Terinimah · Petinimah · Exinimah · Zettinimah · Yottinimah
Inserted M series: Uninemar · Binemar · Trinemar · Quadrinemar · Quintinemar · Sextinemar · Septinemar · Octinemar · Noninemar · Dekinemar · Hektinemar · Kilinemar · Meginemar · Giginemar · Terinemar · Petinemar · Exinemar · Zettinemar · Yottinemar
M(α;β)-series: Uninamus · Binamus · Trinamus · Quadrinamus · Quintinamus · Sextinamus · Septinamus · Octinamus · Noninamus · Dekinamus · Hektinamus · Kilinamus · Meginamus · Giginamus · Terinamus · Petinamus · Exinamus · Zettinamus · Yottinamus
Initial tar series: Tritar · Quadritar · Quintitar · Sextitar · Septitar · Octitar · Nonitar · Dekotar · Hektotar · Kilotar · Megotar · Gigotar · Terotar · Petotar · Exotar · Zettotar · Yottotar
Inserted tar series: Unintar · Bintar · Trintar · Quadrintar · Quintintar · Sextintar · Septintar · Octintar · Nonintar · Dekintar · Hektintar · Kilintar · Megintar · Gigintar · Terintar · Petintar · Exintar · Zettintar · Yottintar · Tarintar
By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By aster: White-aster notation · White-aster
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea
By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system
By ふぃっしゅ (Fish): Ackermann function
By koteitan: Ackermann function · Beklemishev's worms · KumaKuma ψ function
By Mitsuki1729: Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table
By みずどら: White-aster notation
By Naruyoko Naruyo: p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great
By 猫山にゃん太 (Nekoyama Nyanta): Flan number 4 version 3 · Fish number 5 · Laver table
By Okkuu: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6
By rpakr: p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation
By ふぃっしゅ (Fish): Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By Okkuu: Verification of みずどら's computation program of White-aster notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory
By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud
See also: Template:Googology in Asia
Sources[]
- ↑ 1.0 1.1 Taranovsky, Dmytro. Ordinal Notation. Retrieved 2014-09-26.
- ↑ Personal 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\}\)
- ↑ My system of number names (FGS) - Traveling To The Infinity