N^2=Nを満たす自然数といえばN=0,1が挙げられる。（ただし、Nを0を含むように構成した時）では、これ以外にN^2=Nを満たす自然数は存在するかと言われると、存在しないということが答えになる。今回の話はそれでおしまい。

なわけがない。もちろん自然数の範囲ではN^2=Nを満たすNは上にあげたようなものしかない。しかし、これを集合に含まれる元の数、要するに濃度、くらいに広げてみるとどうだろう。例えば、|N|=|Z|であることは良く知られていることである。明らかにN⊂Zであり、一致していないにも関わらず、である。つまり、集合の濃度くらいに話を広げてしまえば、|N|^2=|N|となる集合Nを見つけられるのではないかということである。

そのような集合は実際に存在する。というか気づいている人の方が大半であろう。わざわざnではなくNを使っているということは、そう、自然数の集合である。つまり、F:N×N→Nとなるような全単射写像Fが少なくとも一つ存在することがわかる。

というか、この日誌で集合の個数の数え上げについて述べていなかった気がするので、それも今述べてしまおう。

集合の個数が等しいとは

|A|=|B|とは、ある全単射写像F:A→Bが存在することを指す。

また、|A|≦|B|であるとは、ある単射写像F:A→Bが存在することを指す。

集合の個数、というのは群でも環でもモノイドでもなんでもないただの集合でも定まる最も普遍的な不変量であると言える。つまり、やはり数学の基本は数にあるということだ。数によって集合の構造がとても漠然としてはいるが少しだけ定まるということだ。

集合の個数、これからは濃度と呼ぶ、について述べたところで、この定義から導かれる性質をいくつか紹介、証明しよう。

集合の濃度の定理

1. A⊂B→|A|≦|B|

2. A=B→|A|=|B|

3. |N|=|Z|

4. |A|≦|B|∧|B|≦|A|→|A|=|B|（ベルンシュタインの定理）

[証明]

1と2はどちらも、AからBへの恒等写像を例として出せば、定義からいうことができる。

3は少々難しい。Fを次のように定める。もし偶数であれば、2で割った数をそのまま出力し、もし奇数であれば、1を足して2で割った数をマイナスにして出力する。

例えば、F(0)=0,F(1)=-1,F(2)=1,F(3)=2。これは何と全単射になっている。

全射であることを示す。

∀b∈Z,∃a∈N,b=F(a)を示せば良い。

b≧0の時、a=2b∈Nとすれば、F(a)=b

b<0の時、a=-2b-1∈Nとすれば、F(a)=b

単射であることを示す。

F(a)=F(b)→a=bを示す。

k=F(a)=F(b)とする。この時、k≧0であれば、a=2kである。bも同様。よって、a=2k=b。

k<0の時、a=-2k-1となる。bも同様。よって、a=bである。

これらより、全単射性が証明できたので、|N|=|Z|

4の証明はこの記事に書くにはあまりにもヘビーすぎるので、いずれの機会に証明する。この定理はベルンシュタインの定理と呼ばれていて、全単射写像を構成しないで単射写像を構成するだけで等濃度であることがわかる便利な定理である。この定理の妥当性はAとBが有限集合の時に確認することができる。（数学では有限の場合と無限の場合では大きなギャップがあるが。）

さて、問題は|N×N|=|N|であるかどうかである。この時、様々な方法で全単射写像を構成できる。

・素因数分解の一意性の利用

ベルンシュタインの定理を用いる。

n→(n,0)と写像する。これは自明に単射である。

ここからがトリックである。

自然数の組(i,j)→2^i 3^jというように写像すると、これは実は単射写像である。

実際に示してみると、

2^i 3^j=2^s 3^tであれば、素因数分解の一意性より、i=s, j=t。これで単射性が示せた。

両方向からの単射が存在するので、ベルンシュタインの定理より全単射写像が存在する。よって、題意が示せた。

・最初から全単射を作りにいく方法

下の表のように番号をつける。

5　15

4　10　16

3　6　11　17

2　3　7　12　18

1　1　4　8　13　19

0　0　2　5　9　14　20

　　0　1　2　3　4　5

このように斜めに順番をつけると全単射が作れる。