560 ページ

タラノフスキーの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)$$."

## ２階算術を超えるシステム

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.