カントールの定理の反例を出そうとして逆に納得した話
前提
偶数の個数も、自然数の個数も、整数の個数も、有理数の個数も全部等しい
$ |{\rm Odd}|=|\N|=|\Z|=|\mathbb Q|
これは、集合の大きさを、「関数を使って 1 対 1 に対応付けられることと、その2つの集合の大きさは等しいことは同じ」としているため
$ ^{\exist f: S\rightarrow T,\forall t\in T, \exist! s\in S}[f(s)=t]\Leftrightarrow[|S|=|T|]
例えば整数と奇数は関数 $ f(z)=2z-1で 1 対 1 に対応付けられる
他には有理数は2次元格子座標に原点に近い順に番号を振っていく関数を作り、自然数と対応付けられる
じゃあ、逆に何でもかんでも無限は無限ってことになりそうやん？
$ |\N|=\infty?
カントールの定理による実例
$ |\N|<|\R| 自然数の集合よりも実数の集合のほうが真にデカい
集合$ Aの冪集合$ 2^Aの濃度$ 2^{|A|}は$ |A|<2^{|A|} 特に$ Aが無限集合においてもこれが成り立つことが大事
$ A=\{a_0,a_1,a_2\}なら$ 2^A=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{c,a\},\{a,b,c\}\}
要素は合計$ 2^3=8個ある
カントールの定理に反論するために 2 つの関数を用意する
1. 素数にナンバリングする関数
$ p:\N^+\rightarrow\mathbb P
$ p(i)=i番目の素数
例: $ p(1)=2,p(2)=3,p(3)=5,p(4)=7,p(5)=11
これで素数全体の集合$ \mathbb Pと正の整数全体の集合$ \N^+が 1 対 1 に対応付けられる
よって $ |\mathbb P|=|\N|
2. 素数の部分集合から自然数数を生み出す関数
$ \Pi:2^\mathbb P\rightarrow\N
$ \Pi(\{p_0,p_1,p_2,\cdots,p_n\})=p_0\times p_1\times p_2\times\cdots\times p_n
$ \Pi(\varnothing)=1
これで、素因数分解の一意性から、自然数と素数の部分集合には 1 対 1 の対応付けができる！
4は「素数の部分集合」に対応しますか？nishio.icon
2×2なので…
対応してないっすね。
$ \{2,2\}=\{2\}で消えちゃうSummer498.icon
お～。こういうの待ってた。抜け落ちてた
よって $ |2^{\mathbb P}|=\N
$ |\mathbb P|=|\N|だったので、$ |2^\N|=\N
よっしゃ！ 反例を示せたぞ！
オチ
集合$ Sの部分集合には$ S自身も含まれていることを忘れている
なので、$ \Pi(\mathbb P)について考える必要がある
$ \Pi(\mathbb P)=\inftyとしようか？$ \inftyは自然数に含まれていないのでダメ
他の自然数は全部予約済みだからダメ
どう上手く$ \mathbb Pを処理しようとしても、必ずどこかで問題が発生する
つまり$ 2^Aには$ A自身が属するがゆえに$ |2^A|は$ |A|よりもデカくなっている
疑問
$ \mathbb P-\{p\}を$ -pに対応付ければ良いのでは？
$ \Pi:2^\mathbb P\rightarrow\Z-\{0\}
$ \Pi(\{p_0,p_1,p_2,\cdots,p_n\})=p_0\times p_1\times p_2\times\cdots\times p_n
$ \Pi(\mathbb P-\{p_0,p_1,p_2,\cdots,p_n\})=-p_0\times p_1\times p_2\times\cdots\times p_n
$ \Pi(\varnothing)=1
$ \Pi(\mathbb P)=-1
こうすると素数のべき集合と整数の集合が一対一に対応付けられそう
なーんか妙だなtakker.icon
今度調べる