集合論

1
集合論
瓜生等
2014 年 4 月 1 日
目次
論理と命題
2
1.1
命題と真理値 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2
命題関数と述語論理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
集合
4
2.1
集合の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
集合の演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
集合の性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
写像
8
3.1
写像の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
全射と単射 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.3
写像の性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1
2
3
同値関係
10
4.1
同値関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.2
同値類 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
集合の濃度
12
5.1
濃度の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
5.2
有限集合と無限集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
5.3
濃度の性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
5.4
濃度の演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.5
濃度の順序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
6
順序関係
16
7
深い定理
18
4
5
集合論 2 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
1 論理と命題
数学は論理的に命題を証明することが必要である. また, このことにより, 絶対の信頼をおける命題を獲得で
きるようになる. このための確認と準備である.
1.1 命題と真理値
定義 1.1 真か, 偽のいずれかがはっきりしている文章を命題という. 与えられた命題に真ならば T , 偽なら
ば F を対応させ, これを命題の真理値という.
定義 1.2 2 つの命題 P, Q に対して, 二項論理記号 ∨, ∧, ¬, ⇒, ⇔ の真理値を以下の表で定義する.
P Q P ∨ Q P ∧ Q ¬P P ⇒ Q P ⇔ Q
T T
T
T
F
T
T
T F
T
F
F
F
F
F T
T
F
T
T
F
F F
F
F
T
T
T
P ∨ Q は命題 P と命題 Q のいずれかが真であれば真となる
P ∧ Q は命題 P と命題 Q がいずれも真であるときのみ真である.
¬P は命題 P の真偽が反転する.
P ⇒ Q は命題 P が真であり, 命題 Q が偽であるときのみ偽である.
定義 1.3 命題 P ⇒ Q に対して,
• 命題 Q ⇒ P を逆命題
• 命題 (¬P ) ⇒ (¬Q) を裏命題
• 命題 (¬Q) ⇒ (¬P ) を対偶命題
という.
命題 1.4 P , Q, R を命題とする. 論理記号 ∨, ∧, ¬, ⇒, ⇔ に関し, 以下の命題は常に真である. トートロ
ジーということもある.
1) ¬(¬P ) ⇔ P .
2) P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R).
3) P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R).
4) ¬(P ∨ Q) ⇔ (¬P ) ∧ (¬Q).
5) ¬(P ∧ Q) ⇔ (¬P ) ∨ (¬Q).
6) P ∨ (¬P ).
7) (P ⇒ Q) ⇔ ((¬Q) ⇒ (¬P )).
8) (P ⇒ Q) ⇔ ((¬P ) ∨ Q).
2
集合論 3 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
9) (P ⇔ Q) ⇔ ((P ⇒ Q) ∧ (Q ⇒ P )).
10) (P ∧ (P ⇒ Q)) ⇒ Q.
11) ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R).
¶
³
背理法の原理
トートロジー (8)(P ⇒ Q) ⇔ ((¬P ) ∨ Q) から, (P ⇒ Q) ⇔ ¬(P ∧ ¬Q) はトートロジーである.
そして, これは背理法を説明している.(P ∧ ¬Q) が偽の命題であることと (P ⇒ Q) が真の命題となるこ
とは同じことである. すなわち, 結論の否定と仮定が同時に成立することから矛盾がおこれば,P ⇒ Q が
真であることが証明できることになる.
のちに解るように数学の基礎は背理法による証明が多々登場する. 論理が数学を支えているといえる.
µ
¶
´
³
数学的帰納法
命題が An , n ∈ N がたくさんある場合, その命題を一挙に証明する方法である.
(1) A1 が真であることを示す.
(2) k ≥ 1 であるとき,Ak ⇒ Ak+1 が真であることを示す.
µ
´
これを証明できれば,(1) により A1 が真であるから,(2) を用いて,A2 が真であることがわかり, 以後 (2) を繰り
返して用いることにより,A3 , A4 , · · · がつぎつぎに真であることがわかるという仕組みである.「ドミノ倒し」
の仕組みである. 複数命題の証明法としてよく使用される.
1.2 命題関数と述語論理
定義 1.5 変数を含み, その変数の値を指定するごとに命題を表す文章を命題関数といい, x が変数のときは
P (x), Q(x) のように表す.
定義 1.6 述語論理
• 全称記号：命題関数 P (x) に対し, 「∀ xP (x)」とは「すべての x に対して P (x) が成り立つ」という
命題を表す.
• 存在記号：命題関数 P (x) に対し, 「∃ xP (x)」とは「P (x) が成り立つような x が存在する.」という
命題を表す.
¶
³
•「∀ xP (x)」の否定命題は「∃ x¬P (x)」
「すべての x に対して P (x) が成り立つ」の否定命題は「ある x に対して P (x) が成り立たたない」
•「∃ xP (x)」の否定命題は「∀ x¬P (x)」
「P (x) が成り立つような x が存在する」の否定命題は「すべての x に対して P (x) が成りたた
µ
ない」
´
これ以後背理法を多用するため, 否定命題をつくることに慣れておく必要がある.
3
集合論 4 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
¶
³
例題
∀ϵ > 0 ∃N ∀n ≥ N ⇒ |an − α| < ϵ
なる命題があるとする. この否定命題は
∃ϵ > 0 ∀N ∃n ≥ N |an − α| ≥ ϵ
∀ϵ > 0 ∃δ > 0 ∀x of |x − a| < δ ⇒ |f (x) − f (a)| < ϵ
なる命題があるとする. この否定命題は
∃ϵ > 0 ∀δ > 0 ∃x of |x − a| < δ |f (x) − f (a)| ≥ ϵ
µ
´
2 集合
2.1 集合の定義
定義 2.1 集合の表し方
(1) 要素 a, b, c, . . . を並べて {a, b, c, . . . } などと表す。
(2) 変数 x を含む命題関数 P (x) に対し, P (x) が真である x 全体の集合を {x：P (x)} で表す.
定義 2.2 集合の元
(1) 要素 a が集合 A の要素であるとき, a ∈ A または A ∋ a で表し, a は A に属するという. また要素 a
が A の要素でないとき, a ̸∈ A または A ̸∋ a と表す.
定義 2.3 集合の記号
(1)x ∈ A ⇒ x ∈ B であるとき, A ⊂ B または B ⊃ A で表わす. このとき A は B の部分集合であると
いう.
(2) A ⊂ B, A ⊃ B が成立するとき A = B で表す.
(3) A ⊂ B, A ̸= B であるとき、A は B の真部分集合であるという.
特別な集合として、要素をもたない集合を扱えるようにしておくと便利である。そこで、要素をもたない集
合を空集合とよび, ∅ で表す.
問題 1 任意の集合 A に対して、∅ ⊂ A であることを示せ。
これから登場することになる数の集合の記号を紹介しておこう.
記号 2.4 数の記号
N : 自然数全体からなる集合
Z: 整数全体からなる集合
Q: 有理数全体からなる集合
R: 実数全体からなる集合
C: 複素数全体からなる集合
4
集合論 5 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
2.2 集合の演算
一般に集合を考えるとき、ある一つの集合 Ω を固定し、その部分集合を考えることがある。この様な Ω を
全体集合という。以下全体集合を Ω として説明する。
定義 2.5 集合の演算
(1) A ∪ B = {x : x ∈ A ∨ x ∈ B} を A と B の和集合という。
(2) A ∩ B = {x : x ∈ A ∧ x ∈ B} を A と B の共通集合という。
(2) A ∩ B = ∅ であるとき、A + B = A ∪ B で、A + B を定義し、A と B の直和という。
定義 2.6 J を添数集合とし,α ∈ J に対して一つの集合 Aα ⊂ Ω が対応しているとする。A = {Aα : ∀α ∈ J}
を考える。これは集合の集合となっており、このような A を集合族という。
注意 2.7 特に。J = N であるとき、集合族を {An }∞
n=1 とかくことがある。
定義 2.8 集合の演算
集合族 A = {Aα : ∀α ∈ J} の和集合と共通集合を以下で定義する。
(1) 和集合
∪
Aα = {x ∈ Ω : ∃α ∈ J x ∈ Aα }
α∈J
(2) 共通集合
∩
Aα = {x ∈ Ω : ∀α ∈ J x ∈ Aα }
α∈J
(3) 直和
α ̸= β ⇒ Aα ∩ Aβ = ∅ であるとき、
∑
Aα =
α∈J
で、
∑
∪
Aα
α∈J
Aα を定義し、これを直和という。
α∈J
注意 2.9 特に。J = N であるとき、
∞
∪
n=1
An ,
∞
∩
An とかくことがある。
n=1
定義 2.10 差集合と補集合
(1) 集合 A, B の差集合 A\B は以下で定義する。
A\B = {x : x ∈ A ∧ x ̸∈ B}
(3) 集合 A の補集合 Ac は以下で定義する。
5
集合論 6 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
Ac = Ω\A
.
問題 2 A, B ⊂ Ω であるとき、A\B = A ∩ B c であることを示せ。
定義 2.11 直積集合
(1) 集合 X, Y に対して、
X × Y = {(x, y) : x ∈ X ∧ y ∈ Y }
を集合 X, Y の直積 (集合) という。また、(x, y) を順序対という。
(2) 一般に集合 X1 , X2 , · · · , Xn に対して、
X1 × X2 × · · · × Xn = {(x1 , x2 , · · · , xn ) : xk ∈ Xk (k = 1, 2, · · · , n)}
を集合 X1 , X2 , · · · , Xn の直積 (集合) という。また (x1 , x2 , · · · , xn ) を順序対という。
注意 2.12
n
∏
Xn = X1 × X2 × · · · × Xn と書くことがある。
k=1
2.3 集合の性質
全体集合を Ω とする。また、A, B, C ⊂ Ω とする。
命題 2.13 和集合と共通集合
(1) A ∪ B = B ∪ A, A ∩ B = B ∩ A
(2) A ∪ A = A, A ∩ A = A
(3) A ∪ ∅ = A, A ∩ ∅ = ∅
(4) A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C
(5) A ⊂ A ∪ B, B ⊂ A ∪ B, A ∩ B ⊂ A, A ∩ B ⊂ B
(6) A ⊂ B ⇔ A ∪ B = B ⇔ A ∩ B = A
(7) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
命題 2.14 De Morgan
(1)
(A ∪ B)c = Ac ∩ B c , (A ∩ B)c = Ac ∪ B c
(2)
(
∪
α∈J
A α )c =
∩
Acα , (
α∈J
∩
α∈J
6
Aα )c =
∪
α∈J
Acα
集合論 7 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
定義 2.15 集合族の単調性
∞
集合族を {An }∞
n=1 とするとき、n = 1, 2, · · · に対して An ⊂ An+1 が成立しているとき、{An }n=1 は単
調増加であるといい、An ↗ と書く。An ⊃ An+1 が成立しているとき、{An }∞
n=1 は単調減少であるといい、
An ↘ と書く。
定義 2.16 集合族の極限集合
集合族を {An }∞
n=1 とするとき、
lim sup An =
n→∞
∞ ∪
∞
∩
Ak , lim inf An =
n→∞
n=1 k=n
∞ ∩
∞
∪
Ak
n=1 k=n
をそれぞれ、{An }∞
n=1 の上極限集合、下極限集合という。
lim sup An =
n→∞
∞ ∪
∞
∩
∞ ∩
∞
∪
Ak = lim inf An =
n→∞
n=1 k=n
Ak
n=1 k=n
が成立するとき、この集合を lim An と書き、{An }∞
n=1 の極限集合という。
n→∞
命題 2.17 極限集合の性質
(1) lim inf An ⊂ lim sup An
n→∞
n→∞
(2) (lim inf Acn )c = lim sup An , (lim sup Acn )c = lim inf An
n→∞
n→∞
∞
∪
(3) An ↗⇒ lim An =
n→∞
n=1
n→∞
n→∞
An , An ↘⇒ lim An =
n→∞
∞
∩
An
n=1
問題 3 A ∩ B = φ ⇐⇒ A ⊂ B c ⇐⇒ B ⊂ Ac を示せ。
問題 4 A△B = (A ∪ B) \ (A ∩ B) を示せ。
ここで、A△B = (A\B) ∪ (B\A) である。
問題 5
(1) {An }∞
n=1 の上極限集合は無限個の An に入る元を集めたものであることを示せ。
(2) {An }∞
n=1 の下極限集合は有限個以外の An に入る元を集めたものであることを示せ。
問題 6 つぎの集合列についてその上極限集合と下極限集合を求めよ。
)
{ ( 1
− n , 1 − )n1
(
An =
1
1
n, 1 + n
n は奇数
n は偶数
問題 7 An ↗ であるとき, 次を証明せよ。
lim An =
n→∞
∞
∪
n=1
7
An
(2.1)
集合論 8 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
3 写像
3.1 写像の定義
定義 3.1 写像の定義と写像が同じであること
(1) X, Y を集合として, X の各要素に対して Y の１つの要素を指定できるとき, この対応を X から Y
への写像と呼んで, f : X → Y と表わす. また、各 x ∈ X について, 写像 f : X → Y で対応する Y の要素
を f (x) で表し, これを x の f による像と呼ぶ.
(2) ２つの写像 f : X → Y と g : Z → W が等しいとは, X = Z かつ Y = W であり, すべての x ∈ X
に対して f (x) = g(x) が成り立つことであり, このとき f = g と書く.
定義 3.2 集合の像と逆像
f : X → Y を写像とする。
(1) A ⊂ X であるとき、{f (x) : x ∈ A} となる集合を f の A の像といい、f (A) であらわす。特に、f (X)
を Imf と書くこともある。
(2) B ⊂ Y であるとき、{x ∈ X : f (x) ∈ B} となる集合を f の B の逆像といい、f −1 (B) と書く。
定義 3.3 合成写像恒等写像逆写像
(1) X, Y , Z を集合, f : X → Y , g : Y → Z を写像とする. 各 x ∈ X に対して, g(f (x)) ∈ Z を対応さ
せる X から Z への写像を f と g の合成と呼んで g◦f で表す.
(2) X の各要素 x を x 自身に対応させる写像を X の恒等写像と呼び, 1X または idX などで表す.
(3) 写像 f : X → Y に対し, g◦f = 1X , f ◦g = 1Y を満たす写像 g : Y → X を f の逆写像といい,
g = f −1 で表す.
3.2 全射と単射
定義 3.4 全射単射
1) 写像 f : X → Y について,Y の各要素 c に対して, f (x) = c となる x ∈ X が存在するとき, f は上へ
の写像 (または全射) であるという. onto ( surjection)
2) 写像 f : X → Y について,f (x) = f (y) (x, y ∈ X) ならば x = y が成立するとき, f は 1 対 1 写像 (ま
たは単射) であるという. one to one ( injection)
3) 1 対 1 かつ上への写像を全単射という. one to one onto (bijection)
問題 8 写像 f : X → Imf は全射であることを示せ. このように Imf を確定させることは重要である.
なぜ全射や単射を考えるかの説明をしよう. まず全射を考える.
¶
³
いま,X, Y ⊂ R として, 全射である関数 f ：X → Y を考える. このとき, 任意の c ∈ Y に対して,f (x) = c
となる x ∈ X が存在すると言うことは, 方程式 f (x) = c の解が X にあるということ示している. このよ
うに全射は方程式の可解性を表現していることになる.
µ
8
´
集合論 9 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
では単射は何を表現しているか.
¶
³
いま,X, Y ⊂ R として, 単射である関数 f ：X → Y を考える. このとき,c ∈ Y に対して, 方程式 f (x) = c
を考える. この方程式をみたす解を x1 , x2 ∈ X としよう.
f (x1 ) = c
f (x2 ) = c
であるので,f (x1 ) = f (x2 ) が成立し, 単射であるので,x1 = x2 が従う. これは方程式 f (x) = c の解が唯
一であることを示している. このように単射は方程式の解の一意性を表現していることになる. これが解
が唯一であることを示す方法であることに注意したい.
µ
´
命題 3.5 写像 f : X → Y の逆写像が存在するためには, f が全単射であることが必要かつ十分であり f の
逆写像はただ一つに定まる.
例 3.6 平方根
f : R → R, f (x) = x2 とする. このとき, 逆関数を考えたいが, まず全射とするために, Imf を計算する. こ
れは Imf = {y : y ≥ 0} である. そこでまず Y = {y : y ≥ 0} とおくことにし, f : R → Y として, これが単
射かどうかを確かめる.x1 , x2 ∈ R として, f (x1 ) = f (x2 ) とすると,x21 = x22 が得られるが, 因数分解すること
により, x1 = ±x2 となり単射は成立していない. そこで, 定義域も限定しないと単射とできないことが判明す
る. 定義域を制限する可能性はいくつもあるが, 最も自然な制限は X = {x : x ≥ 0} であろう. このようにし
て,f : X → Y なる全単射が得られる. この逆関数 f (x) を
√
x と書いているのである. この様に具体的な関数
の全単射を得るためには, 値域 (逆関数の定義域となる) をまず求め, つぎに定義域 (逆関数の値域となる) を考
察することが必要であることに注意したい.
3.3 写像の性質
定義 3.7 一般集合族の直積集合
集合族 A = {Aα : ∀α ∈ J} に対して、写像
ϕ : J ∋ α → x α ∈ Xα
の全体の集合を
∏
Xα と書き、
α∈J
集合族 A = {Aα : ∀α ∈ J} の直積 (集合) という。また、ϕ を
∏
xα または (xα ) と書くことがある。そ
α∈J
して、xα を ϕ の座標という。
特に、Xα = X であるとき、X J =
∏
Xα と書き、J を指標とし、X を基底とした巾集合という。
α∈J
注意 3.8 X J は J から X への写像全体となっていることに注意しよう。
定義 3.9 2A
A を集合とする。このとき、写像
9
集合論 10 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
ϕ : A → {0, 1}
の全体を 2A と書くことがある。
定義 3.10 集合の特性関数
集合 A の部分集合を S とするとき、S の特性関数を
{
1S (a) =
1 (a ∈ S)
0 (a ∈
/ S)
と定義する。
問題 9
2A = {1S : S ⊂ A}
であることを示せ。
定義 3.11 集合 A の部分集合全体を P(A) と書くことにする。
命題 3.12 P(A) から 2A への写像 f を f (S) = 1S , S ∈ P(A) と定義すると f は全単射である。これより、
P(A) と 2A は同一視できることになる。
命題 3.13 A1 , A2 ⊂ X, B1 , B2 ⊂ Y , ϕ : X → Y であるとき、以下が成立する。
(1) ϕ(A1 ∪ A2 ) = ϕ(A1 ) ∪ ϕ(A2 ), ϕ(A1 ∩ A2 ) ⊂ ϕ(A1 ) ∩ ϕ(A2 )
(2) ϕ−1 (B1 ∪ B2 ) = ϕ−1 (B1 ) ∪ ϕ−1 (B2 ), ϕ−1 (B1 ∩ B2 ) = ϕ−1 (B1 ) ∩ ϕ−1 (B2 ),
(3) A1 ⊂ ϕ−1 (ϕ(A1 )), B1 ∩ ϕ(X) = ϕ(ϕ−1 (B1 ))
問題 10
φ : X → Y, ψ : Y → Z とする。このとき次を示せ。
(1)φ, ψ が全単射ならば ψ ◦ φ は全単射で (ψ ◦ φ)−1 = φ−1 ◦ ψ −1 .
(2)ψ ◦ φ が全射ならば ψ は全射.
(3)ψ ◦ φ が全射で ψ が単射ならば φ は全射.
(4)ψ ◦ φ が単射ならば φ は単射.
(5)ψ ◦ φ が単射で φ が全射ならば ψ は単射.
問題 11
次を示せ。
(1)A × (B ∪ C) = (A × B) ∪ (A × C)
(2)A × (B ∩ C) = (A × B) ∩ (A × C)
4 同値関係
定義 4.1 関係
10
集合論 11 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
集合 X と Y の関係とは直積集合 X × Y の部分集合 R のことである。x ∈ X, y ∈ Y に対して、
(x, y) ∈ R ⊂ X × Y であるとき、x と y は R 関係にあるといい、xRy または x ∼ y と書く。
4.1 同値関係
定義 4.2 同値関係
集合 X と X の関係 R が以下を満足するとき、関係 R は X の同値関係という。
(1) ∀x ∈ X に対して、(x, x) ∈ R (反射律)
(2) (x, y) ∈ R ⇒ (y, x) ∈ R (交換律)
(3) (x, y), (y, z) ∈ R ⇒ (x, x) ∈ R (推移律)
4.2 同値類
定義 4.3 同値類
関係 R が X の同値関係であるとする。
[x] = {y ∈ X : (x, y) ∈ R}
で、[x] を定義する。これを x の同値類といい、x を同値類の代表元という。
命題 4.4 関係 R が X の同値関係であるとする。同値類についてい以下が成立する。
x, y ∈ X とするとき、
(1) [x] ̸= ∅
(2) (x, y) ∈ R ⇔ [x] = [y]
(3) (x, y) ∈
/ R ⇔ [x] ∩ [y] = ∅
定義 4.5 関係 R が X の同値関係であるとする。同値類全体を X/R または X/ ∼ と書き、同値関係 R によ
る商集合という。
例 4.6 x, y ∈ R に対して、x ∼ y ⇔ x − y ∈ Z と ∼ を定義すると、∼ は同値関係となる。このときの商集
合を R/Z と書くと、
ϕ : [0, 1) → R/Z, ϕ(x) = [x]
は全単射である。
問題 12
X = {2, 3, 4, 5} と Y = {3, 6, 7, 10} に対して関係を「x ∈ X が y ∈ Y を割り切る」によって
定める。この関係を表す、順序対の集合 R を求めよ。
問題 13
R を実数の集合とするとき、x, y ∈ R に対して x ∼ y を x − y ∈ Q(有理数の集合) でを定め
る。∼ は同値関係であることを示せ。またこのとき、0 が属する同値類は何になるか。
11
集合論 12 / 19
問題 14
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
自然数の直積 N × N に次の関係を入れる。(m, n), (m′ , n′ ) ∈ N × N に対して m + n′ = m′ + n
のとき、(m, n) ∼ (m′ , n′ ) とする。∼ は同値関係となることを示せ。また、この同値関係は何を意味して
いるかを考えよ。
問題 15
自然数の直積 N × N に次の関係を入れる。(m, n), (m′ , n′ ) ∈ N × N に対して mn′ = m′ n の
とき、(m, n) ∼ (m′ , n′ ) とする。∼ は同値関係となることを示せ。また、この同値関係は何を意味してい
るかを考えよ。
問題 16
X を全体集合とし、X の部分集合を元とする集合を S(X) と書く。S(X) の元 A, B に対して
bijection φ : A → B が存在するとき、A ∼ B と書く。このとき ∼ は同値関係となることを示せ。
特に X が元を n 個もつ有限集合であるとき、その商集合の元は何個あるか。このことからこの同値関係
は何を意味しているかを考えよ。
5 集合の濃度
この節では、集合の個数の概念を有限集合から無限集合へと拡張する。
5.1 濃度の定義
定義 5.1 濃度
X, Y が集合で、X, Y の間に全単射 f : X → Y が存在するとき、X, Y は対等であるといいき、X ∼ Y と
書く。このとき、X, Y は同じ濃度 (基数) をもつという。X の濃度を今後 |X| と書くことにする。
問題 17
集合 X, Y の濃度が同じである、すなわち X ∼ Y は同値関係であることを示せ。
5.2 有限集合と無限集合
定義 5.2 有限集合無限集合可算集合高々可算な集合
(1) ある n ∈ N が存在して、 {1, 2, · · · , n} ∼ A とできるとき A を有限集合という。有限集合でないとき、
無限集合であるという。
(2) N ∼ A であるとき A を可算集合であるという。可算集合でない無限集合を非可算集合であるという。
(3) 可算集合または有限集合であるとき、高々可算な集合であるという。
問題 18
素数全体の集合は無限集合であることを示せ。
定義 5.3 濃度の記号
(1) n ∈ N に対して、 {1, 2, · · · , n} ∼ A であるとき |A| = n と定義する。(有限集合の個数)
(2) N ∼ A であるとき |A| = ℵ0 と定義する。ℵ0 はアレフゼロと読む。
12
集合論 13 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
(3) R ∼ A であるとき |A| = ℵ と定義する。ℵ はアレフと読む。
例 5.4 Z は可算集合である。
問題 19
n ∈ N に対して、ϕ : Z → N を以下のように定義する。
ϕ(n) = 2n + 1, ϕ(−n) = 2n
このとき、。ϕ は全単射であることを示せ。
例 5.5 N 2 = N × N は可算集合である。これより、さらに、n ∈ N に対して、N n は可算集合であること
がわかる。
問題 20
m, n ∈ N に対して、ϕ : N 2 → N を以下のように定義する。
ϕ(m, n) =
1
(m + n − 2)(m + n − 1) + m
2
このとき、。ϕ は全単射であることを示せ。
定理 5.6 無限集合は可算部分集合を含む。
定理 5.7 可算集合の任意の部分集合は高々可算である。
例 5.8 Q は可算集合である。
定理 5.9 R は可算でない無限集合である。
5.3 濃度の性質
定理 5.10 濃度の定理
(1) A1 ∼ B1 , A2 ∼ B2 , A1 ∩ A2 = B1 ∩ B2 = ∅ ⇒ A1 + A2 ∼ B1 + B2
(2) A1 ∼ B1 , A2 ∼ B2 ⇒ A1 × A2 ∼ B1 × B2
定理 5.11 A, B, C, Aα (α ∈ J) に対して以下が成立する。
(1) (B × C)A ∼ B A × C A
(
)A
∏
∏
(2)
Aα
∼
AA
α
α∈J
α∈J
(3) A ∩ B = ∅ のとき C A+B ∼ C A × C B
( )A
( )B
(4) C A ∼ C A×B ∼ C B
13
集合論 14 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
5.4 濃度の演算
定義 5.12 濃度の和
α, β を濃度とし、 X, Y が互いに素 (X ∩ Y = ∅) で、|X| = α, |Y | = β となる集合であるとする。
α + β = |X + Y |
と定義し、これを濃度 α, β の和という。
注意 5.13 X1 ∩ Y1 = X2 ∩ Y2 = ∅ で、|X1 | = |X2 |, |Y1 | = |Y2 | となる集合であるとする。
このとき、すでに示して命題より、|X1 + Y1 | = |X2 + Y2 | であった。このことから濃度の和は集合のとり
かたに依存していない。このように、不定性のありそうな定義ではらるが、それが実はきちんと定義できてい
るとき、その定義は well deﬁned であるという。
定義 5.14 濃度の積
α, β を濃度とし、 X, Y を |X| = α, |Y | = β となる集合であるとする。
αβ = |X × Y |
と定義し、これを濃度 α, β の積という。
問題 21
濃度の積の定義は well deﬁned であることを示せ。
定義 5.15 濃度のべき乗
α, β を濃度とし、 X, Y を |X| = α, |Y | = β となる集合であるとする。
αβ = |X Y |
と定義し、これを濃度 α, β のべき乗という。
問題 22
濃度のべき乗の定義は well deﬁned であることを示せ。
命題 5.16 α, β, γ を集合の濃度とする。このとき以下が成立している。
(1) α + β = β + α (2) αβ = βα
(3) (α + β) + γ = α + (β + γ) (4) (αβ)γ = α(βγ)
(5) α(β + γ) = αβ + αγ
注意 5.17 巾乗についても成立している法則があるが、ここでは省略する。
14
集合論 15 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
5.5 濃度の順序
定義 5.18 濃度の大小
X が Y の部分集合と対等であるとき、
|X| ≤ |Y |
と定義する。また、|X| ≤ |Y | であり |X| ̸= |Y | であるとき、|X| < |Y | と定義する。
定理 5.19 Cantor
|X| < 2|X|
例 5.20 この定理より、ℵ0 < 2ℵ0 となるが、さらに 2ℵ0 = ℵ である。これは、実数が 2 進数展開できること
に注意すればよい。
このことより、ℵ0 < ℵ であるが、この間に別の濃度は存在するであろうか。当初はそのような濃度は存在
しない (連続体仮説) と考えられてきたが、Choen(1963) はこの仮説は集合論の公理系とは独立であることを
示した。
定理 5.21 Bernstein
|X| ≤ |Y |, |X| ≥ |Y | ⇒ |X| = |Y |
例 5.22
ℵ0 = n + ℵ0 = ℵ0 + ℵ0 = nℵ0 = ℵn0
例 5.23
問題 23
ℵ2 = ℵ, ℵ0 ℵ = ℵ
ベルンシュタインの定理を用いて、次を示せ。
(1) {x|0 < x ≤ 1} ∼ {x|0 ≤ x ≤ 1}
(2) {(x, y)|0 < x ≤ 1, 0 < y ≤ 1} ∼ {(x, y)|0 ≤ x ≤ 1, 0 ≤ y ≤ 1}
(3) a < b であるとき、[a, b] ∼ R2
(4)a < b であるとき、[a, b] ∼ D 但し、D ⊂ R2 で D は少なくとも１つの内点を持つとする。
問題 24
C[0, 1] ∼ R を示せ。但し、 C[0, 1] とは [0, 1] で定義された連続関数全体とする。
ヒント：連続関数 f (x) は x が有理数のときの f (x) の値がわかれば、x が無理数のときにも f (x) の値が
わかる。従って、可算集合から可算集合への関数と同等となるを用いる。当然このことも証明が必要。
問題 25
無理数全体の濃度は ℵ であることを示せ。
15
集合論 16 / 19
問題 26
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
次の濃度に対する等式を示せ。
n + ℵ = ℵ0 + ℵ = ℵ + ℵ = nℵ = ℵn = ℵ
問題 27
有理数を端点とする区間全体からなる集合の濃度を求めよ。
問題 28
任意の無限集合はそれ自身と対等な真部分集合を含むことを示せ。
6 順序関係
定義 6.1 集合 R ⊂ X × X が順序関係にあるとは以下の 3 つを満すときを言う。
(1) (x, x) ∈ R
(2) (x, y) ∈ R, (y, x) ∈ R ⇒ x = y
(3) (x, y) ∈ R, (y, z) ∈ R ⇒ (x, z) ∈ R
¶
³
(x, y) ∈ R を x ≼ y または y ≽ x と書くことにすると、いかにも順序らしい。
この記号で上記の定義を再度書いてみると以下となる。
(1) x ≼ x
(2) x ≼ y, x ≽ y ⇒ x = y
(3) x ≼ y, y ≼ z ⇒ x ≼ z
順序 ≼ をもつ集合 X を順序集合といい (X, ≼) と書くことにする。
µ
定義 6.2 (X, ≼) が有向集合であるとは
任意の x, y ∈ X に対して、ある z ∈ X が存在して、x ≼ z, y ≼ z となることである。
定義 6.3 (X, ≼) が全順序集合であるとは
任意の x, y ∈ X に対して、x ≼ y または y ≼ x となることである。
Note: 全順序集合は有向集合である。
定義 6.4 最大元 (最小元) が x(∈ X) であるとは
任意の y ∈ X に対して、y ≼ x(y ≽ x) が成立することである。
定義 6.5 極大元 (極小元) が x(∈ X) であるとは
x ≼ y(y ≽ x) となる y ∈ X があるとき、x = y が成立することである。
定義 6.6 X 部分集合 A の上界 ( 下界) が x ∈ X であるとは
任意の a ∈ A に対して、a ≼ x(a ≽ x) が成立することである。
16
´
集合論 17 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
定義 6.7 集合 A の上界 (下界) の中に最小元 (最大元) があるとき、それを上限 (下限) といい sup A(inf A)
と書く。
Note: (X, ≼) が全順序集合のとき極大元 (極小元) と最大元 (最小元) は一致する。
定義 6.8 (X, ≼) が全順序集合であるとする。X の空でない任意の部分集合 A が常に最小元ともつとき、
(X, ≼) は整列集合であるという。
Note: 自然数の集合は整列集合であるが、整数と実数の集合は整列集合とはならない。
定義 6.9 x ≼ y(x ≽ y) で x ̸= y であるとき、x ≺ y(x ≻ y) と書く。
定義 6.10 (X, ≼), (Y, ≤) がふたつの順序集合であるとする。
写像 f : X → Y が全単射が存在し、
x1 ≺ x2 のとき f (x1 ) < f (x2 )
が成立するとき、(X, ≼), (Y, ≤) は順序同型であるという。
定義 6.11 順序集合 (X, ≼), (Y, ≼) があり、X ∩ Y = ∅ とする。このとき、集合の直和 X + Y の順序を
(x, y ∈ X, x ≼ y) ∨ (x, y ∈ Y, x ≼ y) ∨ (x ∈ X, y ∈ Y )
であるとき、x ≤ y と定義する。
問題 29
上記で ≤ を定めるとき、(X + Y, ≤) は順序集合となることを示せ。これを順序和という。
定義 6.12 順序集合 (X, ≼), (Y, ≼) に対して、集合の直積 X × Y の順序を
(x = x′ , y ≼ y ′ ) ∨ (x ≼ x′ )
であるとき、(x, y) ≤ (x′ , y ′ ) と定義する。
問題 30
上記で ≤ を定めるとき、(X × Y, ≤) は順序集合となることを示せ。これを辞書式順序という。
問題 31
(X, ≼), (Y, ≼) が全順序ならば、(X × Y, ≤) も全順序となることを示せ。
問題 32
自然数 m が自然数 n で割り切れるとき、n ≼ m と書くことにする。このとき、≼ は N の順序
集合であるが、全順序集合でないことを示せ。
問題 33
x ∈ R2 に対して ||x|| を原点と x との距離と定義する。x ≼ y を ||x|| ≤ ||y|| で定義するとき、
≼ は R2 の順序とならないことを示せ。
17
集合論 18 / 19
問題 34
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
順序集合 (X, ≼) において、s が集合 A(⊂ X) の上限であるための必要十分条件は次の２条件を
満足することであることを示せ。
(1) 任意の x ∈ A に対して x ≼ s であること。
(2) 任意の x ∈ A に対して x ≼ a であるとき、s ≼ a であること。
問題 35
X = {1, 2, 3, 4, · · · , 12} であるとき、m が自然数 n で割り切れるとき、n ≼ m と書くことに
する。
(1) 全ての元に対して順序関係を書き出せ。
(2)X は有向集合であるか。
(3)X の最大元はなにか、なければ極大元を全て書け。
問題 36
以下の問題は通常の不等号を順序として考えよ。
(1) 偶数の集合と奇数の集合は順序同型であることを示せ。
(2) 正の有理数と整数は順序同型でないことを示せ。
(3) (−∞, ∞) と (0, 1) は順序同型であることを示せ。
問題 37
(1) 自然数 n に対して X = {a1 , a2 , a3 , · · · , an },Y = {b1 , b2 , b3 , · · · } に対して順序和 X + Y を作ると
き、X + Y と自然数の集合 N とは順序同型となることを示せ。
(2) 自然数 n に対して X = {1, 2, 3, 4, · · · , n} に通常の不等号の順序を考えるとき X × X に辞書式順序
を入れとき、(p, q) ∈ X × X は最初から何番めの順となるか。
7 深い定理
¶
³
• 選択公理
空でない集合からなる集合族において、各集合から同時に１つずつ元を取り出すことができる。
• Zorn の補題
空でない順序集合の任意の全順序部分集合が上界を持っているとき、この順序集合は少なくとも一
つの極大元を持つ。
• 整列可能定理
µ
任意の集合は適当な順序によって整列化できる。
以上のように選択公理の様に明らかに成立していると思われる事実も数学の論理から見ると深い内容を内包
していることが解る。これらの同値性を示すことはかなり難解である。
18
´
集合論 19 / 19
6:48pm 2014 年 4 月 1 日 Uryu Hitoshi
参考文献
[1] 集合・位相・距離梅垣大矢垣原共立出版
[2] 関数解析の基礎コルモゴロフフォミーン岩波書店
[3] 集合・位相・測度志賀浩二朝倉書店
[4] 集合への 30 講志賀浩二朝倉書店
[5] 入門集合と位相竹之内実教出版
[6] 集合論入門赤摂也培風館
[7] 新版集合論辻正次小松勇作共立出版
19

Download Report