自然数 (7)数学的帰納法
命題24
$A~$を集合、$d:A\to\mathbb{N}~$を写像とし、$A_n=\{a\in A\mid d(a)=n\}~(n\in\mathbb{N})~$とおく。各元$~a\in A~$についての命題$~P(a)~$があり、次が成り立つとする。 \begin{align} (1)&~{}^{\forall}a\in A_0, P(a)\\ (2)&~{}^{\forall}n\in\mathbb{N},({}^{\forall}a\in A_n, P(a)) \Longrightarrow ({}^{\forall}a\in A_{n+1}, P(a)) \end{align} このとき、${}^{\forall}a\in A, P(a)~$が成り立つ。
各自然数$~n\in\mathbb{N}~$についての命題
\[
Q(n) ~:\Longleftrightarrow~ {}^{\forall}a\in A_n, P(a)
\]
を考える。
このとき、条件(1),(2)は次のようになる。 \begin{align} (1)&~Q(0)\\ (2)&~{}^{\forall}n\in\mathbb{N},Q(n) \Rightarrow Q(n+1) \end{align} 数学的帰納法よりすべての$~n\in\mathbb{N}~$において$~Q(n)~$が成り立つ。
$d~$は$~\mathbb{N}~$に値をもつので主張が得られる。
$$\square$$
このとき、条件(1),(2)は次のようになる。 \begin{align} (1)&~Q(0)\\ (2)&~{}^{\forall}n\in\mathbb{N},Q(n) \Rightarrow Q(n+1) \end{align} 数学的帰納法よりすべての$~n\in\mathbb{N}~$において$~Q(n)~$が成り立つ。
$d~$は$~\mathbb{N}~$に値をもつので主張が得られる。
命題25
$A~$を集合、$d:A\to\mathbb{N}~$を写像とし、$A_n=\{a\in A\mid d(a)=n\}~(n\in\mathbb{N})~$とおく。各元$~a\in A~$についての命題$~P(a)~$があり、次が成り立つとする。 \begin{align} (1)&~{}^{\forall}a\in A_0, P(a)\\ (2)&~{}^{\forall}n\in\mathbb{N},({}^{\forall}k\in\mathbb{N}, 0\le k\le n \Rightarrow {}^{\forall}a\in A_n, P(a)) \Longrightarrow ({}^{\forall}a\in A_{n+1}, P(a)) \end{align} このとき、${}^{\forall}a\in A, P(a)~$が成り立つ。
命題24と同様に自然数に関する帰納法(ここでは定理13)に帰着すればよい。
$$\square$$