2015年8月14日更新

順序数・濃度の簡単なまとめ

PDF版

このページでは選択公理を仮定しない.

順序数についてはそのうち書きます. |X| で X の濃度を表す.

定義 X と Y を集合とする.

  1. |X|≦|Y| ⇔ 単射 X→Y が存在する
  2. |X|=|Y| ⇔ 全単射 X→Y が存在する
  3. |X| < |Y| ⇔ |X|≦|Y| かつ |X|≠|Y|
  4. |X|≦*|Y| ⇔ 全射 Y→X が存在するか, X= ∅
  5. |X| <* |Y| ⇔ |X|≦* |Y| かつ |X|≠|Y|

命題1

  1. |X|≦|Y| かつ |Y|≦|X| ならば |X|=|Y| (Bernsteinの定理)
  2. |X| < |P(X)| (Cantorの定理)
  3. |X|≦|Y| ならば |X|≦*|Y|
  4. |X|≦*|Y| ならば |X|≦|P(Y)|

定義 κ と λ を濃度とする. κ=|X|, λ=|Y|, X∩Y= ∅ となるような X, Y を取る.

  1. κ+λ:=|X∪Y|
  2. κ・λ:=|X×Y|
  3. κλ :=|XY| (XY:= { f: Y→X } )
  4. κ=λ+μ となる濃度 μ が唯一つ存在するとき, κ-λ:=μ
  5. κ=λ・μ となる濃度 μ が唯一つ存在するとき, κ÷λ:=μ

もちろんこれらはwell-definedである.

定義 整列された無限集合 X を使って |X| と表される濃度をアレフと言い, アレフ で表す.特に,自然数全体がなす整列集合で表されるアレフを アレフ0 と書く.

命題2 二元集合 2= { 0, 1 } の濃度を 2 と表せば,任意の濃度 κ に対して 2・κ=κ+κ, κ2=κ・κ である.また κ=| X | のとき 2κ=| P(X) | .

命題3 任意の濃度 κ, λ について
κ≦λ ⇔ ある濃度 μ が存在して κ+μ= λ

命題4 濃度 κ, λ≧2 に対し κ+λ≦κ・λ .

証明 κ=|X|, λ=|Y|, X∩Y= ∅ となる集合を取る. a≠b となる a, b∈X , s≠t となる s, t∈Y を取る. φ: X∪Y→X×Y を

φ(x) := <x, s> (x∈X のとき)
φ(x) := <a, x> (x∈Y\{ s } のとき)
φ(x) := <b, t> (x=s のとき) .

と定めれば φ は単射である.

命題5 アレフ0≦κ ならば 2κ-κ=2κ

証明 κ=|X| となる集合 X を取る. X∋x |→ { x } ∈P(X) により X⊂P(X) とみなしたとき | P(X) |≦| P(X)\X | を示せばよい.

X に含まれない元 ∞ を一つ取り Y := X∪ { ∞ } と置く. f: P(X)→P(Y)\X を f(x) := x∪{∞} で定める.これは明らかに単射だから |P(X)|≦|P(Y)\X| である.ここで アレフ0≦κ だから κ+1=κ ,即ち |Y| = |X| であり,よって |P(Y)\Y| = |P(X)\X| となる.またアレフ0≦|P(Y)\Y| だから

|P(Y)\X| = |(P(Y)\Y)∪{∞}| = |P(Y)\Y|+1 = |P(Y)\Y|

となる.従って |P(X)|≦|P(X)\X| が分かった.

命題6 任意のアレフ アレフに対してアレフ2=アレフ

証明 無限順序数 α に対し |α×α| = |α| を示せばよい. 任意の順序数 β>0 は

β = ωβ1・m1+…+ωβn・mn, 1≦n, m1, …, mn < ω, β≧β1 > … > βn

の形に一意に書ける(Cantor標準形.キューネン第I章演習問題6の解答を参照). 全単射 g: ω×ω→ω を g(0, 0)=0 となるように一つ取る. β, β'<α が与えられたとき α≧β1 > … > βn を使って

β = ωβ1・m1+…+ωβn・mn
β' = ωβ1・m1'+…+ωβn・mn'

と書いて f(β, β') := ωβ1・g(m1, m1')+…+ωβn・g(mn, mn') と定めれば,これは全単射 f: α×α→α を与える.

命題7 任意のアレフアレフ, アレフ'に対しアレフアレフ'=アレフ+アレフ'=max{ アレフ, アレフ' } .

証明 アレフ'≦アレフ としても一般性を失わない.このとき

アレフ
アレフ+アレフ'
アレフアレフ' (命題4による)
アレフアレフ
=アレフ (命題6による)
=max{ アレフ, アレフ' } .

命題8 濃度 κ, λ, μ とアレフ アレフ が κ・アレフ≦λ+μ を満たすとき, κ≦μ または アレフ≦λ である.

証明 κ=|X|, λ=|Y|, μ=|Z| となる集合 X, Y, Z と アレフ=|W| となる整列順序集合 W を取る. Y∩Z= ∅ としてよい.仮定より単射 f: X×W→Y∪Z が存在する. A:=f-1(Y), B:=f-1(Z) とすれば |A|=|Y|=λ, |B|=|Z|=μ, X×W=A∪B である.

(i) { x }×W⊂A となる x∈X が存在するとき.
アレフ=|W| = |{ x }×W|≦|A|=λ である.

(ii)どの x∈X についても ¬{ x }×W⊂A となるとき.
wx := min{ w∈W | <x, w>∈B } と書けば κ= |X| = |{ <x, wx> | x∈X }|≦|B|=μ である.

命題8.5 濃度 κ, λ, μ とアレフ アレフ が κ・λ≦アレフ+μ を満たすとき, κ≦アレフ または λ≦μ .

証明 κ=|X|, λ=|Y|, μ=|Z| となる集合 X, Y, Z と アレフ=|W| となる整列順序集合 W を取る.仮定より単射 f: X×Y→W∪Z が存在する.

(i) ある x∈X について f({x} ×Y)⊂Z となるとき.
g: Y→Z を g(y):=f(x, y) で定めれば g は単射で λ=|Y|≦|Z|=μ である.

(ii)任意の x∈X について ¬f({x} ×Y)⊂Z となるとき.
Yx:= { y∈Y | f(x, y)∈W } ≠ ∅ である. g: X→W を g(x):=min { f(x, y)|y∈Yx } で定めれば g は単射で κ=|X|≦|W|=アレフ である.

命題9 濃度 κ, λ とアレフ アレフアレフ≦κ+λ を満たすとき, アレフ≦κ または アレフ≦λ である.

証明 アレフ≦κ+λ とすると命題6より アレフアレフ≦κ+λ となる.よって命題8より アレフ≦κ または アレフ≦λ が分かる.

命題10 濃度 κ, λ とアレフ アレフアレフ≦κ・λ を満たすとき, アレフ≦κ または アレフ≦λ である.

証明 κ=|X|, λ=|Y| となる集合 X, Y と アレフ=|W| となる整列順序集合 W を取る.単射 f: W→X×Y が存在する. πX, πY をそれぞれ X×Y から X, Y への射影として U:=πX(f(W))⊂X, V:=πY(f(W))⊂Y と置く. W の整列順序を使って, U, V は整列可能である.また f(W)⊂U×V である.このとき命題7を使って アレフ=|W|≦|U×V|=|U|・|V|= max { |U|, |V| } となる.故に アレフ≦|U| または アレフ≦|V| であるが,それぞれ アレフ≦κ, アレフ≦λ を導く.

命題11 Pfin(X) := { Y⊂X | Y は有限集合 } と置く.
整列可能な無限集合 X に対し |X| = | Pfin(X) |

証明 X の整列順序 ≦ を取る.

Y∈Pfin(X) を取り, |Y| = n とする.このとき順序同型 fY: n→(Y, ≦) が一意に存在する.そこで f(Y) := <n, fY(0), …, fY(n-1)>∈ { n } ×Xn と定める.これにより単射 f: Pfin(X)→∪n=0( { n } ×Xn) が定義できる.

次に,命題6により単射 g2: X2→X が存在する.そこで n > 2 に対して gn: Xn→X を

gn(x1, …, xn-1, xn) := g2(gn-1(x1, …, xn-1), xn)

で定めると,各 gn は単射である. g0: X0→X を一つ取り, g1 := idX とする.この { gn }n=0 より単射 g: ∪n=0( { n } ×Xn)→∪n=0( { n } ×X) が

g(n, x1, …, xn) := (n, gn(x1, …, xn))

で定義できる.

また,命題7により |ω×X| = |X| である.

以上により

|X|≦|Pfin(X)|≦|∪n=0( { n } ×Xn)|≦|∪n=0( { n } ×X)| = |ω×X| = |X|

である.

命題12 X を集合とする. |α|\not\leq|X| となるような順序数 α が存在する.

証明 Γ(X) := { α | α は順序数, |α|≦|X| } と置く. Γ(X) は集合である.

W:= { R⊂X×X | R は X のある部分集合を整列する } と定義する. W は集合である.よって「 W に現れる整列順序と同型な順序数全体」も集合である.この集合は Γ(X) と一致する.

順序数の推移的な集合は順序数だから, Γ(X) も順序数である.よって Γ(X) ∉ Γ(X) だから | Γ(X) |\not\leq| X | となる.

この Γ をHartogs関数という.

また κ=|X| のとき κ* := |Γ(X)| と書く.これをHartogs numberという.Hartogs numberはアレフである.

命題13

  1. Γ(X) は |α|\not\leq|X| となるような順序数 α のうち最小の順序数である.
  2. κ*アレフ\not\leqκ となるようなアレフ アレフ のうち最小のアレフである.
  3. κ*≦22κ2
  4. κ*≦222κ
  5. 無限濃度 κ に対して κ**=(κ+κ*)*
  6. 無限濃度 κ に対して (κ2)**

証明 (3) κ=|X| となる X を取り

W:= { R⊂X×X | RはXのある部分集合を整列する }

と置く.明らかに |Γ(X)|≦*|W| である.よって |Γ(X)|≦|P(W)| であり

κ*=|Γ(X)|≦|P(W)|≦|P(P(X×X))|=22|X|2=22κ2

となる.

(4) κ=|X| となる X を取り α∈Γ(X) とする.単射 f: α→X に対して Af:= { f''β | β < α } ∈P(P(X)) と定める. B := { Af | α∈Γ(X), f: α→X は単射 } と置けば B⊂P(P(X)) となる. φ: B→Γ(X) を φ(Af) := dom(f) とすれば φ は全射となる.よって |Γ(X)|≦*B だから |Γ(X)|≦P(B)≦|P(P(P(X)))| .

(5) κ*≦κ+κ* だから κ**≦(κ+κ*)* である. κ** < (κ+κ*)* と仮定すると κ** はアレフだから, (κ+κ*)* の最小性より κ**≦κ+κ* となる.よって命題命題9により「 κ**≦κ または κ**≦κ* 」となり矛盾する.故に κ**=(κ+κ*)* である.

(6) κ≦κ2 だから κ*≦(κ2)* である. κ* < (κ2)* と仮定すると κ* はアレフだから (κ2)* の最小性により κ*≦κ2 となる.故に命題命題9から κ*≦κ となり矛盾する.故に κ*=(κ2)* である.

定義 集合 X に対して K(X):= { f: α→X |α は順序数, f は単射 } をKruse関数という. κ=|X| のとき κ := |K(X)| と書く.

明らかに,次が成り立つ.

命題14

  1. κ≦2κ2
  2. κ≦22κ
  3. κ < κ
  4. アレフ アレフ に対して アレフ=2アレフ

命題15

  1. κ・μ≦(κ+μ)
  2. κ≧アレフ0⇒κ
  3. κ+κ=κ⇒(κ)2

命題16 κ≧アレフ0 とアレフ アレフ が κ≦κ+アレフ を満たすとき, κ < κ=2κアレフ である.

証明 κ≧アレフ0 だから命題15より κ である.よって κ+κ≦κ≦κ+アレフ となる.故にある アレフ'≦アレフ が存在して κ+κ=κ+アレフ' となる.このとき アレフ'≦κ+κ だから命題9により アレフ'≦κ が分かる.故に κ+アレフ'=κ であるから κ+κ=κ となる.従って命題15より (κ)2 が従う.仮定より κ≦κ+アレフ だから,ある μ≦κ と アレフ''≦アレフ が存在して κ=μ+アレフ'' と書ける.このとき アレフ''≦κ だから κアレフ''≦(κ)2≦κ+アレフ である.命題8により κアレフ または アレフ''≦κ が分かる.

アレフ''≦κ と仮定すると κ=μ+アレフ''≦κ+κ=κ となり κ < κ (命題14)に矛盾する.従って κアレフ である.よって κ < κアレフ であり, κ がアレフだから κ=2κ となる.

コメント

(名無し) | 2013年6月26日 07:12

悩める門外漢に教えてください
(よく出会うアマチュア質問とは思いますがお願いします):
N: 自然数
N1: 各数の先頭に”0. “をつけて得る集合。(自然数には最高桁が見える、が前提)
N2:  N1の要素に”3”を無限につけて得る数のうち異なるものだけの集合。
注 Nの328と3283 はN1では0.328と0.3283 になります。N2を作る際、両数はともに0.328333333….. と0.328333333… になるので一つになります。つまりN2はNよりはるかに小さい集合になります。
命題は:N2は可算か?
自明に可算と思えます。では並べて見せてください:(中略)対角線論法で列挙されなかった数が生成できました。(それは終わり?の方は3でない数が続く特殊数です。)
それがN2に入っていたらN2はNより大きい、となるので嘘でしょう。
つまり、対角線論法が生成する数はN2に入っていません。
なぜそう言える?
私が思いつく答えらしい答えは、「自然数は有限最高桁を持つから。。。」でしょう。すると、更に疑問がわきます:ならば、Nは有限集合なのか?Nは最高桁数の上限MをパラメータとしてN(M)と表され、Mが有限のときは有限である集合なのか?Mを段々大きくして無限に持って行く可能無限集合の世界なのか?カントールのお話しは「実無限と可能無限の比較話だったのか」「無限集合(実数集合)は有限集合より大きい」と言うアホ話だったのか?
N2にあたる集合を持ってきてカントールの意義の説明は読んだことがありますが、それらは「自然数は最高桁があるから」でした。Nは有限集合と言うなら、私は更に納得できない!!!
もし、「自然数には最高桁があるが、見ることはできない」ならば、自然数を鏡像反転し、後には3を無限個つける、というアルゴリズムで定義することもできます。328 → 0.8233333….
ここら辺で何か、お助けマン公理が登場のようにも思いますが教えてください。

管理人 | 2013年6月26日 22:03

対角線論法で(具体的に)どうやって数を生成したのか分かりませんが、その数xはある桁から先に無限個3が並ぶ数なのですか? もしそうでないならば、N2の定義からxはN2に含まれません。

迷える狼 | 2013年6月27日 08:07

前回は、試し、とばかりスイッチを押したので名無しになりました。失礼。迷える狼

前回質問は、
1) 自然数集合Nは、最高桁Mを引数とするN(M)と表せる有限集合か?
2) 小数が、小数点M桁以降から異なるとき、両数は異なる、と言えるか?Mが有限なら当然ですが、Mは無限です。


今回の質問は「背理法の適用について」です。背理法は、YES,NO回答をもつ命題を決め、YES者とNO者を想定し、相手の矛盾を上げつらい勝者を決める方法です。今の場合「(0,1)全実数Rの全要素をNに沿って並べ得るか?」です。
知られている論は「NO者がYES者に向かって、YESと言うなら見せてください」から始まります。公平な審判は疑問を持ちます:
1.「ある」なら見せ得るものか?見せる義務はあるのか?
2.N者先攻は不公平ではないか?
3.Nはアルゴリズム定義(KがあればK+1もある)ですが、Rの方は列挙定義しかありません。これは異なる集合の比較ではないか?
です。背理法は例外なく「NOと言う方が有利」ですが、有限問題ならその差は問題ない、ことは明らかです。以下の例は以上の疑問を踏まえています。

YES者は以下のようにアルゴリズムで提示します:最初に任意の数aを挙げます。 次にこれから対角線論法(以下D論と呼ぶ)で得られるすべての数を並べます。(例えば小さい順に。)一般にk個まで得たら、それら全部からD法で生成される異なる数全部を並べます。このように生成される順序つき実数系列をR(a)とします。これをNO者に見せるのです。
NO者は、それでは見えないよ、と言うかもしれません。しかし、アルゴリズムはNO者が使うであろうD法を使って記述しているのです。自縄自縛です。じゃんけんで相手に「先に良く見えるように見せろ」と言えばジャイアンです。

更に言えば、我々はアルゴリズムで定義されていない集合(今の場合実数)をa, b, ……..と表記してわかったような気がします。これにD法を適用する、などと軽く言います。しかし、上に定義したR(a) では、aの後に無限個が並びます。1個でも増えるたびに無限個の数が並びます。したがって無理に書くとすれば
a ……  b….  c  ….. のように 無限部分「…..」が分散して現れます。このような表現数列にD法をどのように適用するのでしょうか?D法の記述では、bは何桁目、とか指定することが必要でしょう。bはすでに無限番の後です。これはつまり、NO者にはこの表現の解析能力がない、と思われます。

NO者は言うかもしれません:反論を見て作り直している。後出しでずるい。
ではYES者も、並べてみせるから実数を見せて下さい、とNO者に求める権利があります。NO者は(できないと言うその主張から)当然できません。でも並べてみよ、と言う限りその義務が発生します。問題自身を提示できない、ので戦わずしてYES者の勝ち(=Nから実数Rへの全単射が存在する)と言えるでしょう。
これは一休の屏風の虎退治と同じ話です。虎を追い出せば退治してみせる、と言う一休は正論だ、が一般人の了解です。

長く書きましたが、内容は前回と同じルーツです:自然数集合は実数集合とは、写像などは考えてはいけない異質のものではないか。
あるいは:無限集合については、その要素のどれとも異なるものがその要素であることもある、と言う命題が成り立つ世界はどの公理にも反しない、のではないか?(既存の集合定義とには矛盾することはわかりますが。)

著者は公理系の権威とお見受けしますので教えてください。

迷う狼 | 2013年6月27日 08:14

今見ました。ありがとうございます。

その数xがN2に属さない理由を話題にしています。「ある桁」に言及しなければ説明できないではないかと。

自然数集合は「ある桁」が引数なのですか?そうであれば、そのことを初めから言ってもらえば、実数への全単射がない、ということはカントールを要しません。この理解困難で発生する数学嫌いは無くなるでしょう。

迷う狼 | 2013年6月27日 18:57

繰り返しで申し訳ありません。今回の質問テーマは、自然数集合だってべき集合だ、です。

悩める狼は「カントールの定理」に疑いを抱いているのではありません。逆に、これを適用していない、と言いたいのです。
対角線論法が「各桁で異なる数を採用せよ」と言うからべき集合を考えていることが明らかになり、定理の右辺を想います。しかし自然数集合だってべき集合です。100桁までの自然数はべき集合10の100乗 の要素です。だからこれもカントール命題の右辺です。左辺はいつ登場するのでしょう?

もう少し書くならば:実数の小数点以下100桁まで自由値で、以降はすべて3 とする小数全体は、100桁自然数=べき集合10の100乗と同じ規模です。この事実を N(100)=R(100)と書きましょう。一般には、自然数のM桁、実数の小数点以下P桁を考えるとして、N(M) とR(P) 大小比較問題になります。M>Pなら自然数の方が実数より多い、ことすら発生します。この意味での自然数と実数とのどっちが多いかはNとPの大小と同じです。
カントールによる「自然数より実数が多いことの証明」はカントールの命題を使ってはいなくて、暗黙の桁数仮定「M<P」の自明な帰結です。ひどくは、Mは有限とする著者もいます。何故こんなことが許される?

管理人 | 2013年6月28日 00:20

正直何いってんのか分からないのですが。

>その数xがN2に属さない理由を話題にしています。「ある桁」に言及しなければ説明できないではないかと。
「ある桁」に言及する必要はありません。何故ならばそんなもの存在しないからです。今証明すべきことは「その数xはある桁から先に無限個3が並ぶ数」でない、ということです。

迷える素人 | 2013年6月30日 08:35

先には文字化けに気づかず失礼しました。

考え方の説明は伝わらないものである、ですので、具体的な実数列挙アルゴリズムを提案します。どうでしょう?

嘘!に決まっている、と思わないで、どこから誤りか教えて頂きたいのですが。


提案:対角線論法で新数を生成できない実数の並べ方

任意の一つの実数をa1 とする。

a1=0.862848585....

対角線論法(以下D法と呼ぶ)を、k個の実数並びから一つの数を生成する規則と考える。
対角がないときにはそれ以前の数と同じ並びとする。(厳密ルールは以下の例からわかるでしょう。)それをa2とする。

a2=0.962848585....

しかし、多進数表示では、D法による生成が一意でないので、議論の簡明さのために2進表示を使います。あらためて例を作ります。

a1=0.1100100.......

これからD法で生成される数をa2として並べる。

a2=0.0100100.......


a1, a2からD法で得る数をa3とする。


a3=0.0000100.......


以下同様にa1, a2, .., ak からD法で得る数をak+1とする。

以下のような表ができる。

a1 : 0.1100100.......
a2 : 0.0100100.......
a3 : 0.0000100.......
a4 : 0.0010100.......
a5 : 0.0011100.......
a6 : 0.0011000.......
a7 : 0.0011010
::::::::


定理1:実数の並び R(a1) から対角線論法は R(a1) に属さない数は生み出せない。
理由:定義から。

定理2:R(a1)と自然数は同じ濃度である。
理由:自然数は kからk+1を一意に生成する。
R(a1)は、1からkまでからk+1を一意に生成する。

考察1:この表右辺数字部分をマトリクスと考える。
ここでは、マトリクスの(1,1)から下への対角線で考えた。しかし、任意の列
(1,k)から始めれば(たぶん)異なる数が生成される。それら全部をR(1,p)と書く。

するとD法を拡大解釈すると、R(1,1) R(1,2) R(1,3) ....を生成するとみなすこともできる。
しかしこれら全部合わせて一列に列挙して考えることができる。

考察2:R(a1)は実数の、無限集合とは言え、ほんの一部です。真部分集合であることの証明も簡単です。だからこれだけでは全部を挙げてはいない、と言えます。しかしそれは今の主旨、対角線論法はどんな並びからでも新数を列挙するは否定される、とは関係ない話です。

(名無し) | 2014年10月 8日 02:50

>>迷える素人さん

1年以上前のポストに対するレスになり申し訳ないのですが…

あなたのおっしゃるR(a1)と言うのは、a1,a2,...を並べた表のことですか?

ならば、「定理1:実数の並び R(a1) から対角線論法は R(a1) に属さない数は生み出せない。」は誤っています。

よく見ると分かるように、自然数kに対して、この表(R(a1))の中の実数akは、a1の小数第(k-1)位までの0と1を反転させて、第k位以降はa1と同じ、という実数になっています。
したがって、この表に属する任意の実数は、十分先の桁では(akなら第k位以降)、a1と同じになっています。

対角線論法で得られる数と言うのは、(私の理解が正しければ、)「すべての自然数kに対して」、小数第k位がakの小数第k位と異なる数、のことです。
この表に対角線論法を適用した場合、得られる実数は、a1の「すべての桁」を反転させた数です(この実数をbと呼ぶことにします)。

先ほど述べたように、表の中の任意の実数akは、第k位以降はa1と同じですから、bとは異なります(bは第k位もa1とことなる)。
ですから対角線論法は表に属さない数を生み出しています。

(名無し) | 2017年7月20日 09:28

I don't fully understand Japanese, but it seems that for proposition 5 you only proved 2^κ+κ=2^κ; I believe that to prove 2^κ-κ=2^κ, you need to show that for any μ satisfying μ+κ=2^κ, we have μ=2^κ.

コメントする

感想、意見、質問など何でもどうぞ。
※書き込んだのに表示されない場合は、ページをリロードしてみてください。