数学 IB No.3
10月16日配布 担当：戸松 玲治∗
4 直積集合 , べき集合
4.1 直積集合
次は直積集合について学ぼう. n個の集合A1, . . . , Anに対して,その直積集合を次で定める:
A1×A2× · · · ×An:={(a1, . . . , an)|ai∈Ai, i∈ {1, . . . , n}}.
ここで元(a1, . . . , an)は, a1 からan を並べた組†である. もしAn のうち1つでも空集合ならば, A1× · · · ×An =∅と決める.
問題 33 (1pt.) 直積集合{1,2} × {1,2,3} の中の元をすべて書き上げ,元の総数を求めよ.
問題 34 (1pt.) 集合たちA1, . . . , Anはすべて有限集合であるとし,Anの元の数を#Anと書く. こ のとき,直積集合A1× · · · ×An の元の数は#A1· · ·#Anであることを示せ.
これ以降,一般に有限集合Bの元の個数を#Bと表す.
4.2 べき集合
次にべき集合について学ぼう. Aを集合とする. このAの部分集合の集まりをP(A)と書き,Aの べき集合(power set)と呼ぶ. つまり,
P(A) :={B |B⊂A}.
よってP(A)の元はAの元ではなく,Aの部分集合である. ここは初心者が間違えやすいところであ るので強調しておく. 慣れるまでちょっと大変かもしれないが,問題を解きながら落ち着いて考えて いこう. P(A)を2Aと書いたりもする. たとえば, A={1,2}なら,P(A) ={∅,{1},{2},{1,2}}と なる. だから,Aの部分集合{2}はP(A)の元だし, A={1,2}もそうである. つまり,{2} ∈ P(A) や{1,2} ∈P(A)がなりたつ. どういう集合を考えて,その元はどういうものからなるかを注意して おかなければならない. 実際この例に見るように,二つ集合A,Bがあったとして, A∈Bが矛盾し た式でないこともあるわけである. よって,x∈Aを「xをAの元として含む」と表現するとすっき りする. ここで言いたかったのは,集合の「元」はいつでも元とレッテルが張られているんではなく, バックグラウンドにいる集合があって始めて元ということ.
問題 35 (各1pt.) 次の有限集合のべき集合を記述せよ:
(1). {1}, (2).{1,2,3}, (3).{1,2} × {1,2}, (4).{1,2,3} × {1}.
ここで空集合∅のべき集合P(∅)が何か調べよう. B ⊂ ∅とすれば, 集合論の決まりから集合Bは 空集合∅を部分集合として含む. つまり∅ ⊂B. この2つの包含からB =∅が分かった. つまり P(∅) ={∅}である. 空集合∅の元の個数はもちろん0だが,そのべき集合P(∅)の元としてちゃんと
∅があるから,個数は1である. このように, 元の数がn個の集合のべき集合を取ると, 2n個の元を もつ新しい集合に変わる.
さて空集合の話に戻そう. P(∅)は空集合一つからなる集合{∅} であった. 繰り返しいうが,∅はも とは集合であったが,P(∅)を考える場合は元である. 少しややこしい話だが,次にべき集合P(∅)のべ き集合P(P(∅))を考える. P(∅) ={∅}は1点集合だから,P(P(∅)) ={∅, P(∅)}={∅,{∅}}である.
∗http://www.ma.noda.tus.ac.jp/u/rto/sched.html
†本当は組とは何なのか決めなければならないが,ここでは気にしなくてよい.
問題 36 (2pt.) P(P(P(∅)))の元を列挙せよ.
問題 37 (各1pt.) 次の問に答えよ.
(1) P(R)∩R=∅を示せ.
(2) P(X)∩X 6=∅となる集合Xの例をあげよ.
上の二つの共通部分を見て何か妙な気持ちがしたと思う. 少なくとも私はこれまで数学をやってい てこの種の共通部分は扱ったことがない,と思う. しかし二つの集合があれば必ず共通部分をとるこ とができるという集合論の決まりがあるので, 何か怪訝に思うかもしれないが躊躇する必要はない.
要は二つの集合が共通に含む元の集まりを考えようということである.
4.3 写像の集合
集合Aから集合Bへの写像全部の集まりをMap(A, B)とかBAと書く. つまり Map(A, B) :={f |f:A→B}.
なぜ「BのA乗」のような書き方をするのかは後の直積の所で分かるだろう.
さて今B = {0,1}としよう. このときMap(A,{0,1})の元は0,1に値をとるA上の関数であ る. 実はこの集合とP(A)との間に全単射が存在することを見よう. 各S ∈ P(A)に対して, 関数 χS∈Map(A,{0,1})を,x∈SならχS(x) = 1, x /∈SならχS(x) = 0と定める.
問題 38 (2pt.) 写像Φ :P(A)→Map(A,{0,1}),Φ(S) =χSは全単射であることを示せ.
問題 39 (1pt.) 有限集合Aに対して,#P(A) = 2#Aがなりたつことを示せ.
問題 40 (1pt.) #A=m,#B=n のとき,# Map(A, B)を求めよ.
問題38によってP(A)とMap(A,{0,1}) ={0,1}Aは同一視される. 2点集合{0,1}を形式的に2 に置き換えたもの2AがP(A)の別記号である理由はここにある.
4.4 添え字集合
数学をやっていると,しばしばいくらかの集合が数字などでパラメータ付けされているケースがあ る. たとえば自然数nに対してAn :={1,2, . . . , n}とすれば,Anたちはnが決まると一つ集合が決 まっている. またもしくは,何でもいいから空集合でない集合Λと,ある集合Aを用意して各λ∈Λ ごとにBλ :=Aとおけば,Bλたちはλが決まると一つ集合が決まっている(今はみんな同じ集合だ が). この考察を一般化して次のように考える. Λを何かある(空でない)集合とし,各元λ∈Λに対 してある集合Aλが対応しているとき,Aλの全体を{Aλ}λ∈Λ と書き, Λで添え字づけられた集合族 といって, Λを添え字集合(index set)という. 添え字集合は有限集合でも無限集合でもよい.
添え字集合を使うと合併,共通部分,直積も次のように一般化できる. {Aλ}λ∈ΛをΛで添え字づけ られた集合族とする. このときそれらの和集合(合併集合)と共通部分を次で定める.
∪
λ∈Λ
Aλ={x| ∃λ, x∈Aλ}, ∩
λ∈Λ
Aλ={x|x∈Aλfor allλ∈Λ}.
一方直積については,次のように定義する.
∏
λ∈Λ
Aλ= {
x: Λ→ ∪
λ∈Λ
Aλ
x(λ)∈Aλ }
.
つまり直積とは, Λから∪λAλへの写像xでx(λ)∈Aλとなっているものの集まり,ということであ る. もしΛ ={1,2, . . . , n}だったら, x∈∏
λ∈ΛAλに対して組(x(1), . . . , x(n))∈A1× · · · ×Anを 対応させることで同一視できるから,元を並べていったものの集まりであるA1× · · · ×An という集 合を一般化したものである. x(λ)をxλと書いて, x∈∏
λ∈ΛAλをx= (xλ)λ∈Λのように表示する.
直積集合はずらっと元を並べたものの集まりだと気持ちでは思っていてよい.
5 集合の濃度 , 可算無限 , 非可算無限
これから濃度という概念を準備する. 集合Aの濃度とはおおざっぱにいえば,「Aの元の個数」の ことである. この濃度という概念を生み出したのはCantorであり, この考えが生まれる前は無限集 合は無限であり,無限にも個数の概念があるとは考えられていなかった. この辺りから徐々にレベル が上がってくる. 終わりに手軽に読める良本をあげておいた. ぜひ一度よんでもらいたい.
さてAが有限集合の場合なら,個数という濃度の意味に何のあいまいさもない. しかし無限集合を 考えたときはそうはいかず,個数という概念を少し高みから見直す必要がある. それにはこうしたら よい. 今集合AとBの「元の個数」が等しかったとしよう. そうすればもちろんその間に全単射が できるだろう. 逆に全単射ができれば,「元の個数」も等しいだろう. つまりAとBの「元の個数」
というはっきりしない性質を全単射というはっきりした性質で定義してしまうのである.
定義 5.1 集合Aと集合Bの間に全単射が存在するとき,濃度(potency)‡が等しいという.
これからAとBの間に全単射が存在することを,A∼=Bと書こう. 「Aの濃度」はここでは厳密 に定めないことにするが,Aの濃度を#Aと書く(#Aは厳密にはAと濃度の等しい集合全部のこと である). AとBの濃度が等しいことは, #A= #Bと書かれる.
定義 5.2 自然数Nの濃度をℵ0(アレフゼロ), 実数Rの濃度をℵ(アレフ)と書く. 濃度ℵ0をもつ集 合(つまりNと全単射ができる集合)のことを可算集合という. 無限集合であって可算集合でないも のを非可算集合という.
濃度の大小も定めておこう. 集合A,Bの間に単射A→BができるときにAの濃度はBの濃度以 下であるといって, #A≤#Bと書く. たとえば埋め込みN→Rは単射なので, ℵ0≤ ℵである. 真
の不等号#A <#Bは, 単射A→Bは存在するが, 全単射は存在しないことを意味する.
問題 41 (2pt.) NとZ×Zの間の全単射を,具体的に1つ与えよ.
問題 42 (2pt.) A,Bが可算集合ならば,合併集合A∪Bも可算集合であることを示せ.
問題 43 (1pt.) 可算集合の無限部分集合は可算集合であることを示せ.
問題 44 (包除原理,2pt) 次を示せ.
(1) 有限集合A,B に対して#(A∪B) = #A+ #B−#(A∩B)が成立.
(2) 一般にn個の有限集合A1, . . . An に対して,
# ( n
∪
k=1
Ak
)
=
∑n i=1
#Ai+
∑n k=2
∑
i1<···<ik
(−1)k−1#(Ai1∩ · · · ∩Aik).
問題 45 (2pt.) Nn={1,2, . . . , n} とおく. 全単射f :Nn →Nn のうち,固定点§を持たないものの 個数はn!
∑n
k=0
(−1)k 1
k! で与えられることを示せ(Hint: 包除原理).
‡基数(cardinal number)ともいう.
§k∈Nns.t. f(k) =k,となるkのこと
問題 46 (2pt.) 自然数nの素因数分解をn=pe11· · ·perr と書く(piたちはnの素因数). またオイ ラーのφ関数をφ(n) := #{k∈N|1 ≤k≤nかつkとnは互いに素}と定める. このとき次の等 式を示せ:
φ(n) =n(1−p−11)· · ·(1−p−r1)
(Hint: Ai:={k∈N|1≤k≤nかつkはpjで割り切れる}とおき,補集合(∪r
i=1Ai)cを調べよ.) 次の2つの定理は非常に重要であり,数学科の常識として証明とともに憶えておいてもらいたい.
問題 47 (2pt.) 有理数の集合Qは可算集合であることを示せ.
問題 48 (2pt.) 実数の集合Rは非可算集合であることを示せ(Cantorの定理).
よってこの命題によってℵ0<ℵであることが分かった. 無限集合でもたっぷり元があると自然数 の濃度ℵ0を越すのである.
さて#A≤#Bかつ#B≤#Aが成り立っていたとして,果たして#A= #Bが従うであろうか.
これを保証するのが次のCantor-Bernsteinの定理である. 全単射を作るのが一般に難しくても,お互 いに単射で中に入れてやれば濃度が等しいことが言えるという優れものである.
問題 49 (Cantor-Bernstein,2pt.) 2つの単射f:A→Bとg:B→Aがあったとすれば,全単射 h:A→Bが存在する. つまり, #A≤#Bかつ#B ≤#A =⇒ #A= #B.
Cantor-Bernsteinの定理はもはや常識として使っていってよい(一度は証明を読んでおくこと).
問題 50 (1pt.) 集合A,B,C は A⊂B⊂C を満たすとする. A,C の濃度が等しいとき,B も同 じも濃度を持つことを示せ.
問題 51 (各2pt.) 次の等式を示せ.
(1) # Map({0,1},N) =ℵ0.
(2) # Map(N,{0,1}) =ℵ(Hint: 2進展開とCantor-Bernsteinの定理を用いよ).
問題38により2N=P(N)∼= Map(N,{0,1})であるから, #2N=ℵである. これを次で表現する.
2ℵ0=ℵ.
問題 52 (Cantor, (1):1pt,(2):2pt.) Aを集合とする. 次の問いに答えよ.
(1) #A≤#P(A)を示せ.
(2) #A <#P(A)を示せ.
よって一口に無限集合といっても,濃度が異なるものたちが無数に存在する.
#N<#P(N)<#P(P(N)))<· · ·<#Pn(N)<· · ·
無限！これほど人間の精神をゆり動かしたものはない.
ダフィット・ヒルベルト
参考文献
[志] 志賀浩二,集合への30講,朝倉書店.
[竹] 竹内外史,集合論とは何か,ブルーバックス.
