COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

自然数

理論

自然数と集合

自然数全体から成る集合の存在

 自然数全体から成る集合は, 無限公理の主張を満たす集合の部分集合全体の共通部分として定義される.

定理≪自然数全体から成る集合の存在≫

 無限公理を満たす集合 $N$ に対して, $N$ の部分集合で無限公理の主張を満たすもの全体から成る集合族を $\widetilde N$ とおく.
このとき, $\widetilde N$ の共通部分 $\mathbb N = \bigcap\widetilde N \subset N$ は $N$ のとり方によらず一意に定まる.

証明

 $\widetilde N$ は冪集合の公理と分出公理によって存在が保証され, 外延性公理によって一意に定まることに注意しておく.
無限公理より $N \in \widetilde N$ だから, $\widetilde N \neq \varnothing.$
また, 任意の $x\in \bigcap\widetilde N,$ $M\in \widetilde N$ に対して $x \in M,$ $M \subset N$ だから, $x \in N.$ よって, $\bigcap\widetilde N \subset N.$
$N'$ も無限公理の主張を満たす集合とする.
$N\cap N' \subset N$ より $\mathscr P(N\cap N') \subset \mathscr P(N)$ だから, $\widetilde{N\cap N'} \subset \widetilde N.$
よって, $\bigcap\widetilde{N\cap N'} \supset \bigcap\widetilde N.$
一方, $x \in \bigcap\widetilde{N\cap N'},$ $M\in \widetilde N$ とすると, $M\cap N' \in \widetilde{N\cap N'}$ より $x \in M\cap N'$ だから, $x \in M.$
この $x,$ $M$ は任意だから, $\bigcap\widetilde{N\cap N'} \subset \bigcap\widetilde N.$
よって, $\bigcap\widetilde{N\cap N'} = \bigcap\widetilde N.$
同様に $\bigcap\widetilde{N\cap N'} = \bigcap\widetilde N'$ も成り立つから, $\bigcap\widetilde N = \bigcap\widetilde N'.$

定義≪自然数と集合≫

(1)
集合 $\mathbb N$ の元を自然数(natural number)と呼ぶ.
(2)
空集合 $\varnothing$ を $\mathbb N$ の元と見るとき, $0$ で表すこともある.
(3)
各 $n\in \mathbb N$ に対して, $n\cup\{ n\}$ を $n$ の直後(successor)と呼び, $n^+$ で表す.
(4)
$1 = 0^+,$ $2 = 1^+,$ $3 = 2^+,$ $4 = 3^+,$ $5 = 4^+,$ $6 = 5^+,$ $7 = 6^+,$ $8 = 7^+,$ $9 = 8^+$ とおく.
 $n^+ = n\cup\{ n\}$ は通常 $n+1$ と書かれるが, $1 = 0+1$ という表記を避けるため, この記法を採用した. これを $n'$ で表す文献も多いが, 本稿では 別に与えられた自然数を表す記号として用いる. 定義より,
$x \in n^+$ $\iff$ $x \in n$ または $x = n.$

Peano の公理

 上記の定義では, 自然数は $0,$ $1 = \{ 0\},$ $2 = \{ 0,\ 1\},$ $3 = \{ 0,\ 1,\ 2\},$ $\cdots$ のようになり, 数の間に包含関係 $0\subset 1\subset 2\subset 3\subset \cdots$ が成り立つ. これは一見奇妙に思われるが, 自然数全体から成る集合 $\mathbb N$ が次の Peano の公理を満たすことから, $\mathbb N$ に関する代数的な諸性質が導かれる:

定理≪Peano の公理の満足≫

 自然数全体 $\mathbb N$ は次の条件を満たす:
(i)
直後の存在: 任意の $n\in \mathbb N$ に対して, $n^+ \in \mathbb N.$
(ii)
最小数の存在: $n_0 \in \mathbb N$ で任意の $n\in \mathbb N$ に対して $n_0 \neq n^+$ を満たすものが存在する.
(iii)
数学的帰納法の原理: 任意の集合 $N \subset \mathbb N$ に対して, ($m \in N$ かつ ($n\in \mathbb N$ $ \Rightarrow$ $n^+ \in \mathbb N$)) $\Longrightarrow$ $N = \mathbb N.$
(iv)
直後をとる写像の単射性: 任意の $n,$ $n' \in \mathbb N$ に対して, $n^+ = n'^+$ $\Longrightarrow$ $n = n'.$

証明

(i)
明らか.
(ii)
任意の $n\in \mathbb N$ に対して, $n \in n\cup\{ n\}$ より $n\cup \{ n\} \neq \varnothing$ すなわち $n^+ \neq 0$ だから, $n_0 = 0$ は条件を満たす.
(iii)
前半の条件を仮定する.
$N$ は無限公理の主張を満たすから, $\mathbb N \subset N.$
これと仮定 $N \subset \mathbb N$ より, $N = \mathbb N.$
(iv)
$n^+ = n'^+$ とすると, $n \in n^+ = n'^+$ かつ $n' \in n'^+ = n^+$ より,
$n = n'$ または ($n \in n'$ かつ $n' \in n.$)
次の補題より $n \in n',$ $n' \in n$ はそれぞれ $n \subsetneqq n',$ $n' \subsetneqq n$ を意味するから, 同時に成り立つことはない. ゆえに, $n = n'.$

補題≪自然数の帰属関係の特徴付け≫

 任意の自然数 $m,$ $n$ に対して, $m \in n$ $\iff$ $m \subsetneqq n.$

証明

($\Rightarrow$)
任意の $m \in \mathbb N$ に対して \[ m \in n \Longrightarrow m \subsetneqq n \quad \cdots [1]\] を満たす $n \in \mathbb N$ 全体を $N_1$ とおく.
(1-i)
任意の $m \in \mathbb N$ に対して, $m \in 0$ は偽だから, $n = 0$ に対して $[1]$ は自動的に成り立つ. よって, $0 \in N_1.$
(1-ii)
$n \in N_1$ とする. $m \in \mathbb N,$ $m \in n^+$ とすると, $m \in n$ または $m = n.$
  • $m \in n$ のとき, $n \in N_1$ より $m \subsetneqq n$ だから, $n \subset n^+$ と合わせると, $m \subsetneqq n^+.$
  • $m = n$ のとき, $m \subset n$ であり, $n \in N_1$ より $n \subsetneqq n^+$ でなければならないから($n = n^+$ とすると $n \in n$ より $n \subsetneqq n$ となり, $n \neq n$ となってしまう), $m \subsetneqq n^+.$
よって, $n^+ \in N_1.$
ゆえに, 数学的帰納法の原理より $N_1 = \mathbb N$ となり, 任意の $n \in \mathbb N$ に対して $[1]$ が成り立つ.
($\Leftarrow$)
任意の $m \in \mathbb N$ に対して \[ m \subsetneqq n \Longrightarrow m \in n \quad \cdots [2]\] を満たす $n \in \mathbb N$ 全体を $N_2$ とおく.
(2-i)
任意の $m \in \mathbb N$ に対して, $m \subsetneqq 0$ は偽だから, $n = 0$ に対して $[2]$ は自動的に成り立つ. よって, $0 \in N_2.$
(2-ii)
$n \in N_2$ とする. さらに, $m \in \mathbb N,$ $m \subsetneqq n^+$ とする.
仮に $n \in m$ とすると, 前半の結果より $n \subsetneqq m$ となるから, $n^+ = n\cup\{ n\} \subset m$ となって $m \neq n^+$ に反する.
よって, $n \notin m$ より $m \neq \{ n\}$ したがって $m \not\subset \{ n\}$ となることが対偶法によって分かるから, $m \subset n^+\setminus\{ n\} = n$ すなわち $m \subsetneqq n$ または $m = n.$
  • $m \subsetneqq n$ のとき, $n \in N_2$ より $m \in n$ だから, $m \in n\cup\{ n\} = n^+.$
  • $m = n$ のとき, $m \in n^+.$
よって, $n^+ \in N_2.$
ゆえに, 数学的帰納法の原理より $N_2 = \mathbb N$ となり, 任意の $n \in \mathbb N$ に対して $[2]$ が成り立つ.

数学的帰納法

定理≪数学的帰納法≫

 自然数 $n$ に関する命題 $\varphi (n)$ について, 次の条件が同時に成り立つならば, 任意の自然数 $n$ に対して $\varphi (n)$ は真である:
(i)
$\varphi (0)$ は真.
(ii)
任意の $n\in\mathbb N$ に対して $\varphi (n)$ が真$\Longrightarrow$ $\varphi (n^+)$ は真.

証明

 条件 (i), (ii) を仮定する.
$\mathbb N$ の部分集合 $N = \{ n\in\mathbb N|\varphi (n)\}$ は仮定 (i) より $0 \in N$ を満たし, 仮定 (ii) より $n \in N$ $\Longrightarrow$ $n^+ \in N$ を満たすから, 数学的帰納法の原理より, $N = \mathbb N.$
ゆえに, 任意の $n\in \mathbb N$ に対して $\varphi (n)$ が成り立つ.
 以下, 編集中.