濃度、可算集合

サイトのTOP→理系インデックス
集合論のTOP→集合論インデックス





D6

Ωを集合全体とする。

X、Y を集合とする。

X から Y への全単射が存在するという関係を 〜 とする。

このとき、関係 〜 はΩの同値関係である。

証明

明らかに、恒等写像 I:X→X は全単射である。

よって、X〜X である。

−−−−−−−−−−−−−−−−−−−−

X〜Y と仮定する。

いま、全単射 f:X→Y が存在する。

よって、逆写像 f−1:Y→X が存在する。

逆写像 f−1 は Y から X への全単射であるから、Y〜X である。

−−−−−−−−−−−−−−−−−−−−

X〜Y かつ Y〜Z と仮定する。

いま、全単射 f:X→Y、全単射 g:Y→Z が存在する。

また、g*f は X から Z への全単射である。

よって、X〜Z である。

定義 ( 濃度 )

2つの集合の間に全単射が存在するという関係は同値関係である。(※D6)

よって、この関係によって 『 集合全体 』 を同値類によって分類できる。

このような同値関係について、2つの集合 X、Y が同じ同値類に属するとき、cardX=cardY と表す。

cardX を 『 X の濃度 』 という。

つまり、次の(1)、(2)は同じ意味である。

(1) cardX=cardY が成り立つ。

(2) 集合 X、Y の間に全単射が存在する。

参考

上の定義では 『 集合全体 』 を考えた。

しかし、『 集合全体 』 を集合として考えるとパラドクスが生じてしまう。

つまり、『 集合全体 』 を集合として考えることはできない。

よって、『 同値類 』 という概念を、今回のような場合に用いることは厳密には正しくない。

しかし、通常の数学で支障が生じることはないので、素朴集合論では用いる。

詳しいことは公理的集合論などで議論される。

定義 ( 無限可算集合 )

自然数全体 と同じ濃度をもつ集合を 『 無限可算集合 』 という。

つまり、ある集合が無限可算であるならば、その集合と の間に全単射が存在する。

無限可算集合の濃度を次式の右辺のような記号で表す慣習がある。



この記号を 『 アレフゼロ 』 という。

アレフゼロ は card で代用できるので、このサイトではあまり使用しない。

D7

次が成り立つ。

補足

ただし、2 は{2,4,6,・・・}を意味する。

また、 は{ x∈|x>0 } を意味する。

(1)の証明

次のように定める。



いま、写像 f は全単射であるから、card(2)=card である。

(2)の証明

次のように定める。



いま、f は全単射であるから、card=card である。

(3)の証明

次のように定める。



いま、f は全単射であるから、card=card である。

(4)の証明

次のように定める。



いま、f は全単射であるから、card(×)=card である。

定義 ( 濃度の大小 )

X、Y を集合とする。

単射 f:X→Y が存在するとき、cardX≦cardY と表す。

cardX≦cardY かつ cardX≠cardY であるとき、「 Y は X より濃度が大きい 」 という。

このとき、cardX<cardY と表す。

D8

X を集合とする。

を X の巾集合とする。

このとき、次が成り立つ。

証明

次のように定める。



いま、f は単射であるから、cardX≦card2 である。

cardX=card2 と仮定する。(背理法)

いま、全単射ψ:X→2 が存在する。

ここで、次のような集合 A を考える。



いま、φ∈2 である。(※A4)

ψは全単射であるから、ある x∈X が存在して、ψ(x)=φとなるようにできる。

むろん、この x はψ(x)に属さない。

よって、x∈A である。

よって、A は空ではない。

−−−−−−−−−−−−−−−−−−−−

A∈2 であるから、ある a∈X が存在して、ψ(a)=A となるようにできる。

いま、次のいずれかが成り立つ。

(*1) a が A に属する。

(*2) a が A に属さない。

もし、(*1)ならば、



これは矛盾である。

もし、(*2)ならば、



これは A の定義に当てはまるので、a∈A である。これは矛盾である。

よって、cardX≠card2 である。

よって、cardX<card2 である。

D9

任意の無限集合は無限可算集合を含む

証明

A を無限集合とする。

A は空ではないので、A から1つの元 a を取り出せる。

A は無限集合なので、A から a を取り除いた集合 A−{a}は空ではない。

よって、A−{a}から1つの元 a を取り出せる。

A−{a、a}は空ではないから、さらに a を取り出せる。

A は無限集合であるから、この操作を順次繰り返すことができる。

こうして、A とは異なる集合 A’={a、a、a,・・・}が得られる。

その取り方から、明らかに A’は無限可算集合であり、A に含まれる。

補足

上の証明はやや直観的である。

それゆえ、気付きにくいが、実はこの証明では選択公理が使用されている。

そこで、厳密な証明を以下に載せる。

厳密な証明

X を無限集合とする。

を、X の(空でない)部分集合全体とする。

( つまり、=2−{φ}である )

ψを、任意の A∈ に対して A を対応させた写像とする。

見方を変えると、ψは 『 を添字集合とする集合族 (A)A∈ 』 である。

しかも、任意の A は空ではない。

そこで、各 A∈ から1つの元 x∈A を取り出して固定する。(※選択公理)

このような集合族を (xA∈ と表す。

ここで、次のようにおく。



いま、{ x,x,x,・・・}は X の無限可算な部分集合である。

D10

無限集合の中では、無限可算集合の濃度が最小である。

証明

明らかである。(※D9)

D11

X、Y を集合とする。

このとき、次は同値である。

(1) cardX≦cardY が成り立つ。(ただし、X≠φ)

(2) 全射 g:Y→X が存在する。

証明

明らかである。(※C5)

定義 ( 高々可算 )

集合 A が無限可算集合または有限集合であるとき、A を 『 高々可算集合 』 という。

つまり、A が高々可算ならば、cardA≦card である。

参考

無限可算を可算と呼ぶ書物もある。

高々可算を可算と呼ぶ書物もある。

単に可算と呼ぶと混乱する可能性があるので、このサイトではなるべく可算という呼び方は避ける。

D12

次が成り立つ。



( ただし、(2)においてJ≠φとし、任意のλ∈J に対してAλ≠φとする )

(1)の証明

仮定より、単射 f:A→ と 単射 g:B→ が存在する。

そこで、次のように定める。



明らかに、ψは単射である。

よって、card(A×B)≦card(×)である。

よって、card(A×B)≦card である。(※D7)

(2)の証明

(1)より、card(J×)≦card である。(★)

いま、任意のλ∈J に対し、全射 fλ→Aλ が存在する。(※D11)

そこで、次のように定める。



いま、ψは全射である。

よって、D11より、



よって、(★)より、

D13

次が成り立つ。

証明

明らかである。(※D12、D10)

D14

X を無限集合とする。

Y を高々可算集合とする。

このとき、cardX=card(X∪Y)である。

証明

いま、ある無限可算集合 A が存在して、A⊂X となるようにできる。(※D9)

また、card(A∪Y)=card である。(※D13)

つまり、全単射 f:A→A∪Y が存在する。

次のように定める。



いま、g は全単射である。

よって、cardX=card(X∪Y)である。

D15

card=card である。

証明

次のように定める。



明らかに、f は全射である。

よって、card≦card(×)である。(※D11)

また、 は無限可算である。(※D7)

よって、× は無限可算である。(※D13)

つまり、card(×)=card である。

よって、card≦card である。

よって、card=card である。(※D10)

D16

(1) 区間 (a、b) と は濃度が等しい。

(2) 区間 (0、1] と (0、1) は濃度が等しい。

(3) 区間 (0、1] と は濃度が等しい。

(4) 区間 [a、b] と [c、d] は濃度が等しい。

(1)の証明

次のように定める。



いま、f は全単射である。

つまり、(0、1) と は濃度が等しい。

(2)の証明

次のように定める。



いま、f は全単射である。

つまり、(0、1] と (0、1) は濃度が等しい。

(3)の証明

(1)、(2)より、明らかである。

(4)の証明

次のように定める。



いま、f は全単射である。

つまり、[a、b] と [c、d] は濃度が等しい。