情報数学 I − A 講義のポイント No.13
復習
［１］
１）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,≼)の例RX ≡ {f | f :X →Rの写像の全体}とし，f ≼g def⇔ f(x)5g(x) (∀x∈X)で≼ を定めると，(
RX,≼)
は順序集合である。
３）(X,≼)を順序集合とする。Xの最大元，最小元，極大元，極小元
1. Xの最大元 x∈X def⇔ y≼x (∀y∈X), 2. Xの最小元 x∈X def⇔ x≼y (∀y∈X)
3. X の極大元 x∈X def⇔ x≼y, y∈X ⇒ x=y, 4. Xの極小元 x∈X def⇔ y ≼x, y ∈X ⇒ x=y
４）順序集合(X,≼)とXの部分集合Aに対して，Aの上界，下界，上限，下限
1. x∈X が Aの上界の元 def⇔ a≼x (∀a∈A), 2. x∈X が Aの下界の元 def⇔ x≼a (∀a∈A) 3. x∈X が Aの上限 (x= supA) def⇔ Aの上界の最小元, 4. x∈X が Aの下限 (x= infA) def⇔ A
の下界の最大元
５）順序集合(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,≼)は帰納的順序集合である。
１）束（Lattice）
(X,≼)を順序集合とする。∀x, y∈Xに対して，{x, y}の上限(x∨y)と下限(x∧y)が存在するとき，Xを束という。
２）束の例
1. X = 2Ω とする。 A ≼ B def⇔ A ⊆ B で X 上に関係≼を定めると，(X,≼)は順序集合である。さらに，
A∨B≡sup{A, B}=A∪B, A∧B≡inf{A, B}=A∩B より，{A, B}の上限A∨B，{A, B}の下限A∧B は，それぞれ，A∪B, A∩Bであることがわかるので，(X,≼)は束である。
2. X を区間 [0,1]上の実数値連続関数の全体とする。X 上に関係 ≼を f ≼ g def⇔ f(t) 5 g(t) (t∈[0,1]) で定めると，(X,≼)は順序集合である。さらに，(f ∨g) (t) ≡ max{f(t), g(t)} (t∈[0,1]), (f ∧g) (t) ≡ min{f(t), g(t)} (t∈[0,1]) とf ∨g, f ∧g を定めると，これらは{f, g}の上限，下限であることがわかるの で，(X,≼)は束である。
３）束の性質
(X,≼)が束であるとき，∀x, y, z∈Xに対して次が成立する。
1. 結合律： (x∨y)∨z=x∨(y∨z)， (x∧y)∧z=x∧(y∧z),2. 交換律： x∨y=y∨x， x∧y=y∧x,
1
3. ベキ等律： x∨x=x， x∧x=x, 4. 吸収律： x∨(y∧x) = (x∨y)∧x=x ３）束の種類
分配束(X,≼)def⇔ 束(X,≼)が次の分配律を満たすとき，(X,≼)を分配束という。
• 分配律： x∧(y∨z) = (x∧y)∨(x∧z)， x∨(y∧z) = (x∨y)∧(x∨z)
モジュラー束(X,≼)def⇔ 束(X,≼)が次のモジュラー律を満たすとき，(X,≼)をモジュラー束という。
• モジュラー律： x≼z ⇒ x∨(y∧z) = (x∨y)∧z 1. 単位元1 ∀x∈X, x∨1 = 1, x∧1 =x
2. 零元0 ∀x∈X, x∨0 =x, x∧0 = 0
3. x∈Xに対して，xの補元xc xc∨x= 1, xc∧x= 0
直補束(X,≼)def⇔ 束(X,≼)に対して，Xの全ての元xが補元xcをもつとき，(X,≼)を直補束という。
ブール（Boole）束(X,≼)def⇔ 束(X,≼)が直補束で，分配律を満たすとき，(X,≼)をブール束という。
［ 2 ］
集合の濃度集合Xの元・要素の個数（例えば，α）を集合の濃度(cardinal number)または基数といい，|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への全単射が存在する。
2-2)無限集合（infinite set）
有限集合でない集合を無限集合という。
2-2-1) 可算集合(countable set) 命題2 自然数の全体Nは無限集合である。
自然数の全体Nの濃度をℵ0(”アレフゼロ”と読む)と表す。|N|=ℵ0濃度ℵ0をもつ集合Xを可算(countable)集合ま たは可付番集合という。すなわち，X∼Nである集合Xは濃度ℵ0をもつ可算集合である。
命題 3 (1)整数の全体Zは可算集合である。 (2)N2=N×Nは可算集合である。
例)有理数の全体Qは可算集合である。
無限集合の性質
無限集合Xの部分集合Aに対して，A⊂X ⇒ |A|=|X|となる場合がある。有限集合Y の部分集合Bに対して，
B⊂Y ⇒ |B| ≤ |X|が常に成り立つ。
2-2-2)非可算集合(uncountable set)
命題 4 実数の全体Rは可算でない無限集合である。
実数の全体Rの濃度を連続体の濃度といい，ℵ(”アレフ”と読む)で表す。上記の証明で用いられた方法を対角線論法と いう。
１）濃度に関する基礎定理
定理 5 (1.4) (1)共通の添数集合Jを持つ２つの集合族{Aα;α∈J}と{Bα;α∈J}があり，これらは各々互いに素(i.e., α̸=β ⇒Aα∩Aβ=∅, Bα∩Bβ=∅). このとき，任意のα∈J に対して，Aα∼Bαならば
∑
α∈J
Aα∼∑
α∈J
Bα
2
(2)２つの集合族{Aα;α∈J}，{Bα;α∈J}について，任意のα∈Jに対して，Aα∼Bα ならば
∏
α∈J
Aα∼ ∏
α∈J
Bα
(3)２つの集合A, Bについて，任意のa∈Aに対して，B∼Ba となる集合Baが対応するならば BA∼ ∏
a∈A
Ba
(4)任意の集合A, B, C, Aα (α∈J)に対して，
(i) (B×C)A ∼ BA×CA , (ii)
(∏
α∈J
Aα
)A
∼ ∏
α∈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)より，この定義は整合 的である。
定理 6 (1.5) α, β, γを任意の濃度とするとき，次が成立する。
(1) α+β=β+α , (2) αβ=βα
(3) (α+β) +γ=α+ (β+γ) , (4) (αβ)γ=α(βγ) (5) α(β+γ) =αγ+βγ , (6) (αβ)γ =αγβγ (7) αβαγ =αβ+γ , (8) (
αβ)γ
=αβγ 定理7 ℵ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<ℵ
定理 8 (Cantorの定理) |X|<2|X|
定理 9 (Schroder-Bernstein (シュレーダー-ベルンシュタイン)の定理) |X| ≤ |Y| かつ |Y| ≤ |X| であれば |X|=
|Y|
［ 3 ］
１）数列{an}の上極限（値），下極限（値）
広義の実数全体 R=R∪ {−∞,+∞}
i)数列{an} ⊂R
単調増加列 an ↑ a15a25a35· · ·, 単調減少列 an↓ a1=a2=a3=· · · An≡ {am; m=n}と置くと，Anは単調減少の集合列 An↓ A1⊇A2⊇A3⊇ · · · an≡supAn = sup
m≥nam (Anの上限), an ≡infAn = inf
m≥nam (Anの下限)
3
定理10 数列{an},{ an}
に対して，1. an ↓ 2. an↑ 定義11 数列{an}に対して，
1. lim sup
n→∞ an≡ inf
n≥1an= inf
n≥1
(
m≥nsupam
)
を数列{an}の上極限（値）という。2. lim inf
n→∞an≡sup
n≥1an = sup
n≥1
(
m≥ninf am )
を数列{an}の下極限（値）という。
3. 数列{an}に対して，上極限と下極限が一致する，すなわち，lim sup
n→∞ an = lim inf
n→∞anのとき，数列{an}の極限 lim
n→∞an が存在する。
(a) lim
n→∞an=a (∈R) のとき，数列{an}はaに収束する。
(b) lim
n→∞an= { +∞
−∞ のとき，数列{an}は発散する。
2. Rにおいて，級数 ∑∞
n=1an≡ lim
m→∞(∑m
n=1an) 命題12 ∀n1, n2に対して， inf
m≥n1am5 sup
m≥n2
am
定理13 数列{an}に対して，次が成立する。
1. lim inf
n→∞an5lim sup
n→∞ an,2. an ↑ ⇒ lim
n→∞an= sup
n≥1an, 3. an↓ ⇒ lim
n→∞an= inf
n≥1an
4. lim sup
n→∞ an= lim
n→∞
(
m≥nsupam
)
, 5. lim inf
n→∞an = lim
n→∞
(
m≥ninfam
)
２）集合列{An}の上極限（集合），下極限（集合）
X; 集合 (2X,≼)
A≼B def⇔ A⊆B
単調増加の集合列 An↑ A1⊆A2⊆A3⊆ · · ·, 単調減少の集合列 An↓ A1⊇A2⊇A3⊇ · · · An≡ {Am; m=n}と置くと，Anは単調減少の集合族の列 An↓ A1⊇ A2⊇ A3⊇ · · · An ≡supAn = sup
m≥nAm (Anの上限)， An≡infAn= inf
m≥nAm (Anの下限) 定理14 集合列{An}に対して，次が成り立つ。
1. sup
n≥1An=
∪∞ n=1
An, 2. inf
n≥1An=
∩∞ n=1
An, 3. An↓, 4. An ↑
定義15 集合列{An}に対して，
1. lim sup
n→∞ An≡ inf
n≥1An= inf
n≥1
(
m≥nsupAm
)
を集合列{An}の上極限（集合）という。2.lim inf
n→∞An≡sup
n≥1An= sup
n≥1
(
m≥ninf Am
)
を集合列{An}の下極限（集合）という。
定理16 集合列{An}に対して，次が成り立つ。
1. lim sup
n→∞ An= ∩∞
n=1
∪∞ m=n
Am, 2. lim inf
n→∞An= ∪∞
n=1
∩∞ m=n
Am, 3. lim inf
n→∞An ⊆lim sup
n→∞ An
4. An↑ ⇒ lim
n→∞An= sup
n≥1an = ∪∞
n=1
An, 5. An↓ ⇒ lim
n→∞An = inf
n≥1an= ∩∞
n=1
An
4
