情報数学 I-A 講義のポイント No.8
復習 No.7
１）X上の順序関係R
i) 反射律 ∀x∈X に対して，(x, x)∈R
ii) 反対称律(x, y)∈R かつ (y, x)∈R ⇒ x=y iii) 推移律(x, y)∈R，(y, z)∈R ⇒ (x, z)∈R 上記のi)ii)iii)を満たす関係Rを(半)順序関係という。
X上の順序関係Rに対して，(x, y)∈R を x≼y と書き，(X,≼)で 順序集合を表す。
２）順序集合(X,≼)の種類 有向集合，
∀x, y∈X に対して，∃z∈X s.t. x≼z かつ y≼z
有向集合の例 X = 2Ω A≼B def⇔ A⊆B と≼を定め ると，(X,≼)は有向集合である。
全順序集合，
∀x, y∈X に対して， x≼y または y≼x
全順序集合の例 X =R x≼y def⇔ x5y と≼を定める と，(X,≼)は全順序集合である。
整列集合，全順序集合(X,≼)が整列集合であるとは
∀Y (̸=∅)⊂X が最小元をもつ
整列集合の例 X =N x≼y def⇔ x5y と≼を定める と，(X,≼)は整列集合である。
帰納的順序集合，順序集合(X,≼)が帰納的順序集合であるとは 任意の全順序部分集合Y ⊆Xが上界をもつ
帰納的順序集合の例 A ≡ {f |f :X →Y への単射の全体} fα : Xα(=domfα) → Y, f ≼ g def⇔ domf ⊆ domg かつ g¹domf=f (g(x) =f(x) (∀x∈domf))
と≼を定めると，(A,≼)は帰納的順序集合である。
３）集合の濃度
集合Xの元・要素の個数（例えば，α）を集合の濃度(cardinal num- ber)または基数といい，
|X|=α, ♯(X) =α
などで表す。集合Aから集合Bへの全単射が存在するとき，集合Aと集合 Bは対等（equipotent）であるといい，
A∼B
で表す。このとき，集合Aと集合Bの濃度（要素の数）は等しい。
|A|=|B| 2-1)有限集合（finite set）
X が有限集合とは，
0≤ |X|=n <+∞
を満たすことをいう。
命題 1 上記の集合Aと集合Bは対等である。すなわち，集合Aから集合B への全単射が存在する。
∃f :A→B s.t. f(ak) =k−1∈B (∀k= 1,2,· · ·, n) 2-2)無限集合（infinite set）
有限集合でない集合を無限集合という。
2-2-1)可算集合(countable set)
命題 2 自然数の全体Nは無限集合である。
自然数の全体Nの濃度をℵ0(”アレフゼロ”と読む)と表す。
|N|=ℵ0
濃度ℵ0をもつ集合Xを可算(countable)集合または可付番集合という。す なわち，
X ∼N
である集合Xは濃度ℵ0をもつ可算集合である。
命題 3 整数の全体Zは可算集合である。
命題 4 N2=N×Nは可算集合である。
例)有理数の全体Qは可算集合である。
無限集合の性質
無限集合Xの部分集合Aに対して，
A⊂X ⇒ |A|=|X|
となる場合がある。有限集合Y の部分集合Bに対して，
B⊂Y ⇒ |B| ≤ |X|
が常に成り立つ。
2-2-2) 非可算集合(uncountable set)
命題5 実数の全体Rは可算でない無限集合である。
実数の全体Rの濃度を連続体の濃度といい，ℵ(”アレフ”と読む)で表す。
上記の証明で用いられた方法を対角線論法という。
講義 (No.8) の内容
１）濃度に関する基礎定理
定理 6 (1.4) (1)共通の添数集合Jを持つ２つの集合族{Aα;α∈J}と{Bα;α∈J}
があり，これらは各々互いに素(i.e.,α̸=β ⇒Aα∩Aβ=∅, Bα∩Bβ=∅).
このとき，任意のα∈Jに対して，Aα∼Bα ならば X
α∈J
Aα∼X
α∈J
Bα
(2) ２つの集合族{Aα;α∈J}，{Bα;α∈J}について，任意のα∈J に 対して，Aα∼Bα ならば
Y
α∈J
Aα∼ Y
α∈J
Bα
(3) ２つの集合A, Bについて，任意のa∈Aに対して，B ∼Ba となる 集合Baが対応するならば
BA∼ Y
a∈A
Ba
(4)任意の集合A, B, C, Aα (α∈J)に対して，
(i) (B×C)A ∼ BA×CA
(ii) ÃY
α∈J
Aα
!A
∼ Y
α∈J
(Aα)A
(iii) CA+B ∼ CA×CB
(iv) ¡
CA¢B
∼ CA×B ∼ ¡
CB¢A
２）濃度に関する演算
濃度についての演算を考える。α, βを与えられた濃度とし，X, Y を互いに 素で|X|=α,|Y|=βとなる集合とするとき，
|X+Y|=α+β
と定義し，これを濃度αとβの和という。この定義が整合的(well-defined) であることを示す必要がある。すなわち，このようなX, Y が存在すること と，そのようなX, Y の選び方によらず|X+Y|が一定になることを示せば よい。
まず，|X0|=α,|Y0|=βとなる集合X0, Y0が存在することは濃度の定義 に含まれる。X=X0× {1}, Y =Y0× {2}とおくと，
X ∼X0, Y ∼Y0
かつ
X∩Y =∅
となるので，互いに素で|X|=α,|Y|=βとなる集合X, Y の存在がいえる。
次に，|X+Y|がX, Y の選び方によらないことは，
X ∼X1, Y ∼Y1 かつ X1∩Y1=∅ のとき，定理１.４(1)より
X+Y ∼X1+Y1
が成り立つ。よって，α+βの定義は整合的である。
濃度αとβの積を，|X|=α,|Y|=βとなる集合を用いて，
αβ=|X×Y|
と定義すると，定理１.４(2)より，この定義は整合的である。また，|X|= α,|Y|=βのとき，
αβ=¯¯XY¯¯
と定義すると，定理１.４(3),(2)より，この定義は整合的である。
定理7 (1.5) α, β, γを任意の濃度とするとき，次が成立する。
(1) α+β =β+α , (2) αβ=βα (3) (α+β) +γ=α+ (β+γ) , (4) (αβ)γ=α(βγ) (5) α(β+γ) =αβ+αγ , (6) (αβ)γ =αγβγ (7) αβαγ =αβ+γ , (8) ¡
αβ¢γ
=αβγ
定理8
ℵ0=n+ℵ0=ℵ0+ℵ0=nℵ0=ℵ20=· · ·=ℵn0 (∀n∈N)
２つの集合X, Y において，XがY の部分集合に対等であるとき，
|X| ≤ |Y|
とかいて，|X|は|Y|より大きくない，または，|Y|は|X|より小さくない，
という。
|X| ≤ |Y| かつ |X| ̸=|Y| のとき，
|X|<|Y|
とかいて，|X|は|Y|より小さい，または，|Y|は|X|より大きいい，という。
例)
ℵ0<ℵ 定理 9 (Cantorの定理)
|X|<2|X|
定理 10 (Schroder-Bernstein (シュレーダー-ベルンシュタイン)の定理)
|X| ≤ |Y| かつ |Y| ≤ |X| であれば |X|=|Y|
