再帰・数学的帰納法

離散数学は、ZF集合論 (Zermelo-Fraenkel set theory)、 および PA公理 (Peano axioms) に基づく標準モデルに依拠して体系化されている。そのため、再帰的定義 (recursive definition) においては 整礎性 (well-foundedness)・非循環性 (non-cyclicity) が要求され、基底 (base) の存在が必須である。

• 「再帰」$=$「自己参照」$+$「基底」

一方、離散数学には 命題論理 (propositional logic)、推論規則 (inference rule)、証明論 (proof theory) 的体系など、より 形式論理 (formal logic) に近い領域も含まれる。この領域では、ゲーデル文や停止性問題などに見られるように、基底を欠ける再帰的・自己言及的構造が理論的に取り扱われる。

• 「再帰」$=$「自己参照」

再帰的定義

• 例：
  • 階乗とは？(一般的な定義)：正の整数 $n$ に対して、$n$ の階乗 ($n!$) は以下となる。
  \[\begin{align*} n! & =\Pi^n_{k=1}k \\ & =1\times 2\times\cdots\times (n-1)\times n \end{align*}\]
  • 階乗とは？(再帰的な定義)：正の整数 $n$ に対して、$n$ の階乗 ($n!$) は以下となる。
  \[\begin{align*} n! & = \begin{cases} 1 & n=1\textrm{の時} \\ n\times (n-1)! & n>1\textrm{の時} \end{cases} \end{align*}\]
  • 実際の計算：
    • $n=1$の時、$1!=1$
    • $n=2$の時、$2!=2\times 1!\,=\cdots=2\times 1=2$
    • $n=3$の時、$3!=3\times 2!\,=\cdots=3\times 2=6$
    • $n=4$の時、$4!=4\times 3!\,=\cdots=4\times 6=24$
    • $\cdots$
      • 動的計画法 (Dynamic Programming) での メモ化再帰 (memoized recursion) により、各部の「$=\cdots$」の計算が省略可能
        • 同じ部分問題を何度も解くことを避けるために、中間結果を保存 (メモ化)
        • 時間計算量が減るが、空間計算量が増える

自己参照

「自己参照」は、矛盾を引き起す可能性がある

• 嘘つきのパラドックス：「この文は嘘である」
  • $L=$「$L$は偽」
  • 仮に $L$ が真だとすると、「$L$ は偽」と矛盾
  • 逆に $L$ が偽だとすると、「$L$ は偽」は真だったので、また矛盾
• 停止性問題 (Halting Problem)：プログラムと入力を受け取って、その計算は有限時間で停止するか (を判断できるプログラムが存在するか)？
  • この問題を解けるプログラム $S(P,I)$ が存在すると仮定する、ただし、$P$ は問題プログラム、$I$ は $P$ の入力
  \[\begin{align*} S(P,I)=\begin{cases} 1 & P(I)\,\textrm{停止する時、かつその時に限り} \\ 0 & P(I)\,\textrm{停止しない時、かつその時に限り} \end{cases} \end{align*}\]
  • あるプログラム $D$ (入力は $P$ と想定) を以下の規則に従って作る
  \[\begin{align*} D(P)=\begin{cases} \textrm{停止させない} & S(P,P)=1\textrm{の時} \\ \textrm{停止させる} & S(P,P)=0\textrm{の時} \end{cases} \end{align*}\]
  • $S$ は $D(D)$ が停止するかどうかを判断できるか？(決定不能)
    • 仮に $S(D,D)=1$ だとすると、$S$ の定義により、$D(D)$ は停止する。これは $D$ の定義と矛盾
    • 逆に $S(D,D)=0$ だとすると、$S$ の定義により、$D(D)$ は停止しない。これも $D$ の定義と矛盾
  • カントールの対角線論法 (Cantor’s Diagonal Argument)
    • 非可算集合 \(F=\{f(i)\mid f(i)=0.a_{i1}a_{i2}a_{i3}\ldots\textrm{かつ}a_{ij}\in\mathbb{N}\}\)
    • \[\begin{align*} b_i=\begin{cases} 1 & a_{ij}\neq 1\textrm{の時} \\ 2 & a_{ij}=1\textrm{の時} \end{cases}, 0.b_1b_2b_3\ldots\notin F \end{align*}\]
• ゲーデルの不完全性定理 (Gödel’s Incompleteness Theorems) からの思考
  • ある日、賢明なゲーデルは「この文は嘘である」を「この文は真であると証明することはできない」に書き換えた。では、この文は真であろうか？

PA公理 (非形式的な説明)

1. $0$ は自然数である。
2. 任意の自然数 $a$ に対して、後続数 $a’$ が存在し、それも自然数である。後続数は、ある自然数のすぐ次の数である。例えば、$0$ の後続数は $1$、$1$ の後続数は $2$ である。
3. 任意の自然数 $b,c$ に対して、$b=c$ の時、それらの後続数も等しくなる ($b’=c’$)。逆に、後続数が等しいなら元の数も等しい。
4. $0$ はどの自然数の後続数でもない。
5. 以下の2点が成立すれば、ある命題はすべての自然数について成り立つとなる。
   5.1. その命題が $0$ に対して成り立つこと。
   5.2. 任意の自然数 $a$ に対し、もしその命題が $a$ に対して成り立つならば、$a’$ に対しても成り立つこと。

数学的帰納法 (Mathematical Induction, $=$ PA (第5) 公理)

• 原理：「$0$ に成り立ち、任意の自然数 $n$ に成り立てば $n+1$ にも成り立つ命題は、すべての自然数に成り立つ」($\star$ 正の整数の範囲なら、$0$ を $1$ に変更)
• 千年の歴史をもつ、今もなお使われる数学的証明法
• PA公理 (1891年) によって帰納的推論の正当性を保証

数学的帰納法の手順

• 「任意の正の整数 $n$ に対して、$P(n)$」という形の命題の証明
  1. (基底段階) $P(1)$ を証明
  2. (帰納段階) 「任意の正の整数 $k$ に対して、$P(k)$ ならば $P(k+1)$」を証明

• 例：任意の正の整数$n$に対して、$2n\le 2^n$ となることを証明せよ。

  証明：

  • (基底段階)まず、$n=1$ の時に正しいことを証明する。
  • $n=1$ の時に、左辺 $=2n=2$、右辺 $=2^n=2$、左辺 $=$ 右辺
  • したがって、$2n\le 2^n$ であり、正しい。
  • (帰納段階) 次に、任意の正の整数 $k$ を考える。
  • $2k\le 2^k$ であると仮定する。
  • $2(k+1)=2k+2$
  • したがって、$2(k+1)\le 2^k+2\le 2^k+2^k=2^{k+1}$
  • したがって、$2(k+1)\le 2^{k+1}$ であり、正しい。$~\square$