1.8 濃度
1.8.1 有限集合
これまでにも有限集合という言葉をことわりなく使ってきたが, ここで定義と基本的な 性質を与えておく.
あらためて集合[n]を定義しておこう.
定義 1.8.2. n∈N0 に対し, N0 の部分集合[n]を
[n] :={m∈N0 m < n} で定める.
また, [n]を順序集合と考えるときは, とくに断らなければ N0（の普通の順序）から入 る順序を入れる.
定義 1.8.3. 集合X が有限集合(finite set)である
⇔def
ある非負整数n∈N0が存在して, X は[n]と対等である.
注意 . 有限集合の定義の仕方にはいろいろな流儀がある. 適当な仮定のもとではいずれも
同値である. ここで述べた定義は最もわかりやすいものだと思うが, 一番標準的というわ けではない.
集合[n] についての性質をいくつか挙げる. 証明は数学的帰納法による（1.10.8節を 見よ）.
補題 1.8.4. A ⊂ [n]ならば, ある m∈ N0, m ≤n が存在し, Aと[m]は順序同型であ る: A∼= [m]. ただし, Aには[n]から入る順序を入れる.
系 1.8.5. n∈N0とする. 任意の∅ 6=A⊂[n]に対し, minAが存在する. すなわち, 任意のn∈N0 に対し, [n]は整列集合である.
証明. ∅ 6=A⊂[n]とする. あるm≤nと順序同型g: [m]→A が存在する. A 6=∅ゆえ m >0で0 = min[m]. 明らかにg(0) = minA.
系 1.8.6. 任意のn∈N0に対し, [n]からの全射は切断を持つ.
補題 1.8.4とほとんど同様に示せるが, 次の補題 1.8.7は元の個数を考える上で基本的
である.
補題 1.8.7. m, n∈N0とする. このとき次が成り立つ. 1. 単射f: [m]→[n]が存在する⇔m≤n.
2. 全射ではない単射f: [m]→[n]が存在する⇔m < n.
系 1.8.8. m, n∈Nとする. このとき
1. 全射f: [m]→[n]が存在する⇔m≥n.
2. 単射ではない全射f: [m]→[n]が存在する⇔m > n.
注意 . ⇒はm= 0またはn= 0のときも正しい. 問 46. m, n ∈N,m≥nとする. 全射[m]→[n]を作れ.
補題 1.8.4より次が分かる.
系 1.8.9. 有限集合の部分集合は有限集合である.
証明. X を有限集合, A⊂ X とする. 定義よりあるn∈N0 と全単射f: X →[n]が存在 する. f のAへの制限によりA∼=f(A)⊂[n]である. あるm∈N0 が存在しf(A)∼= [m]
であるからA∼= [m].
系 1.8.10. Xを有限集合, Y を集合とする. 全射X →Y が存在すれば, Y は有限集合で
ある.
証明. Y 6= ∅としてよい. [n] ∼=X とし, 全射 X →Y との合成f: [n] −→∼= X → Y を考 えるとf は全射である. よって 系 1.8.6よりf は切断s: Y →[n]を持つ. s(Y)⊂[n]だ からs(Y)は有限集合. f ◦s= idY ゆえsは単射. よってY ∼=s(Y)は有限集合.
補題 1.8.7より次が分かる.
系 1.8.11. X ∼=Y かつX ∼= [n]かつY ∼= [m]ならばm=n.
証明. 仮定のもと[m] ∼= [n]となる. とくに単射[m] → [n], [n] → [m] が存在するので m≤nかつn≤mゆえm=n.
定義 1.8.12. X を有限集合とする. X ∼= [n]であるとき, n∈N0 をX の元の個数あるい は濃度(cardinality) といい, ]X, |X|等と表す. 系 1.8.11をX = Y の場合に使えば, このnはX に対し一意に定まる.
系 1.8.13. X, Y を有限集合とする. このときX ∼=Y ⇔ |X|=|Y|. 問 47. これを示せ.
系 1.8.14. X, Y を|X|=|Y|である有限集合とし, f: X →Y を写像とする. 次は同値. 1. f は単射.
2. f は全射. 3. f は全単射.
とくにX が有限集合であるとき, 写像f: X →X に対しこれらは同値.
問 48. これを示せ. (ヒント: X =Y = [n]としてよい（なぜ?）. X =Y = [n]の場合 は補題 1.8.7 2, 系1.8.8 2から分かる.)
系 1.8.15. X を有限集合, A⊂X とする. このとき, A∼=X ⇔A =X.
とくに, 有限集合はその真部分集合と対等ではない. 証明. ⇐は明らか.
⇒を示す. A ∼= X とする. このとき|A| = |X|である. i: A → X を包含写像とする と, iは単射であるから, 系 1.8.14よりiは全射. 包含写像が全射なのでA =X.
系 1.8.16. X を集合, Y を有限集合とする.
1. 次は同値.
(i) X は有限集合で|X| ≤ |Y|. (ii) X からY への単射が存在する.
2. 次は同値.
(i) X は有限集合で|X|=|Y|. (ii) X からY への全単射が存在する.
(iii) X からY への単射とY からX への単射が存在する.
3. 次は同値.
(i) X は有限集合で|X|<|Y|.
(ii) X からY への単射が存在するが, X からY への全単射は存在しない.
(iii) X からY への単射が存在するが, Y からX への単射は存在しない.
証明. 1は系 1.8.9, 補題 1.8.7 より明らか.
2は1と系 1.8.13より明らか. 3は1,2より明らか.
系 1.8.17. X 6=∅を集合, Y を有限集合とする. このとき次は同値. 1. X からY への単射が存在する.
2. Y からXへの全射が存在する.
証明. 系 1.8.9, 系1.8.10, 補題 1.8.7 系 1.8.8より明らか. 有限集合の濃度に関する基本的な性質を挙げておく. 定理 1.8.18. X, Y を有限集合とする. このとき,
1. XqY も有限集合で|XqY|=|X|+|Y|. 2. X×Y も有限集合で|X×Y|=|X||Y|. 3. YX も有限集合で|YX|=|Y||X|.
いずれも直感的には明らかであろう. が,きちんと証明しようとすると,自然数の和, 積, 冪乗をどのように定義するかはっきりさせる必要がある. この講義ではこの定理の証明は 述べない. （[6]等参照.）
系 1.8.19. X を有限集合とすると, P(X)も有限集合で|P(X)|= 2|X|. 証明. P(X)∼= 2X.
系 1.8.20. A, B を有限集合とする. このとき|A∪B|=|A|+|B| − |A∩B|.
証明.
A∪B = (A\B)q(A∩B)q(B\A) A = (A\B)q(A∩B)
B = (B\A)q(A∩B).
問 49. 1. A, B, Cを有限集合とする. このとき
|A∪B∪C|=|A|+|B|+|C| − |A∩B| − |B∩C| − |C ∩A|+|A∩B∩C|. 2.（包除原理） A0, A1, . . . , An−1 を有限集合とする. このとき,
[
i∈[n]
Ai
= X
I⊂[n]
|I|is odd
\
i∈I
Ai
− X
∅6=I⊂[n]
|I|is even
\
i∈I
Ai
.
注意 . T
i∈∅Ai =S
i∈[n]Aiと約束すれば（1.5節の注意参照）上の式は X
I⊂[n]
|I|is even
\
i∈I
Ai
= X
I⊂[n]
|I|is odd
\
i∈I
Ai
と書ける.
問 50. X 6=∅を順序集合,A ⊂X を有限部分集合とする. 1. Aが有界とはならないような例があれば挙げよ.
2. X が全順序集合であるとき,A 6=∅ならば,maxA,minAが存在することを, Aの 元の個数に関する帰納法を用いて示せ.
3. X が全順序集合であるとき, Aが有限部分集合であるならば, Aは有界であること を示せ.