対象読者
- 数学の「論理と集合」が分かる方
結論
本記事では、
- 自然数と偶数の数は同じ
- 自然数と奇数の数は同じ
であることをそれぞれ示す。
偶数と奇数と自然数が同じ要素数というのは、「部分と全体と同じサイズ」という直感に反する異常事態である。 例えば、人口を男性と女性に分けたとき、男性と女性は全人口よりも少なくなるのが当たり前の感覚だ。
自然数の分類では、男性・女性・全人口の数が等しくなるような怪奇現象が起きる。 この違いは、人口は有限であるのに対して、自然数は無限であるという点にある。
しかし、無限集合の要素数を比較するなんてどうすればいいのか。 無限の要素を持つ集合はいつまでも数え終わらない。
これを理解するためにはまず、
- 関数のより厳密なイメージ
- 「要素数が同じである」の定義
を押さえる必要がある。
関数とは２つの値の対応関係
高校数学までは関数を把握するためにグラフを多用してきた。 だから、関数とグラフの絵と同じものだと誤解しがちだ。
関数の定義は以下だ。 $$ \forall x \in X, \exists! y \in Y, f(x) = y $$
「\(\forall\)」は「全ての(All)」、 「\(\exists\)」は「存在する(Exist)」を意味する記号である。 「\(\exists!\)」は「ただ1つ存在する(Exist)」という意味だ。
日本語で言うと、関数とは「どの入力に対してもただ1つの出力が対応する」ということである。 入力1つに対して複数の出力を対応づけることは許されない。
例えば、関数 \( f(x) = x^2 \) は以下のような対応関係を表している。
- 入力が1の時、出力は1 (\(f(1) = 1\))
- 入力が2の時、出力は4 (\(f(2) = 4\))
- 入力が3の時、出力は9 (\(f(3) = 9\))
- …
関数は「グラフの絵」というより「入力の集合と出力の集合の対応関係」とイメージできる。 グラフの絵は「入力と出力の座標の集合」である。 入力の集合を定義域、出力の集合を値域と呼ぶ。
関数 \(f\) は以下のように定義域 \(X\)、値域 \(Y\) を明示して書くことができる。
$$f: X \rightarrow Y, f(x) = y$$
定義域と値域の区別は関数をイメージする上で重要だ。 定義域と値域は別物である例を次に示す。
定義域と値域が異なる例
関数 \(f(x) = x^2\) の定義域を実数全体とする。
このとき、負の入力は、2乗によって正として出力される。 つまり、定義域は実数全体なのに対して、値域は非負の実数となる。
「全単射」とは２つの集合の要素数が同じであること
さて、どうすれば無限集合の要素数の大小を比較できるのだろうか。
定義域と値域のそれぞれの要素が1対1対応しているとする。 このとき、定義域と値域は同じ要素数であると直感的に分かる。 この対応が1つでも見つけられれば、無限回の比較を回避しつつ２つの集合の要素数が同じだと示せる。
関数の1対1対応は「全単射」と呼ばれている。 全単射とは「単射」かつ「全射」のことである。
以下で単射と全射について書く。
「単射」とは出力が重ならないこと
単射を数式で表すと以下になる。 $$ \forall x_1, x_2 \in X, x_1 \neq x_2 \Rightarrow f(x_1)\neq f(x_2) $$
日本語で言うと 「定義域の適当な2要素\(x_1\)と\(x_2\)が異なるならば、 それに対応する出力\(f(x_1)\)と\(f(x_2)\)も異なる」 という感じである。
「ならば(\(\Rightarrow\))」は対偶によって、 $$ (P \Rightarrow Q) \Leftrightarrow (\lnot Q \Rightarrow \lnot P) $$ と書き換えられる。 \(P\)と\(Q\)は命題、「\(\lnot\)」は否定とする。
よって、単射の定義を対偶で書き換えると以下となる。
$$ \forall x_1, x_2 \in X, f(x_1 ) = f(x_2) \Rightarrow x_1 = x_2 $$
「2つの出力が等しいならば、それに対応する入力も等しい」という意味だ。
例えば、\(f(x) = x^2\)は単射ではない。 なぜなら、\(f(1) = f(-1)=1\)なのに入力が\(x_1 = 1\)と\(x_2 = -1\)で異なるからだ。
まあ要は、単射とはそれぞれ入力が重ならずに出力されるということだ。 そのためには入力の数以上の出力が必要である。 なので、単射 \(X \leq Y\) とも表される。 おぉ、大小関係の比較の不等号みたいだ。
いや逆に、値域よりも定義域の方が要素数が多いと考えてみよう。 このとき、出力を重複させて圧縮しないと値域を定義域よりも小さく収める事ができないとイメージできるだろうか。 だが、これは単射の定義に反する。
またまた逆に、\(X \leq Y\) の通り定義域より大きな値域を考えてみよう。 このとき、定義域と同じ数だけの出力を割り当ててもまだ値域の要素が余る(図3)。 単射はデブな値域というイメージになる。
「全射」とは余分な値域の要素がないこと
OKOK。単射は分かった。次に全射について述べる。 全射を数式で表すと以下。 $$ \forall y \in Y, \exists x \in X, f(x) = y $$
日本語で言うと「値域のあらゆる要素には対応する入力が存在する」という感じだ。
- 入力と対応しない出力はない(全射)
- 入力１つに対して唯一の出力がある(関数の定義)
- 単射とは違って、出力が重複し得る
よって、全射のイメージは図4のような感じで、定義域の要素数は値域と同じまたは大きくなる。
自然数と偶数と奇数が同じ要素数である証明
以上より、単射かつ全射の「全単射」は1対1対応に他ならないと分かる。 余分な値域がなく、それぞれの入力が重複せずに出力されるからだ。
全単射な関数を見つけられれば、数え上げられない無限集合同士でも要素数が同じだと示せる。
これで証明を始める準備が整ったので、自然数と偶数が同じ要素数である事を示す。
自然数\(\mathbb{N}\)から偶数\(E\)への全単射な関数があるか考える。
$$ f: \mathbb{N} \rightarrow E, f(n) = 2n $$ とおく。
\(f\)が単射であることを示す。 ２つの入力を\(n_1, n_2 \in \mathbb{N}\)とする。
$$ \begin{aligned} & f(n_1) = f(n_2) \\ & \Rightarrow 2n_1 = 2n_2 \\ & \Rightarrow n_1 = n_2 \end{aligned} $$
よって、単射である。
次は全射であることを示す。 適当な出力を\( e \in E \)とおく。 \(e\)は偶数であるため２で割り切れる。 つまり、\(e / 2 \in \mathbb{N}\)であり、これが入力に対応する。 よって、全射である。
以上より、自然数と偶数は1対1に対応(全単射)していることが分かる。
同様に自然数と奇数も同じ要素数であることが証明できる。 以下のような関数を定義して、こいつが全単射であることを示すだけだ。
$$ f: \mathbb{N} \rightarrow O, f(n) = 2n + 1 $$
結び:無限集合では部分と全体が同じ要素数になり得る
人口ような有限集合ではありえない事が自然数の分類では起きることが分かった。 そもそも無限集合を有限集合と同じ感覚で考える事自体がおかしかったのだ。 だって、無限の中から無限を取り出すのは普通にできそうなである。
それにしても、無限な要素数を1対1対応のような切り口で飼い慣らす数学ってすんごいいいい。