序数としての自然数と、その基数性

公理

1. \(1\in\mathbb{N}.\)
2. \(\mathbb{N}'\subseteq\mathbb{N}.\)
3. \(x\in\mathbb{N}\) に対して、\(x'\neq 1.\)
4. \(x,y\in\mathbb{N}\) に対して、\(x\neq y\) ならば \(x'\neq y'.\)
5. \(M\subseteq\mathbb{N}\) に対して、\(1\in M\) かつ \(M'\subseteq M\) ならば、\(M=\mathbb{N}.\)

ただし、関数 \('\) の定義域における任意の部分集合 \(A\) に対して、集合 \(A'\) を \(A'=\{x\in A\mid x'\}\) で定義し、また、全称限量子に当たる言葉（「すべての」や「任意の」）は省略している。

定理 1

数学的帰納法（以下、単に帰納法と呼ぶ）が成り立つ。すなわち、変項 \(x\) を含む任意の命題関数を \(P(x)\) とするとき、すべての \(x\in\mathbb{N}\) に対して \(P(x)\) であることを証明するには、次の二つを示せばよい。

1. \(P(1).\)
2. \(x\in\mathbb{N}\) に対して、\(P(x)\) ならば \(P(x').\)

証明

集合 \(M\) を \(M=\{x\in\mathbb{N}\mid P(x)\}\) と定義すると、第一の条件より \(1\in M.\) 第二の条件より \(M'\subseteq M.\) ゆえに、公理 v より \(M=\mathbb{N}\) で、これはすべての \(x\in\mathbb{N}\) に対して \(P(x)\) であることを意味している。

定理 2

\(x\neq 1\) ならば、\(y'=x\) となる自然数 \(y\) が存在する。

証明

\(x\neq 1\) ならばある自然数 \(y\) に対して \(y'=x\) である、という命題関数を \(P(x)\) と表すことにして、\(x\) に関する帰納法（定理 1）を用いる。

\(1\neq 1\) は成り立たない。ゆえに、\(P(1)\) は結論部分に関係なく形式的に成り立つ。

また、明らかに \(k'=k'\) であるから、\(y'=k'\) となる自然数 \(y\) が存在すると言える。ゆえに、\(P(k')\) が仮定部分に関係なく形式的に成り立つ。さらに、\(P(k)\) ならば \(P(k'),\) も形式的に成り立つ。

定理 3

\(x'\neq x.\)

証明

帰納法による。

公理 iii より \(1'\neq 1.\)

\(k'\neq k\) と仮定すると、公理 iv より \((k')'\neq k'.\)

定理 4

一変数関数の帰納的定義が正当化される。すなわち、関数 \(f\) の値 \(f(x)\) をすべての自然数 \(x\) に対して定義するとき、次の形式を持つ二つの式で定義すればよい。 \[ \begin{cases} f(1)=a \\ f(x')=g(x,f(x)) & (x\in\mathbb{N}) \end{cases} \] ただし、\(a\) は何らかの定数項（数とは限らない）で、\(g\) は既に定義されている関数であり、等式の左辺を右辺で定義するとする。

証明

帰納法による。

公理 iii により \(1\neq x'\) であるので、\(f(1)\) は第一の式のみによって完全に定義され、かつ、定義は重複しない。

同様に、\(f(k')\) は第二の式のみによって、ただし \(f(k)\) の定義に依存する形で定められている。そして、むしろそれゆえ、\(f(k)\) が重複なく定義されているならば、\(f(k')\) もまた定義されており、なおかつ、重複した定義ではない。というのは、もし定義が重複したのなら、ある自然数 \(m,\) \(n\) に対して、\(g(m,f(m))\neq g(n,f(n))\) にもかかわらず \(m'=n'\), すなわち、\(m\neq n\) にもかかわらず \(m'=n'\) ということになるが、これは公理 iv に反するからである。

定義 I

任意の自然数 \(x\) に対してある自然数の集合 \([x]\) を返す関数 \([\;]\) を、帰納的定義（定理 4）によって次のように定義する。 \[ \begin{cases} [1]=\{1\} \\ [x']=[x]\cup\{x'\} & (x\in\mathbb{N}) \end{cases} \] \([x]\) を \(x\) までの数という。公理 i, ii と帰納法により、\([x]\subseteq\mathbb{N}\) が常に成り立つ。

定理 5

\(x\in[x].\)

証明

\(x=1\) ならば、定義 I より \(x=1\in[1]=[x].\) \(x\neq 1\) ならば、定理 2 より \(y'=x\) となる \(y\) が存在し、定義 I より \(x=y'\in[y']=[x].\)

定理 6

\(1\in[x].\)

証明

帰納法による。

定理 5 より \(1\in[1].\)

\(1\in[k]\) と仮定すると、定義 I より \(1\in[k]\cup\{k'\}=[k'].\)

定理 7

\(y\in[x]\) ならば \([y]\subseteq[x].\)

証明

\(x\) に関する帰納法による。

\(y\in[1]\) ならば、定義 I より \(y=1\) であり、\([y]=[1]\subseteq[1].\)

\(y\in[k]\) ならば \([y]\subseteq[k],\) と仮定する。\(y\in[k']\) のとき、定義 I より、\(y\in[k]\) または \(y=k'.\) もし \(y\in[k]\) ならば、帰納法の仮定より \([y]\subseteq[k]\) で、すなわち \([y]\subseteq[k]\cup\{k'\}=[k'].\) もし \(y=k'\) ならば、\([y]=[k']\) で、明らかに \([y]\subseteq[k'].\)

定理 8

\(y\in[x]\) かつ \(y'\notin[x]\) ならば、\(x=y.\)

証明

\(x\) に関する帰納法による。

\(y\in[1]\) かつ \(y'\notin[1]\) のとき、\(y\in[1]\) と定義 I より \(1=y.\)

\(y\in[k]\) かつ \(y'\notin[k]\) ならば、\(k=y,\) と仮定する。\(y\in[k']\) かつ \(y'\notin[k']\) のとき、定義 I より、\(y\in[k]\) または \(y=k'\) で、\(y'\notin[k]\) かつ \(y'\neq k'.\) ゆえに、ここでもし \(k'\neq y\) だとすると \(y\in[k]\) であることになり、\(y'\notin[k]\) と帰納法の仮定より \(k=y\) となるので、\(k'=y'\) が導かれるが \(y'\neq k'\) に反する。ゆえに \(k'=y.\)

定理 9

\(y'\in[x]\) ならば \(y\in[x].\)

証明

\(x\) に関する帰納法による。

公理 iii より \(y'\neq 1\) で、定義 I より \(y'\notin[1]\) となるので、\(y'\in[1]\) ならば \(y\in[1],\) は形式的に成り立つ。

\(y'\in[k]\) ならば \(y\in[k],\) と仮定する。\(y'\in[k']\) のとき、定義 I より \(y'\in[k]\) または \(y'=k'.\) \(y'\in[k]\) ならば、帰納法の仮定より \(y\in[k]\) で、定義 I より \(y\in[k]\subseteq[k'].\) \(y'=k'\) ならば、公理 iv より \(y=k\) で、定理 5 と定義 I より \(y\in[k]\subseteq[k'].\)

定理 10

\(x'\notin[x].\)

証明

帰納法による。

公理 iii より \(1'\neq1\) であるので、\(1'\notin\{1\}=[1].\)

\(k'\notin[k]\) と仮定する。ここでもし \((k')'\in[k']\) だとすると、\((k')'\in[k']=[k]\cup\{k'\}\) であり、しかし定理 3 より \((k')'\neq k'\) であるから、\((k')'\in[k].\) ゆえに、定理 9 より \(k'\in[k]\) であることになり、帰納法の仮定に反する。したがって、\((k')'\notin[k'].\)

定理 11

\([x]=[y]\) ならば \(x=y.\)

証明

\([x]=[y]\) のとき、定理 5 より \(y\in[y]=[x].\) 一方、定理 10 より \(y'\notin[y]=[x].\) ゆえに、定理 8 より \(x=y.\)

定理 12

\(y\notin[x]\) ならば \([x]\subseteq[y].\)

証明

\(y\) に関する帰納法による。

定理 6 より \(1\in[x].\) すなわち、\(1\notin[x]\) ならば \([x]\subseteq[1],\) は形式的に成り立つ。

\(k\notin[x]\) ならば \([x]\subseteq[k],\) と仮定する。そして、\(k'\notin[x]\) とする。もし \(k\notin[x]\) ならば、帰納法の仮定より \([x]\subseteq[k]\) で、定義 I より \([k]\subseteq[k']\) であるから \([x]\subseteq[k'].\) もし \(k\in[x]\) ならば、\(k'\notin[x]\) と定理 8 により \(x=k\) であり、\([x]=[k]\subseteq[k'].\)

定理 13

\([x]\subseteq[y]\) または \([y]\subseteq[x].\)

証明

\(x\) に関する帰納法による。

定理 6 と定理 7 より \([1]\subseteq[y].\)

\([k]\subseteq[y]\) または \([y]\subseteq[k],\) と仮定する。もし \([k']\nsubseteq[y]\) ならば、定義 I より \([k]\cup\{k'\}\nsubseteq[y].\) すなわち、\([k]\nsubseteq[y]\) または \(k'\notin[y].\) \([k]\nsubseteq[y]\) ならば、帰納法の仮定より \([y]\subseteq[k]\) で、\([y]\subseteq[k]\cup\{k'\}=[k'].\) \(k'\notin[y]\) ならば、定理 12 により \([y]\subseteq[k'].\)

定義 II

\(x\leq y\) を \([x]\subseteq[y]\) で定義する。\(x\leq y\) を \(y\geq x\) とも書く。

\(x\leq y\) かつ \(x\neq y\) であることを \(x\lt y\) と書く。\(x\lt y\) を \(y\gt x\) とも書く。

定理 14

\(\mathbb{N}\) は二項関係 \(\leq\) に関して全順序集合である。すなわち、任意の \(x,y\in\mathbb{N}\) に対して、

1. \(x\leq y,\) \(y\leq x\) ならば \(x=y.\)
2. \(x\leq y,\) \(y\leq z\) ならば \(x\leq z.\)
3. \(x\leq y\) または \(y\leq x.\)

が成り立つ。

証明

1 は定義 II と定理 11 による。2 は定義 II より明らか。3 は定理 13 と定義 II による。

定理 15

任意の \(x\in\mathbb{N}\) に対して、

4. \(1\leq x.\)
5. \(x\lt x'.\)
6. \(x\lt y\lt x'\) となる \(y\) は存在しない。

が成り立つ。

証明

4 は定理 6 と定理 7 より明らか。

5 は、定義 I より \([x]\subseteq[x']\) となることと、定理 3 から明らか。

6 の証明。もし そのような \(y\) が存在したとすると、定義 II より \([x]\subsetneq y\subsetneq[x']\) であることになるが、定義 I より \([x]\subsetneq y\subsetneq[x]\cup\{x'\}\) である。ゆえに \(y\) は、\([x]\subsetneq y\) より、ある集合 \(A\neq\varnothing\) を用いて \(y=[x]\cup A\) と表されなければならないが、\(y\subsetneq[x]\cup\{x'\}\) より \([x]\cup A\subsetneq[x]\cup\{x'\}\) であるので、\(A=\varnothing\) とならざるをえず、矛盾する。

定理 16

\([x]=\{y\mid 1\leq y\leq x\}.\)

証明

\(y\in[x]\) のとき、定理 7 より \([y]\subseteq[x]\) で、定義 II より \(y\leq x\) となる。ゆえに、定理 15 の 4 より \(1\leq y\leq x.\)

\(1\leq y\leq x\) のとき、定義 II より \([y]\subseteq[x].\) ゆえに、定理 5 より \(y\in[y]\subseteq[x].\)

定義 III

\([x]\) または \(\mathbb{N}\) から集合 \(X\) への全単射 \(f\) があるとき、\(X=\{f(1),f(2),\ldots,f(n),\ldots\}\) と表すことができるが、これを \(X=\{f_1,f_2,\ldots,f_n,\ldots\}\) とも書く。この \(f_n\) を、数え方 \(f\) における \(X\) の第 \(n\) 要素という。（ここで、\(2\) は \((1')'\) の略記である。）

定義 III の系

自然数は序数である。

定理 17

\([x]\) を定義域とする任意の全単射 \(f\) と \([y]\) を定義域とする任意の全単射 \(g\) に対して、\(\{f_1,f_2,\ldots,f_x\}=\{g_1,g_2,\ldots,g_y\}\) ならば \(x=y.\) （注意。ここでは、定義 III の記法を用いている。）

証明

\(y\) に関する帰納法による。

\(\{f_1,\ldots,f_x\}=\{g_1\}\) のとき、\(g_1\) は \(f_1,\ldots,f_x\) のどれか一つに等しく、他は存在しないことになる。すなわち、\(1\leq i\leq x\) のある \(i\) に対して \(\{f_i\}=\{g_1\}.\) しかし、定理 16 より \([x]\) は常に \(1\) を含むから、定義 III より \(\{f_1,\ldots,f_x\}\) は必ず \(\{f_1\}\) を含まないといけない。つまり、\(f_1\in\{f_i\}\) であるので、\(f_i=f_1.\) これと \(f\) が単射であることより \(i=1\) で、最初から \(x=1\) だったということになる。

\(\{f_1,\ldots,f_x\}=\{g_1,\ldots,g_k\}\) ならば \(x=k,\) が成り立つと仮定して、\(\{f_1,\ldots,f_x\}=\{g_1,\ldots,g_{k'}\}\) の場合を考える。\(x=1\) とすると前述のように \(k'=1\) が導かれるが、公理 iii より \(k'\neq 1\) であるので、\(x\neq 1.\) ゆえに、定理 2 より \(h'=x\) となる自然数 \(h\) が存在する。すなわち、\(\{f_1,\ldots,f_h,f_{h'}\}=\{g_1,\ldots,g_k,g_{k'}\}.\) ここで、\(f_{h'}=g_{k'}\) である場合と、そうでない場合が考えられる。

\(f_{h'}=g_{k'}\) ならば、\(\{f_1,\ldots,f_h\}=\{g_1,\ldots,g_k\}\) である。なぜなら、要素の相等しさによって二つの集合の要素間に一対一の対応が成立しているのだから、そのペアの一つを取り除いても、残りのペアで要素の相等しさは成立しているからである。ゆえに帰納法の仮定より（\(x\) は任意の自然数であるので \(x=h\) としてよい）、\(h=k.\) ゆえに \(x=h'=k'.\)

\(f_{h'}\neq g_{k'}\) ならば、\(1\leq i\leq h\) かつ \(f_i=g_{k'}\) となる自然数 \(i\) が存在しなければならない。ここで関数 \(\varphi\)を、 \[ \begin{cases} \varphi(i)=f(h') \\ \varphi(h')=f(i) \\ \varphi(x)=f(x) & (1\leq x\leq h,\; x\neq i) \end{cases} \] と定義すると、\(f\) が全単射であるので \(\varphi\) も全単射である。また、\(\{\varphi_1,\ldots,\varphi_{h'}\}=\{f_1,\ldots,f_{h'}\}\) であるので \(\{\varphi_1,\ldots,\varphi_{h'}\}=\{g_1,\ldots,g_{k'}\}\) であり、かつ \(\varphi_{h'}=g_{k'}\) が成り立っている。すなわち、先ほど考えた場合に帰着させることができる。

定義 IV

単射になっているある関数 \(f\) を用いて、ある自然数 \(n\) に対して \(X=\{f_1,f_2,\ldots,f_n\}\) と表すことのできる集合を有限集合といい、\(n\) を有限集合 \(X\) の要素の数という。定理 17 より要素の数はただ一つに定まる。

定義 IV の系

基数の \(n\) と序数の第 \(n\) は同じものである。すなわち、 \[|\{x_1,x_2,\ldots,x_n\}|=n.\]