有限濃度を 持つ集合を 有限集合[finite set]といい, 有限でない集合を 無限集合 [infinite set]という. また, 集合 Aが 可算濃度を 持つとき, すなわち, cardA =ℵ0
のとき,A を可算集合[countable set, enumerable set]という. 可算集合 Aは Nと 対等となるので, 全単射 h :N → Aが ある. 各 i∈ N に 対し て, h(i) = ai とすれ ば,A={ai |i∈N}と表せる. 従って,その元に 1,2, . . . と番号付けができる集合 が 可算集合である.
定理 6.5 ど んな 無限集合 X に 対し ても, N から X への単射 h : N→ X が 存在 する. すなわち,ど んな無限集合も必ず 可算部分集合を含む.
証明概略 まず, x1 ∈X を 取る. 互いに 異な る元 x1, . . . , xn ∈ X が 取れ たと する と,X は 無限集合なので,xn+1∈X\ {x1, . . . , xn}が 取れ る. 帰納法により,xi ∈X (i∈N)が xi=xj (i=j)となるように取れ, {xi|i∈N} ⊂Xが 求めるもの. 注意: 上の議論には 選出公理 が 関係し ているが, 一般的には 上のような 証明で 許さ れ る. 厳密には,各i∈Nに 対し て,xi が 存在することと 集合{xi |i∈N}あるいは 点列(xi)i∈Nが 存在することには 違いが ある. このことを 意識すれば, つぎ のよ うに 証明すれば よい.
X の 有 限 部分集合全体を Fin(X) と すると, 選出公理よ り, ϕ : Fin(X) → X で ϕ(A) ∈ X \A と な る写 像が 取れ る. 写像 h : N → X を h(1) = ϕ(∅) (= x1), h(n+ 1) =ϕ({h(1), . . . , h(n)})と 帰納的(再帰的)に 定義できる. このと き,hは 単 射となり,h(N)は X の可算部分集合となる.
写像 hに 関し ても厳密には 再帰定理に よる. すなわ ち, ˜ϕ : Fin(X) → Fin(X)を
˜
ϕ(A) = A∪ {ϕ(A)} と 定義し て, 再帰定理を 適応すれば, 写像 h′ : N → Fin(X) で h′(1) ={x1} か つ h′(n+ 1) = ˜ϕ(h′(n))とな るものが 一意的に 決まる. ここで,
˜
ϕ(h′(n))\h′(n) ={ϕ(h′(n))}なので,写像 h:N→X は h(n) =ϕ(h′(n))と 定義 できる.
可算部分集合を含む集合は 無限集合であるから, 上の定理 6.5 の逆も成立する. よって, つぎ が 成立する:
X — infinite⇔cardX ℵ0
こ うし て,可算濃度は 最小の無限濃度といえ る.
定理 6.6 無限集合は, その自身と対等となる真部分集合を含むが, 有限集合は, そ のど んな真部分集合とも対等にならない.
証明の方針 前半は, 定理6.5 より, 無限集合Aが 可算部分集合B を 含むことに 注 意. N∼N\ {1}より,∃b∈B, B∼B\ {b}. これを 用いて,A∼A\ {b}が 示せる. 後半は,演習3.7を用いて示せる(6.1節の冒頭にあるcardA=nのwell-defindness と 同様).
この定理によれば,その自身と対等となる真部分集合を含むか含まないかによっ て,その集合が 無限であるか 有限であるかが 決まる. すなわち, その自身と対等と なる真部分集合を含む集合は無限集合であり, そのど んな真部分集合とも対等にな らない集合は 有限集合である.
演習 6.2 無限集合から有限部分集合を除いても,濃度は変わらないことを示せ.
ヒント 上の定理の証明(後半)を 参考にせよ.
演習 6.3 N2 =N×N は 可算集合であることを示せ.
ヒント 対応(m, n)→2m−1(2n−1)はN2から Nへの全単射. (素因数分解定理) N2 の 可算性を 示す 直観的方法: つぎ のよ うに N2 の 元を Nで 番号付け ることに よ り,NからN2 への全単射が 定義できる. 式で 定義するのは 面倒である.
(1,1)
(1,2) //(1,3)
{{xxxxxxxx
(1,1)
(1,2)
(1,3)
(2,1)
;;
xx xx xx xx
(2,2)
{{xxxxxxxx
(2,3) あるいは (2,1)
;;
xx xx xx xx
(2,2)
;;
xx xx xx xx
(2,3)
(3,1)
(3,2)
;;
xx xx xx xx
(3,1)
;;
xx xx xx xx
(3,2)
;;
xx xx xx xx
(4,1)
;;
xx xx xx xx
(4,1)
;;
xx xx xx xx
演習 6.4 (1) Z および (2) Qが 可算であることを示せ.
ヒント ベルンシュタ イン の定理の系 6.3(1)が 適用できる.
集合 X は, 有限または 可算であるとき, 高々可算[at most countable]であると いい,51 高々可算でないとき, 非可算[uncountable]であるとい う. すなわち,
X — at most countable ⇔cardX ℵ0
X — uncountable ⇔cardX >ℵ0 演習 6.5 高々可算な集合に 関し て,つぎ を示せ:
(1) 2つの高々可算な集合の直積集合は 高々可算である. すなわち,
cardA, cardB ℵ0 ⇒cardA×B ℵ0
51高々可算を 可算といい,可算を 可算無限ということもある.
(2) それぞれ高々可算である集合の高々可算な和集合は高々可算である. すなわち, card Λℵ0,
∀λ∈Λ, cardAλ ℵ0
⇒card
λ∈Λ
Aλ ℵ0
(3) 無限集合に 高々可算な集合を加えても濃度は 変わらない. すなわち, cardA ℵ0, cardB ℵ0 ⇒cardA∪B = cardA
ヒント (1)は,A×B から N2への単射を 作れ. (2)は, Λ×Nから
λ∈ΛAλ への 全射を 作れ. (3)を 示すのに A∩B=∅と 仮定し てよい. Aの可算部分集合を Cと すれば, cardC= cardC∪B となる. これを 用いて, A∼A∪Bを 示す.
演習 6.6 R\Q∼Rを示せ.
ヒント 演習6.5(3)が 適用できる.
定理 6.7 Rは 非可算集合である. すなわち, c>ℵ0 である.
証明の方針 (0,1)⊂Rより, card(0,1) cardRなので, card(0,1)>ℵ0 を 示せば よい. ど んな写像 h:N→(0,1)も全射とはならないことを 示す. 各h(n)を 10 進 法 無限小数展開 でつぎ のよ うに 一意的に 表す:52
h(n) = ∞
i=1
10−ihi(n), hi(n) = 0,1, . . . ,9 (i.e., 0.h1(n)h2(n)h3(n). . .)
各 i∈Nに 対し て, hi(i)が 奇数ならxi= 2, hi(i)が 偶数なら xi = 1とする. この ときx=∞
i=110−ixi∈h(N).
上の証明で用いられた論法は,カント ールの対角線論法[Cantor’s diagornal
pro-cess] と呼ばれている. つぎ の定理の証明にも同様の論法が 用いられ る:
定理 6.8 (カント ールの定理) 任意の集合 X に 対し て, cardP(X)>cardX.
証明の方針 x → {x} に より X か ら P(X) へ の 単 射が 得られ るので cardX cardP(X). よって,ど んな写像h:X →P(X)も全射とはならないことを示せば よ いが,A={x∈X|x∈h(x)} ∈P(X)を 考えれば, A∈h(X).
カント ールの逆理[Cantor’s Paradox]: ラッセルの 逆理に より, “すべて の集 合の集まり” Ωを集合すると矛盾が 生じ たが,上の定理を用いると濃度に関す る別の矛盾が 生じ る. もし Ωが 集合ならば Ωの部分集合も集合であるから, Ω の元となる. すなわ ち, P(Ω)⊂Ωとなり, cardP(Ω)card Ω. これは 上 の定理に 矛盾する.
定理 6.5によれば, ℵ0 は最小の無限濃度である. 最小の非可算濃度を ℵ1 と表す が,定理6.7の主張はcℵ1に他ならない. つぎ の主張を連続体仮説53[continuum hypothesis]とい う:
c=ℵ1
52例えば, 0.5は 0.4999· · · と 表す. このよ うに 実数の小数表示が 一意的でないことに 注意せよ. また, 0が 無限小数展開できないことにも注意せよ.
53仮説はかつて 仮設と 書いた.
連続体仮説は 証明不可能: ゲ ーデ ル54 とコーエン55 により,通常の数学で 仮 定され る事実(公理)から 出発し た議論では,この連続体仮説は 肯定も否定も 出来ないことが 示され た.
[補足事項]
ペアノの体系の存在: 定理 6.6に よれば,無限集合はその 真部分集合と 対等な 集合である. このよ うな 無限集合が 存在することを用いて,ペアノの体系の存在が 示せる.
無限集合Xが 存在すれば,全射ではない単射f :X →X が 存在する a∈X\f(X)を 取り,X の部分集合族Aをつぎ のよ うに 定義する:
A={A⊂X|a∈A, f(A)⊂A}. X ∈AよりA=∅なので,N =
Aが 得られ,N ∈Aとなる f(N)⊂N よりf|N :N →N を 得る
このとき, (N, a, f|N)はペアノの公理(N3), (N4), (N5)を 満たす 実際, (N3)と (N4)は明らか
(N5): A⊂N で (i)a∈Aかつ(ii)x∈A⇒f(x)∈Aとすれば, A∈AよりN ⊂A ∴A=N