再帰・数学的帰納法

離散数学は，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$