FANDOM


チェーン表記が、矢印表記の自然な拡張である事を示す。

チェーン表記の定義式

  • ルール1: \(a \rightarrow b \rightarrow c = a\underbrace{\uparrow\ldots\uparrow}_cb = a \uparrow^c b\)
  • ルール2: \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\)
  • ルール3: \(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)
  • ルール4: \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)

の1番目の式では矢印表記が使われているため、チェーン表記が矢印表記の自然な拡張である事は一見して分かりにくいが、実はルール1を

  • ルール1': \(a \rightarrow b = a^b\)

と変えても、次のようにしてルール1が成立することを帰納法で証明出来る。


【証明】ルール 1',2,3,4 が成り立つ時に、ルール 1 が成り立つ事を、\(c\) に関する帰納法で示す。

(1) \(c=1\) の時

\begin{eqnarray*} a \rightarrow b \rightarrow 1 &=& a \rightarrow b \text{ (ルール2)}\\ &=& a^b \text{ (ルール1')} \\ &=& a \uparrow b \uparrow 1 \end{eqnarray*}

よって、ルール1が成り立つ。

(2) \(c\) においてルール1が成り立つと仮定して、\(c+1\) でルール1が成立することを示す。

\begin{eqnarray*} a \rightarrow b \rightarrow (c+1) &=& a \rightarrow [a \rightarrow (b-1) \rightarrow (c+1)] \rightarrow c \text{ (ルール4)}\\ &=& a \uparrow^c [a \rightarrow (b-1) \rightarrow (c+1)] \text{ (ルール1)}\\ \end{eqnarray*}

ここで、今度は \(c+1\) を固定して \(b\) に関する帰納法が必要となる。今、計算しているのは \(a \rightarrow b \rightarrow (c+1)\) なので、\(a \rightarrow (b-1) \rightarrow (c+1)\) についてはルール1が成立しているとする。なお、\(b=1\) の時は、ルール1の両辺が\(a\)となるので、成り立っている。

\begin{eqnarray*} a \rightarrow b \rightarrow (c+1) &=& a \uparrow^c [a \uparrow^{c+1} (b-1)] \text{ (上式の続き、ルール1)}\\ &=& a \uparrow^c [\underbrace{a \uparrow^c a \uparrow^c \ldots \uparrow^c a}_{b-1}] \text{ (矢印表記の定義)}\\ &=& \underbrace{a \uparrow^c a \uparrow^c \ldots \uparrow^c a}_{b} \\ &=& a \uparrow^{c+1} b \text{ (矢印表記の定義)}\\ \end{eqnarray*}

以上で、ルール1が成り立つ事が示された。



ルール1を使う方が計算が分かりやすいし、コンウェイもルール1で説明をしているけれど、ルール1'を使えばルール1は成り立つので、ルール1のかわりにルール1'を使っても同じ事で、実はその方がルールが簡単になるので良いとも言える。ルール1'のかわりにルール1が採用されていることで、チェーンの定義が矢印表記の自然な拡張であることが、かえって見えにくくなっているのかもしれない。

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki