集合と位相

　集合 X と集合 Y は、集合の圏の対象として同型であるとき、言い換えると X から Y への一対一上への写像（全単射）が存在するとき等濃であるといい、仮に X @ Y と書くことにします。全単射の合成、逆写像はやはり全単射ですから、関係 @ は同値関係です。

　次に、集合 X から Y への一対一写像が存在するとき X £ Y と書くことにします。
　恒等写像は一対一であること、一対一写像の合成は一対一であることから、関係 £ が集合全体からなる類の上の擬順序関係、すなわち (2-1a) と (2-1b) を満たすことは明らかですが、これが更に

(4-1)  ( X £ Y  Ù  Y £ X )  Þ  X @ Y

を満たすことを証明しましょう（Bernsteinの定理）。
　X £ Y かつ Y £ X と仮定すると、一対一写像 f : X ® Y と g : Y ® X が存在します。ここで

(4-2a)  A0 = X  \  g[Y ]

(4-2b)  B0 = Y  \  f [X ]

(4-2c)  An = (g ° f )n[A0]       ( n = 1, 2, ¼ )

(4-2d)  Bn = ( f ° g)n[B0]       ( n = 1, 2, ¼ )

(4-2e)  A = È{ An | nÎN }

(4-2f)  B = È{ Bn | nÎN }

(4-2g)  A' = X  \  A  \  g[B]

(4-2h)  B' = Y  \  B  \  f [A]

と置きます。ただし、ある集合から自分自身への写像 j を n 個合成した写像を jⁿ と書きました。このとき任意の自然数 n , m に対して

(4-3)  AnÇg[Bm] = (g ° f )n[A0]Ç(g ° f )m[g[B0]]

ですから、n £ m なら、(g _° f )ⁿ が一対一であることと (4-2a) から、

(4-4a)  AnÇg[Bm] = (g ° f )n[A0Çg[( f ° g)m-n[B0]]] Ì (g ° f )n[A0Çg[Y ]] = (g ° f )n[Æ] = Æ

　また、n > m なら、(g _° f )^m _° g が一対一であることと (4-2b) から、

(4-4b)  AnÇg[Bm] = ((g ° f )m ° g)[ f [(g ° f )n-m-1[A0]]ÇB0] Ì ((g ° f )m ° g)[ f [X ]ÇB0]] = ((g ° f )m ° g)[Æ] = Æ

　ゆえに、任意の自然数 n , m に対して

(4-5)  AnÇg[Bm] = Æ

が成り立つので、(4-2e),(4-2f) により

(4-6a)  AÇg[B] = Æ

　同様に、対称的に

(4-6b)  BÇ f [A] = Æ

が成り立ちます。ゆえに X は A と A' と g[B] の互いに交わらない合併に分割され、Y は B と B' と f [A] の互いに交わらない合併に分割されることがわかりました。また、

(4-7)  f [A' ] = f [X  \  A  \  g[B]] = f [X ]  \  f [A]  \  ( f ° g)[B] = Y  \  B0  \  f [A]  \  ( f ° g)[B] = Y  \  (B0È( f ° g)[B] )  \  f [A] = Y  \  B  \  f [A] = B'

ですから、X から Y への写像 h を、AÈA' 上 f に、g[B] 上 g^-1 に一致するように定めれば、h は X から Y への全単射となり、これは X @ Y を意味するので、(4-1) は証明されました。

　さて、X £ Y かつ Ø X @ Y のとき X < Y と書くことにします。このとき、任意の集合 X に対して

(4-8)   X < P (X )

が成り立ちます（Cantorの定理）。
　実際、まず i : X ® P (X ) を i(x) = {x} で定義すれば、明らかに i は一対一ですから X £ P (X ) です。従って、あとはどんな写像 f : X ® P (X ) も全射になり得ないことを示せば十分です。実際

(4-9)  A = { xÎX | xÏf(x) }ÎP (X )

と置くと、これは f の像に属しません。なぜなら、もしある aÎX に対して A = f(a) と書けたとすると、aÎf(a)  Û  aÎA  Û  aÏf(a) となって矛盾するからです。

　さて、順序数 a は、どの bÎa も a と等濃でないとき基数といいます。基数全体の集合を Card と書くことにします。(2-11) により２つの順序数は常に比較可能ですから、基数 a と b は等濃なら a = b です。
　また、a Ì b なら埋め込み写像は一対一ですから a £ b ですが、逆に a £ b なら a Ì b です。なぜなら、そうでないとすると (2-14) と (2-11) により bÎa となりますが、a の推移性により b Ì a 、従って b £ a となりますが、a £ b と (4-1) により a と b は等濃、よって a = b となり矛盾します。
　以上を纏めると、任意の順序数 a , b について

(4-10a)  a @ b  Û  a = b

(4-10b)  a < b  Û  aÎb

となります。したがって、(2-11) により、２個の基数 a , b は比較可能：

(4-11)  a < b  Ú  a = b  Ú  a > b

であることがわかります。
　また、Card は整列類です。なぜなら、任意の空でない A Ì Card を取ると、A は整列類 Ord の空でない部分類ですから順序数としての最小元 a を持ちますが、(4-10) により a は基数としての最小元でもあるからです。

　ここで後の目的のために、Zornの補題について説明しておきましょう。
　順序集合 O の元 a は、x > a となる xÎO が存在しない、言い換えると

(4-12)  "xÎO ( x ³ a  Þ  x = a )

が成り立つとき極大元といいます（極小元も同様に定義されます）。

　さて、順序集合 O の空でない任意の全順序部分集合が上界を持てば、O は極大元を持ちます（Zornの補題）。より具体的には、任意の aÎO に対し、a を元に持つ O の任意の全順序部分集合が上界を持てば、a より大きい極大元が存在します。これを帰謬法で証明しましょう。
　任意の y ³ a が極大元でない、すなわち y より真に大きい xÎO が存在すると仮定すると、a を元に持つ O の任意の全順序部分集合 A に対し、

(4-13)  $xÎO : "yÎA : y < x

が成り立ちます。なぜなら A の上界 z が存在して z ³ a であることから、それは極大元でなく、従ってそれより真に大きい x が存在し、任意の yÎA に対して y £ z < x となるからです。そこで、整列類 Ord において、ある順序数 a に対する切片 Ord_a = a を定義域とする写像 f に対し、第１節のε量化記号を使って

(4-14)  T( f ) :º εx [ xÎO  Ù  ( D( f ) = Æ  Þ  x = a )  Ù  "yÎR( f ) : y < x ]

と置いたとき、(2-20) によって順序類 Ord 上に超限帰納的に構成される写像を F と書くことにします。このとき、ε量化記号の定義により、

(4-15a)  F(0) = a

(4-15b)  ( $xÎO : "bÎa : F(b) < x )  Þ  ( F(a)ÎO  Ù  "bÎa : F(b) < F(a) )

が成り立ちます。このとき、任意の順序数 a > 0 に対して

(4-16)  F(a)ÎO  Ù  "bÎa : F(b) < F(a)

が成り立つことを a に関する超限帰納法で証明しましょう。そのために、任意の gÎa に対して (4-16) の a を g に置き換えたもの：

(4-17)  F(g)ÎO  Ù  "bÎg : F(b) < F(g)

が成り立つと仮定します。さて、任意に b, gÎa を取ると、(2-11) のいずれかが成り立ちますが、bÎg なら (4-17) により F(b) < F(g) が成り立ち、また gÎb なら F(g) < F(b) となりますから、F[a] は a を元に持つ全順序集合です。ゆえに (4-13) を A = F[a] に適用できて、

(4-18)  $xÎO : "bÎa : F(b) < x

が成り立ちます。ゆえに (4-15b) により (4-16) が成り立ちます。よって超限帰納法が完成し、任意の順序数 a に対して (4-16) が成り立ちます。
　ところが (4-16) は、F が全順序類 Ord から O への (2-5) を満たす写像であることを意味していますから、F は一対一写像です。また分出公理により F[Ord] Ì O は集合ですから、置換公理により、その写像 F^-1 による像 Ord も集合になり、矛盾します。
　以上でZornの補題は証明されました。

　さて、このZornの補題を使って、任意の集合 X 上に整列順序が存在すること（整列可能定理）を証明しましょう。
　X が空なら明らかですから X ¹ Æ と仮定します。ここで X の整列部分集合 S の全体を S とし、S, TÎS は、S Ì T であって、S の順序が T の順序の S への制限になっていて、かつ T \ S の元は S の元よりも必ず大きいとき S £ T と定義することにすれば、S は順序集合になります。
　このとき、S の任意の空でない全順序部分集合 W に対し、ÈW は、明かに順序が整合的に定義されますが、さらにこれは整列集合です。なぜなら、任意の空でない集合 A Ì ÈW に対し、AÇS ¹ Æ となる SÎW が存在しますが、a を整列集合 S における AÇS の最小元とすると、T É S のとき、AÇT の元で AÇS に属さないものは、AÇS のどの元よりも大きいので、したがって A の最小元にはなりえません。すなわち a が A の最小元ということになり、ÈW は整列集合であることがわかりました。
　ゆえに S は任意の空でない全順序部分集合が上界を持つので、Zornの補題により極大元 S を持ちます。
　もし S ¹ X なら、元 aÎX \ S を取り、S' = SÈ{a} とおき、a は S の全ての元より大きいとして S の順序を S' の順序に拡張すれば、明かに S' は整列集合で S < S' となりますから、S の極大性に反します。ゆえに S = X であることがわかり、X 上に整列順序が存在することがわかりました。

　整列可能定理と第２節で証明した順序型の存在証明を組み合わせると、任意の集合 X は、ある順序数 α と等濃であることがわかります。
　この結果、任意の集合 X に対し、X と等濃な順序数全体からなる類 A は空でなく、Ord は整列類ですから、A には最小元 a が存在します。これは定義から明らかに基数です。よってこの基数 a を X の濃度とよんで card X と書くことにします。
　X @ card X および card X @ card Y  Û  card X = card Y が成り立ちますから、

(4-19)  X @ Y  Û  card X = card Y

が成り立つ、すなわち等濃とは文字どおり濃度が等しいことである、ということがわかります。

　また、明らかに X < Y  Û  card X < card Y ですから、(4-10b) により

(4-20)  X < Y  Û  card X Î card Y

が成り立つこともわかります。また、(4-20) と任意の２つの順序数が比較可能であることから、任意の２つの集合 X , Y に対して

(4-21)  X < Y  Ú  X @ Y  Ú  X > Y

が成り立つことがわかります。

　さて、w £ X であるような集合 X を無限集合といい、そうでない、すなわち X < w であるような集合を有限集合といいます。明らかに有限集合の部分集合は有限集合です（したがって、BG集合論では「数学の基礎」第11節で定義した部分有限集合と有限集合を区別する必要はなくなります）。
　また、基数が集合として無限集合（有限集合）のとき、無限基数（有限基数）といいます。

　X を無限集合とすれば、w から X への一対一写像 i が存在します。そこで f : X ® X を、xÎR(i) に対しては f(i(n)) = i(n + 1) 、xÏR(i) に対しては f(x) = x で定義すれば、f は X からその真部分集合 X \ {i(0)} への一対一写像になります。
　逆に X から X の真部分集合への一対一写像 f が存在すると仮定します。このとき、帰納的に

(4-22a)  X0 = X

(4-22b)  Xn+1 = f [Xn ]

と定義すれば、X_n+1 は X_n の真部分集合です。
　実際、n = 0 のときは f に関する仮定から明らかです。
　また n まで正しいとすると、仮定により X_n+1 は X_n の真部分集合ですから、f が一対一であることにより f [X_n+1] は f [X_n] の真部分集合です。よって (4-22b) により X_n+2 は X_n+1 の真部分集合です。よって帰納法が成立しました。
　そこで、w から X への写像 i を i(n) = εx(xÎX_n \ X_n+1) で定義すれば、i は一対一、従って w £ X となるので X は無限集合です。
　すなわち X が無限集合であるための必要十分条件は、X から X の真部分集合への一対一写像が存在することです。
　従って特に、有限集合 X から自分自身への写像 f は、一対一なら上への写像です。逆に f が上への写像なら、g(x) :º εy[ f( y) = x] と置くと、これは f(g(x)) = x を満たし、かつ g は X からそれ自身への一対一写像ですから上への写像、すなわち全単射ですから、f も全単射です。すなわち有限集合からそれ自身への写像について、一対一であること、上への写像であること、全単射であることはすべて同値です。

　次に、どの nÎw も w と等濃でないことを証明しましょう。
　実際、w がある nÎw と等濃だったと仮定すると、全単射 f : n ® w が存在します。
　ところで一般に、任意の写像 g : n ® w に対して R(g) には（順序数としての）最大元が存在することが n に関する帰納法で証明できます。実際、n = Æ のときは明らかで、n で正しければ { g(k) | kÎn + 1 } = { g(k) | kÎn }È{ g(n) } は帰納法の仮定と w が全順序集合であることから明らかに最大元を持つからです。
　ゆえに全単射 f : n ® w の像 w は最大限を持つことになりますが、どの mÎw に対しても m + 1 Îw となるため w は最大限を持ちませんから、これは矛盾です。以上でどの nÎw も w と等濃でないことがわかりました。
　このことから特に

(4-23)  card w = w

　すなわち w は基数であることがわかります。

　この結果を用いると、X が有限集合であるための必要十分条件は、card X Î ω が成り立つことである、ということが証明できます。
　実際、X が有限集合なら、X £ w なら、card X Ì card w = w ですが、もし card X = w なら X @ w となって X が有限集合という仮定に反するので card X Î w です。
　逆に card X Î w なら、まず X £ w ですが、上で証明したように X @ card X は w と等濃でないので、X < w となって X は有限集合であることがわかります。

　以上の結果により、n, mÎw が等濃なら n = m であることがわかります。
　実際、n @ m なのに n ¹ m となった仮定すると、(2-11),(2-14) により m @ n Ì m 又は n @ m Ì n となって、n 又は m からその真部分集合への一対一写像が存在することになるので無限集合となり、n , m が共に有限集合であることに反します。

　以上により、w の元はすべて基数であり、これらが有限基数のすべてであることがわかりました。

　なお、無限集合の中でも、特に最小の無限基数である w と等濃な集合を可算集合といい、可算又は有限な集合は高々可算であるといいます。明らかに、可算集合の無限部分集合は可算集合であり、高々可算な集合の部分集合は高々可算です。