タラノフスキーのC (Taranovsky's C) は Dmytro Taranovsky がホームページで公表した順序数を表記するシステムである[1]。2005年8月7日に最初のバージョンが公表され、その後アップデートが続けられている。またTaranovsky本人によって順序数表記を計算するPythonによるプログラムが公開されている[2]

一般的な順序数表記

Let \(\eta\) be an ordinal, and let \(0^S\) and let \(\text{Ld}(a, b)\) be the statement that \(a\) is a limit of ordinals \(c\) such that \((c, b) \in D\). Let \(D\) be the following binary relation over \(\eta\):

  • \(\forall a < \eta: (a, 0) \in D\)
  • \(\forall a < \eta: a \neq 0 \Rightarrow (0, a) \notin D\)
  • \(\forall b \in \text{Lim} \cup \eta: (a, b) \in D \Leftrightarrow \forall c < b: (a, c) \in D\).
  • \(\forall b: (a, b) \in D \Leftrightarrow \text{Ld}(a, b + 1)\)
  • \(\forall b: \exists d \in \text{Lim} \cup \eta: d \leq b \Rightarrow \forall c: (c, a + 1) \in D \Leftrightarrow (c \leq d \vee \text{Ld}(c, b))\)

Then \(C(a, b) = \min\{c : c \in \eta \wedge c > b \wedge (c, a) \in D\}\).

Define a partial ordinal notation system \(O\) as a partial mapping from ordinals to finite strings comprised of symbols and ordinals such that \(O(\alpha)\) is undefined if \(\alpha\) occurs in a string in the range of \(O\). Given a partial ordinal notation system \(O\), 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)\)."

2階算術を超えるシステム

一般的な順序数表記の実装として、タラノフスキーが主要な順序数表記システム (main ordinal notation system) として定義した表記は、タラノフスキーが2階算術証明論的順序数よりも強いであろうとしている。それが本当であれば、極めて強いシステムである。

For \(k \geq 0\), 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 use ordinals above \(a\) except in the scope of an ordinal \(k\)-built from below by \(b\).

Taranovsky's notation, then, is an 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 "\(C\)" written in reverse Polish notation.
  • Ordering is lexicographic with "\(C\)" < "\(0\)" < "\(\Omega_n\)".
  • The strings "\(0\)" and "\(\Omega_n\)" are in standard form.
  • The string "\(abC\)" is in standard form iff all the following are true:
    • "\(a\)" and "\(b\)" are in standard form.
    • If "\(a\)" is of the form "\(cdC\)", \(b \leq d\) according to the aforementioned lexicographic ordering.
    • "\(b\)" is \(n\)-built from below by "\(abC\)".

For \(n = 1\), Taranovsky showed that the system reaches the Bachmann-Howard ordinal.

解析

参考文献

特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。