第１５回 濃度の積

第１５回　濃度の積

 

§１　濃度の積の定義

 

集合の元の個数がそれぞれm、nである２つの有限集合A、Bがあるとする。このとき、AとBの直積A×Bの元の個数はmnである。また、有限集合の場合、集合の元の個数と濃度は一致する。したがって、AとBの濃度を｜A｜、｜B｜で表すと、｜A｜=m、｜B｜=nであり、A、Bの直積A×Bの濃度｜A×B｜=mn。

そこで、一般の濃度の積を次のように定義することにする。

 

定義

α、βを２つの濃度とする。このとき、｜A｜=α、｜B｜=βである任意の集合A、Bをとり、その直積A×Bの濃度をαとβとの積といい、

　　

 

この定義が意味を持つためには、｜A｜=｜A'｜=α、｜B｜=｜B'｜=βのとき、常に、

　　

が成り立つ必要がある。

このことは、次のことから確かめられる。

であるから、AからA'への全単射（１対１対応）f、BからB'への全単射gが存在する。A×BからA'×B'への次の関数hを考える。

　　

すると、hは全単射。よって、｜A×B｜=｜A'×B'｜である。

 

定理　濃度の積については、次のことが成り立つ。

【証明】

（１）　｜A｜=α、｜B｜=βであるA、Bをとると、αβ=｜A×B｜、βα=｜B×A｜。

A×Bの元(a,b)とB×Aの元(b,a)を対応させると、これは全単射。

よって、

　　

 

（２）　｜A｜=α、｜B｜=β、｜C｜=γとすると、

　　

 

（３）　｜A｜=α、｜B｜=β、｜C｜=γ、B∩C=∅である、A、B、Cをとると、

　　

また、だから、

　　

よって、

　　

 

（４）　｜A'｜=α'、｜B｜=βであるA'、Bをとれば、α≦α'よりA⊂A'で｜A｜=αであるAが存在する。

よって、

　　

ゆえに、

　　

（証明終）

 

例１　任意の濃度αに対して

　　

｜A｜=0、｜B｜=αとすると、A=∅。したがって、A×B=∅。

よって、0α=α0=0である。

 

例２　任意の濃度αに対して

　　

 

例３

　　

とおくと、。

そこで、A×Bの元

　　

に対して

　　

の矢印の順番に番号を付けてゆけばA×Bは可算集合になる。

したがって、

　　

 

例４

　　

A、Bを開区間(0,1)とすると、。

(a,b)∈A×Bとすると、a∈A=(0,1)、b∈B=(0,1)はともに

　　

と無限小数の形に展開できる。

そこで、(a,b)をに対応させる写像fを考えると、A×Bは実数全体の集合Rの部分集合と対等。

ゆえに

　　

また、

　　

したがって、

　　

 

§２　和と積の関係

 

２つの有限濃度mとnとの積mnはnを加えたものである。

すなわち、

　　

これは次のように言い換えることができる。

集合｛1, 2, 3, ・・・, m｝を添字の集合とする濃度系がiにかかわらず、を満足すれば、

　　

である。

 

このことは、一般の濃度にも成り立つ。

 

定理　α、βを２つの濃度とし、α>0とする。このとき、なる集合Iを添字の集合とする濃度系が、iにかかわらずを満足するならば、その濃度系の和はαβに等しい。

　　

【証明】

Iの各元iにである集合を対応させ、

　　

となるようにすると、

　　

次に、｜B｜＝βである任意の集合Bをとると、Iの任意の元iに対して。したがって、Bからへの１対１の対応が少なくとも１つ存在する。その１つをとおく。ここでI×Bを作り、その元(i,b)にを対応させるようなI×Bからへの対応φ

　　

を考えると、これは全単射。

よって、

　　

（証明終）

 

例１　α=n（自然数）、とおけば、定理は

　　

 

例２　とおけば、定理は

　　

となる。

これより、

　　

 

§３　濃度の積の拡張

 

濃度αと濃度βとの積αβは、｜A｜=α、｜B｜=βなる集合、AとBの直積A×Bの濃度であった。いま、このAとBとの和集合A∪Bを作り、集合｛1,2｝からA∪Bへの関数fのうちで、それによる1の像f₁がAに属し、f₂がBに属すものの全体Cを考えると、

　　

になる。

一般に、濃度α₁、α₂に対し、なる集合A₁、A₂を選び｛1,2｝からA₁∪A₂へのなる関数fの全体を作れば、その濃度はα₁α₂に等しい。

同様に、濃度に対して、である集合をとり、｛1,2,・・・,n｝からへのである関数fの全体の集合を作れば、その濃度はに等しいことが示される。

このことは次のように言い換えることができる。

集合｛1,2,・・・,n｝を添字の集合とする濃度系に対して、同じく｛1,2,・・・,n｝を添字の集合とするの集合系のうちで、任意のiに対してであるものを考える。このとき、から｛1,2,・・・,n｝からへの関数fで、どのiについてもとなるようなものの全体の集合を作れば、その濃度はに等しい。

一般に、Iを添字の集合とする集合系が与えられたとき、Iからへの関数fのうちで、i∈Iならばとなるようなものの全体を、集合系の直積といい、

　　

と書く。

特に、I=｛1,2,・・・,n｝あるいはI=｛1,2,・・・,n,・・・｝の時は、

　　

などと書く。

 

定義

濃度系が与えられたとき、Iの任意のiに対して、となるような集合系を考える。その直積の濃度を、濃度系の積といい、と書く。

　　

 

第２０回 順序型

第２０回　順序型

 

を順序集合とする。全単射が存在し、fおよびf⁻¹がともに順序を保つ写像であるとき、ととは順序同型といい、

　　

であらわし、fを順序同型写像という。

 

濃度の場合と同様に、順序集合全体のクラスをによって類別し、各同値類にラベルをつけることができる。順序集合（A,≦）に付けられたラベルを順序型といい、記号や単になどで表す。

すると、

　　

が成り立つ。

 

有限濃度nをもつ集合A、Bにそれぞれの順序を与えて、順序集合を作ると、これらはつねに順序同型である。

何故ならば、A、Bの元は

　　

と並べることができる。

　　

とするとφは順序同型写像である。

したがって

　　

これより、有限濃度nの集合から得られる順序集合の順序型はただ１つしか存在しない。

一般に、濃度αの任意の集合Aから作られる任意の順序集合（A,≦）の順序型をα−順序型というが、上で述べたことより、n−順序型は１つしかない。

しかし、αが無限濃度の場合、α−順序型は１つとは限らない。

たとえば、

　　

は同型ではないから、とは、相異なる−型順序である。

自然数全体の集合Nの順序型をω、整数全体の集合Q、有理数全体の集合Qと実数全体の集合Rの順序型をそれぞれγ、η、λで表すことがある。

 

問１　A〜Bかつならば、となるようなB上の順序があることを示せ。

【解】

A〜Bだから、BからAへの全単射（１対１対応）φが存在する。

Bの任意の元x、yに対してのときとおくと、はB上の順序で、φはからへの順序同型写像となる。

よって、

　　

である。

（解答終）

 

問２　であってもとなることがある。そのような例を１つあげよ。

【解】

　　

とすると、

　　

しかし、

　　

（解答終）

 

 

第１９回 選択公理と整列可能定理

第１９回　選択公理と整列可能定理

 

§１　選択公理

 

Λを添字の集合とする集合系が与えられたとき、Λからへの関数fのうちで、Λのどの元λに対して

　　

となるようなものの全体を集合系の直積といい、

　　

で表し、各を直積因子という。

特に、とすれば、集合系の直積は、であるような組全体となり、これまでの直積の定義、つまり、

　　

と一致する。

Nを自然数全体の集合とし、Λ=Nのとき、

　　

で表すことがある。

 

集合系においてとなるものが少なくとも１つあるとき、その直積になる。この裏にあたる命題

Λ≠∅、かつ、すべてのλ∈Λに対して、

　　

が成り立つ

を選択公理という。

このとき、直積の元を集合系の選択関数という。

 

直積において、すべてのが同一の集合Aであるとき、をで表す。また、は、ΛからAへの写像全体の集合に一致する。

 

Aを任意の空でない集合とする。とおくと、X∈ΛならばX≠∅だから、選択公理により、Λによって定まる集合系の直積は空でない。いま、この元を１つとって、それをfとすれば、fはからAへの写像であり、すべてのに対してf(X)=Xとなる。このようなfをAの上の選択関数という。

 

先に、任意の無限集合Aは可算な部分集合をもつことを示した。

その際、Aから元a₁を選び、次にA−｛a₁｝から元a₂を選び、さらにA−｛a₁,a₂｝から元a₃を選び、以下の操作を繰り返すことによって可算集合を得たのだが、実は、この証明において、選択公理を暗黙のうちに使用している。

このことが明確になるように示すと次のようになる。

 

定理　任意の無限集合は可算部分集合をもつ。

【証明】

集合Aが無限集合であるとし、fを集合Aの上の１つの選択関数とする。

まず、とおく。次に、とおく。

同様に、一般に

　　

とおく。

すると、はAの可算部分集合である。

（証明終）

 

定理（濃度の大小）

A,Bを集合とする。AからBへの全射が存在すれば、｜B｜≦｜A｜である。

【証明】

を全射とする。

b∈Bに対して、

　　

とおくと、fは全射であるので、である。

よって、選択公理より、

　　

は空でない。

をその元とすれば、fが写像であることより、は単射。

したがって、

　　

（証明終）

 

§２　整列可能定理

 

空でない任意の集合Aに順序を定め、整列集合にできるか、という問題がある。

選択公理を仮定すると、この問いに肯定的に答えることができる。しかし、この証明は難しいので、ここでは整列可能定理のみを紹介し、整列可能定理から選択公理を証明することにする。

 

整列可能定理

任意の集合は、その上にある順序を定義して整列集合にすることができる。

 

問題　整列可能定理を用いて、選択公理を証明せよ。

【証明】

をであるような集合系とする。

　　

とし、整列可能定理によりAを整列する。この整列順序に関するの最小元をとすれば、はの元である。

よって、

　　

（証明終）

 

また、整列可能定理を用い、次の定理を証明することもできる。

 

定理　（濃度の比較定理）

α、βを任意の濃度とすると、

のうちの１つだけが成立する。

【証明】

｜A｜=α、｜B｜=βである集合A、Bをとり、整列可能定理により、A、Bのそれぞれの上に整列順序を与えることができる。

すると、

　

のうちのいずれか１つだけが成立する。

ゆえに、

（１）の場合は｜A｜=｜B｜、（２）の場合は、（３）の場合は。

すなわち、α=βまたはα≦βまたはα≧β。

したがって、α<β、α=β、β>αのいずれか１つが成立する。

（証明終）

 

§３　Zornの補題

 

Aを空でない順序集合とする。Aの任意の空でない全順序部分集合Xに対して上限が存在するとき、Aを帰納的な順序集合という。

 

Zornの補題

Aが帰納的な順序集合ならば、Aは極大元を持つ。

 

証明はしないが、次のことが知られている。

 

定理

次の（１）〜（３）は同値である。

（１）　選択公理

（２）　Zornの補題

（３）　整列可能定理

 

集合論の教科書などでは、選択公理→Zornの補題→整列可能定理の順に証明し、そして、整列可能定理から選択公理を証明し、選択公理、Zornの補題、整列可能定理の３つが同値であることが示されるのが一般的であるが、選択公理から整列可能定理を直接証明することもできる。

そして、この３つは同値なので、どれを出発点、つまり、公理に採用して、理論を展開してもよいのであった。

 

第１８回 整列集合

第１８回　整列集合

 

（半）順序集合（A,≦）は、Aの部分集合がかならず最小元（最初の元）をもつとき、整列集合という。また、整列集合は全順序集合である。

整列集合の部分集合および整列集合と順序同型な順序集合は整列集合である。

 

例１　自然数全体の集合をNとするとき、

　　

は整列集合である。

 

例２　有限順序集合は整列集合である。

 

例３　通常の順序（大小関係）において、整数全体の集合Z、有理数全体の集合Q、実数全体の集合Rは、最小元（最初の元）を持たないので、整列集合ではない。

 

例４　は整列集合である。

 

問１　整列集合は全順序集合であることを示せ。

【証明】

（A,≦）を整列集合とし、x、y∈Aとする。X={x,y}はAの空でない部分集合だから、Xは最小元min Xをもつ。

min X=xならばx≦yであり、min X=yならばy≦x。

したがって、任意のx、y∈Aに対して、x≦yまたはy≦xが成り立つ。よって、整列集合は全順序集合である。

（証明終）

 

定理１

（A,≦）が整列集合であり、が順序単射であれば、すべてのx∈Aに対して、

　　

である。

【証明】

が空（集合）でないと仮定する。

Xの最小元をx₀とすると、f(x₀)<x₀であり、fは順序を保つ単射だから

　　

したがって、f(x₀)∈Xであって、f(x₀)はXの最小元x₀よりも小さいので、矛盾が生じる。

したがって、Xは空集合∅である。

（証明終）

 

整列集合（A,≦）の元aに対して、集合｛x∈A｜x<a｝をAの元aによる切片といい、記号A〈a〉などであらわす。

 

例５　とするとき、

 

問２　（A,≦）を整列集合とする。Aの２つの元a、bについてb<aならば、

　　(A〈a〉)〈b〉=A〈b〉

であることを示せ。

【解】

　　(A〈a〉)〈b〉=｛x∈A｜x<aかつx<b｝

問題の条件よりb<aだから、

　　(A〈a〉)〈b〉=｛x∈A｜x<aかつx<b｝=｛x∈A｜x<b｝=A〈b〉

（解答終）

 

 

問３　Aでa∈Aならば、AからA〈a〉への順序単射は存在しないことを示せ。

【証明】

を順序単射とすると、fはAからAへの順序単射だからa≦f(a)でなければならない。

一方、f(a)∈A〈a〉だからf(a)<aとなり矛盾する。

したがって、AからA〈a〉への順序単射は存在しない。

（証明終）

 

問４　次のことを示せ。

（１）　整列集合Aから自分自身への順序同型写像はに限る。

（２）　整列集合Aから順序集合Bへの順序同型写像が存在すれば１つに限る。

（３）　Aが整列集合であって、a、b∈Aであるとき、ならばa=bである。

【証明】

（１）　を順序同型写像とすると、fはAからAへの順序単射だから、x≦f(x)。また、f⁻¹も順序単射だから、x≦f⁻¹(x)となり、f(x)≦x。したがって、f(x)=x。

 

（２）　f、gがともにAからBへの順序同型写像ならばはAからAへの順序同型写像。（１）よりとなり、g=fである。

 

（３）　a<bと仮定する。

B=A〈b〉とすれば、問２よりB〈a〉=A〈a〉。したがって、ならば、整列集合Bからその切片B〈a〉への順序単射が存在することになるが、問３よりBからB〈a〉への順序単射への順序単射は存在しないので矛盾する。

よって、ならばa=bである。

（証明終）

 

定理２　A、Bを整列集合とすれば、次の３つの場合の１つ、しかも１つだけが成立する。

（１）　AとBは同型

（２）　AはBのある切片と同型

（３）　BはAのある切片と同型

【証明】

A、Bの部分集合A₁、B₁をそれぞれ

　

によって定義する。

各元a∈A₁に対して、となるb∈Bはただ１つ存在し、b∈Y₁。

この元をb=φ(a)とおくと、写像φ：A₁→B₁が定まる。φは順序同型写像であり、となる。よって、A₁はAと一致するか、またはXのある切片と一致し、同様にB₁はBと一致するか、またはBのある切片と一致する。

もし、A₁=A〈a〉かつB₁=B〈b〉とすれば

となり、a∈A₁となる。これはa∉A₁に矛盾する。したがって、この定理が主張する（１）、（２）、（３）のいずれかが必ず成り立つことがわかった。

次に、（１）、（２）、（３）のなかの２つの場合が同時に成立しないことを示す。

（２）と（３）が同時に成り立つと仮定し、順序同型が成り立つと仮定すると、合成写像

は順序を保つ写像であり、φ(a)<aである。これは定理１に矛盾する。したがって、（２）と（３）は同時に成り立つことはない。他の場合についても、同様である。

（証明終）

 

定理３　（超限帰納法）

Aを整列集合とし、P(x)をAの元に関する命題とする。

このとき、

　　

が成り立てば、すべてのx∈Aに関してP(x)が成り立つ。

【証明】

P(x)が満たさないx∈Aがあったとして矛盾を導く。

　　

とすれば、XはAの空でない部分集合となる。Aは整列集合であるから、Xは最小元を持つ。それをaとすると、aより小さい元はXに属さないから

　　

が成り立つ。したがって、仮定よりP(a)となる。すなわち、a∉Xとなる。これはa∈Xであることに矛盾する。

（証明終）

 

自然数全体の集合Nに通常の大小関係を与えた整列集合を（N,≦）とする。よく知られた数学的帰納法は、整列集合（N,≦）に関する超限帰納法にほかならない。

 

 

第１７回 順序集合

第１７回　順序集合

 

§１　順序集合と順序同型

 

集合X上の関係≦が任意のx、y∈Xに対して、次の条件を満たすとき、この関係を順序、または、半順序という。

≦がX上の順序であるとき、(X,≦)を（半）順序集合という。

x≦yかつx≠yであるとき、x<yと書く。

 

(X,≦)、(X',≦')を２つの順序集合とし、fをXからX'への写像とする。任意のx、x'∈Xに対して

　　

が成り立つとき、順序を保つ写像という。

さらに、単射が存在して、fおよびf⁻¹がともに順序を保つ写像であるとき、(X,≦)と(X',≦')とは順序同型であるといい、

　　

で表し、fを順序同型写像という。。

順序同型については、次のことが成り立つ。

　

（ⅰ）は、恒等写像が順序同型写像であることから明らか。

（ⅱ）は、が順序同型写像ならば、が順序同型写像であることによる。

（ⅲ）は、が順序同型写像ならば、が順序同型写像であることにことによる。

 

集合X上の関係≦が（１）〜（３）、さらに次の条件を満たすとき、この順序を全順序という。

　（４）任意のx、y∈Xに対して、x<y、x=y、x>yのいずれか１つが成り立つ

≦がA上の全順序であるとき、順序集合（A,≦）を全順序集合という。

 

自然数全体の集合N、整数全体の集合Z、有理数全体の集合Q、実数全体の集合Rは全順序集合である。

また、全部分集合の部分集合は全部分集合であり、全部分集合と順序同型である順序集合は全部分集合である。

 

自然数全体の集合Nの冪集合において、その元の間にA⊂Bが成立するとき、A≦Bとすれば、

が成立するので、これは上の（半）順序である。

しかし、A=｛1｝、B=｛2}とすると、A⊂B、A=B、A⊃Bのいずれも成立しないので、これは全順序ではない。

 

§２　部分順序集合

（A,≦）を順序集合、BをAの部分集合とする。このとき。Bの元はすべてAの元であるから、Bの元b、b'がAの元としてb≦b'であるとき、b≦'b'とすれば、≦'はBの上の順序になる。

一般に、Aの部分集合Bと、上のように得られる順序≦'とを組み合わせて得られる順序集合（B,≦'）を（A,≦）の部分順序集合という。（B,≦'）が（A,≦）の部分順序集合であることを

　　

と書く。

（B,≦'）⊂（A,≦）である必要十分条件は

　（１）　B⊂A

　（２）　Bの元b、b'に対してb≦'b'ならばb≦b'

 

 

 

 

§２　最大元、最小元、極大元、極小元

 

（A,≦）を順序集合とし、aをAの元とするとするとき、Aの最大元、最小元、極大元、極小元を次のように定義する。

　

Aの最大元、最小元をそれぞれmax A、min Aなどであらわす。最大元、最小元が存在すれば、それらは一意的に定まる。

また、最大元は極大元であるが、この逆は成立しない。最小元、極小元についても同様である。

(X,≦）を順序集合、AをXの部分集合とする。

　　

であるとき、Aは上に有界といい、aをAの上界という。Aの上界の最小のものが存在するとき、それをAの上限といい、記号

　　a=sup A

などであらわす。

同様に、

　　

であるとき、Aは下に有界といい、aをAの下界という。Aの下界の最大のものが存在するとき、それをAの下限といい、記号

a=inf A

などであらわす。

また、Aが上に下に有界であるとき、Aを有界であるという。

 

問　次のことを示せ。

（１）　自然数全体の集合Nと整数全体の集合Zは順序同型でない

（２）　整数全体の集合Zと有理数の全体の集合Qは順序同型でない

（３）　有理数全体の集合Qと実数全体の集合Rは順序同型でない

【解】

（１）　Nは最小元１をもつが、Zは最小限をもたないから

（２）　Qは稠密であるが、Zは稠密でないから。

QからZへの順序同型写像φがあるとし、1と2の原像をそれぞれa、b∈Qとすると、

　　

よって、

　　

であるが1と2の間に存在することになるが、整数全体の集合Zにそのような元は存在しない。

これは矛盾。したがって、ZとQは順序同型でない。

 

（３）　Qは可算集合、Rは非可算集合だから

（解答終）

 

 

第１４回 濃度の和

第１４回　濃度の和

 

濃度の定義

α、βを任意の濃度とする。このとき、α=｜A｜、β=｜B｜かつA∩B=∅である集合A、Bをとり、その直和A＋Bの濃度｜A＋B｜をαとβの和といい、記号α＋βで表す。

 

一般に、α=｜A｜、β=｜B｜、A∩B=∅である集合A、Bは無数に存在する。したがって、上の定義が成立するためには、集合A、Bの選び方にかかわらず、｜A＋B｜が変わらない必要がある。選び方によって変わらないことは次のように示すことができる。

α=｜A｜=｜A’｜、β=｜B｜=｜B’｜で、かつ、A∩B=∅、A’∩B’=∅とする。

｜A｜＝｜A’｜、｜B｜＝｜B'｜だから、AからA’、BからB'への全単射f、gが存在する。

　　

とすると、hはA＋BからA’＋B’への全単射になる。

よって、

 

例１　任意の濃度αに対し、

　　

である。

｜A｜=0、α=｜B｜とすると、A=∅で、A∩B=∅。また、A+B=B+A=B。

よって、

　　

 

例２

Aを偶数全体の集合、Bを奇数全体の集合とすると、A∩B=∅で、A+Bは自然数全体の集合。

また、

　　

したがって、

　　

 

例３

　　

とすると、A∩B=∅で、で,

　　

また、

　　

よって、

　　

 

定理　α、β、γ、α’を濃度とすると、次のことが成り立つ。

【証明】

（１）　｜A｜=α、｜B｜=β、A∩B=∅とすると、

　　

したがって、

　　

 

（２）　｜A｜=α、｜B｜=β、｜C｜＝γ、さらに、A∩B=∅、A∩C=∅、B∩C=∅とする。

すると、｜A+B｜=α+βで、また、

　　

したがって、

　　

同様に、

　　

一方、

　　

故に、

　　

 

（３）　｜A’｜=α’、｜B｜=β、A’∩B=∅とし、α≦α’とすれば、｜A｜=αかつA⊂A’であるAが存在し、A∩B=∅。

ゆえに、｜A'+B｜=α’+β、｜A+B｜=α+β。

一方、A+B⊂A’+Bだから

　　

したがって、

　　

（証明終）

 

（１）は濃度の加法の交換法則、（２）は濃度の加法の結合法則。

さらに、（２）から次のように、括弧を省いた書き方が許される。

　　

 

 

例３　任意の無限濃度について

　　

｜A｜=αとすれば、Aは無限集合。無限集合Aは可算集合Bを部分集合にもつ。このとき、

　　

（A-B）∩B=∅だから

　　

よって、

　　

したがって、

　　

 

問１　α、β、α’を濃度とするとき、次のことは成り立つか。

【解】

とすると、α<α'。

例３より

　　

また、例２より

　　

したがって、このとき

　　

ゆえに、

　　

は、一般に成立しない。

（解答終）

 

任意の濃度系に対して、次のような、Iを添字の集合とする集合系を考える。

　　

集合系の和集合の濃度を、濃度系の和といい、

　　

で表す。

 

例４　

 

問２　であることを示せ。

【解】

自然数全体の集合をNとすし、任意のn∈Nに対し

　　

とする。

すると、n≠m∈Nのとき

　　

であり、

　　

したがって、

　　

ここで、

よって、

　　

である。

 

 

第１３回 濃度の大小

第１３回　濃度の大小

 

§１　濃度の大小関係

 

A、Bを有限集合とする。Aの濃度がBより小さいことは、Bの中にAと対等な真部分集合があることに他ならない。

すなわち、

　　

であるB₁が存在するとき、

　　

が成立する。

しかし、無限集合のとき、

　　

は一般に成立しない。

たとえば、Aを自然数全体の集合、Bを偶数全体の集合とするとき、BはAの真部分集合でB〜Bが成立するが、A〜Bで、A、Bの濃度はともに可算濃度であって、

　　

は成り立たないからである。

このように矛盾した事態が発生しないように、濃度の大小関係を次のように定義する。

 

濃度の大小の定義

集合A、Bについて

　　

であるB₁があるならば、｜A｜は｜B｜よりも大きくない、あるいは、｜B｜は｜A｜より小さくないといい、

　　

と記される。

さらに、｜A｜≦｜B｜かつ｜A｜≠｜B｜のとき、｜A｜は｜B｜より小さい、あるいは、｜B｜は｜A｜より大きいといい、

　　

と書く。

 

なお、（２）と「AからBへの単射が存在する」と同じことなので、これを濃度の大小の定義としてもよい。

選択公理を認めると、

BからAの全射が存在するとき

　　

であることが証明できる。

 

 

例　自然数全体の集合Nは、実数全体の集合Rの部分集合であり、かつ、NとRは対等でないので、である。したがって、

　　

また、実数全体の集合RからRへの関数全体の集合Fとすると、Fの中にRと対等な部分集合があり、かつ、RとFは対等でないので、関数の濃度をfで表すと、

　　

である。

 

定理１　｜A｜≦｜B｜、｜B｜≦｜C｜ならば｜A｜≦｜C｜である。

【証明】

｜A｜≦｜B｜、｜B｜≦｜C｜だから

　　

であるB₁、C₁がある。

BからC₁への全単射をf、B₁のfによる像をf(B₁)とすると、

　　

よって、

　　

ゆえに、

　　

（証明終）

 

定理２　（ベルンシュタインの定理）

　　

 

ベルンシュタインの定理の証明は大変なので、ここでは定理だけを紹介する。

 

以上のことをまとめると、次のようになる。

 

 

 

§２　冪集合の濃度（カントールの定理）

 

集合Aの部分集合の全体からなる集合をAの冪集合（べきしゅうごう）といい、記号

で表す。

 

例　A=｛1, 2, 3｝とすると、Aの部分集合は

の８個で、Aの冪集合は

である。

 

有限集合Aの要素の数がn、すなわち、Aの濃度｜A｜=nであるとき、の要素の数はで、その濃度はである。

したがって、有限集合Aの場合、次の関係が成立する。

　　

【証明】

n=0あるいはn=1ならば、0<1=2⁰、1<2=2¹だから、

　　

n=kのとき

　　

が成り立つと仮定する。

n=k+1のとき

　　

数学的帰納法により、

　　

ゆえに、

　　

（証明終）

 

Aが有限集合のとき、Aの濃度はAの冪集合の濃度より小さい。

Aが無限集合の場合も、が成り立つというのが、次のカントールの定理である。

 

定理３　（カントールの定理）

任意の集合Aに対して

　　

【証明】

Aの部分集合のうちで、要素を一つしか含まない集合全体をA₁とすれば、

　　

である。

Aの任意の要素aに｛a｝∈A₁を対応させれば、これはAからA₁への全単射になる。

よって、

　　

次に、であることを示す。

　　

を全単射と仮定し、

　　

とおく。

であるから、f(a)=Xとなるa∈Aが存在する。

しかし、

Xの定義から

　　

となり矛盾が生じる。

よって、Aからの全単射は存在しない。

ゆえに、

　　

（証明終）

 

 

第１２回 同値関係と同値類、商集合

第１２回　同値関係と同値類、商集合

 

§１　二項関係

集合Xについて、直積集合X×Xの各元（a,b）について、満たすか満たさないかが判定できる規則Rが与えられたとき、Rを集合X上の二項関係という。順序対（a,b）が二項関係Rを満たすことをaRbやR(a,b)などで表す。また、直積集合X×Xの部分集合

　　

を二項関係Rのグラフという。

 

X上の二項関係Rについて、次の４つの性質を主に考察する。

 

任意のx、y、z∈Xに対して

 

反射律、対称律、推移律を同時に満足する二項関係を同値関係といい、反射律、推移律、反対称律を満足する二項関係を順序関係という。

 

問１　実数全体の集合をとする。上の二項関係Rを次のように定める。次の二項関係は、反射律、対称律、推移律、反対称律のどれを満足しているか。

【解】

（１）　x≦xだから反射律を満たす。

1≦2のならば2≦1は成立しないので、このとき、対称律を満たさない。

x≦yかつy≦zならばx≦zが成立するので、推移律を満たす。

x≦yかつy≦xならばx=yが成立するので、反対称律を満たす。

よって、上の二項関係Rは、反射律、推移律、反対称律を満たす。

つまり、この関係は順序関係である。

 

（２）　x=yとすると、

よって、反射律を満たす。

xRy、すなわち、(x−y)(x+y−1)=0のとき、

よって、対称律を満たす。

②が成立するのは、y=zまたはy=1−zのとき。

y=zを①に代入すると、

y=1−zを①に代入すると

よって、いずれにせよ、推移律を満たす。

しかし、このとき、2=−1でないので、反対称律は成立しない。

よって、この上の二項関係Rは、反射律、推移律、推移律を満たす。

この関係は同値関係である。

（解答終）

 

問１の関係「≦」は、xとyの大小関係、つまり、順序に関する関係。

何故、反射律、推移律、反対称律を満たす関係を順序関係と呼ぶのか、わかってもらえるのではないだろうか。

 

§２　同値関係

 

RをX上の関係とする。任意のx、y、z∈Xに対して

のすべてが成り立つとき、Rは同値関係にあるという。

 

問２　次の関係が同値関係であることを示せ。

 

ここで、は、それぞれ、整数全体の集合、実数全体の集合をあらわし、fは実数から実数への写像とする。

【解】

（１）　a−a=0はnの倍数なので反射律を満たす。

a−bがnの倍数であるとき、ある整数ｍがあってa−b=nm。したがって、b−a=−nm=n(−m)となり、b−aは５の倍数。よって、対称律を満たす。

cを整数し、a−bが５の倍数、かつ、b−cが５の倍数とすると、

　　

である整数lとmが存在する。

　　

ゆえに、a−bがnの倍数、かつ、b−cがnの倍数ならば、a−cはnの倍数。よって、推移律を満たす。

したがって、この関係は同値関係である。

 

（２）　f(a)=f(a)だから推移律を満たす。f(a)=f(b)ならばf(b)=f(a)なので対称律を満たす。

cを実数とする。f(a)=f(b)かつf(b)=f(c)ならばf(a)=f(c)なので推移律を満たす。

よって、この関係は同値関係である。

（解答終）

 

a∈Xに対して

　　

をaのRによる同値類といい、やなどで表す。また、b∈C(a)を同値類C(a)の代表元と言い、特に、aはC(a)の代表元である。

集合A上の同値関係Rが定義されているとき、任意の元a∈Xの同値類は部分集合である。同値類をすべて集めた集合を、同値関係Rによる商集合といい、記号で表す。

 

定理　RをX上の同値関係とする。このとき、次のことが成り立つ。

 

 

この定理から、同値類は共通部分をもたないか、一致するかのいずれか一方である。したがって、同値類全体の集合はXの直和分割を与える。この分割を同値関係RによるXの類別という。

 

§３　集合の濃度

 

A、B、Cを任意の集合とする。

集合の対等に関しては、次のことが成り立つ。

 

したがって、集合の対等〜は、同値関係。

この同値関係〜による同値類をAの濃度、または、基数と呼び、記号｜A｜で表す。

 

第１１回 非可算集合

第１１回　非可算集合

 

有理数、代数的（実）数のように、自然数よりもはるかに（個）数が多そうな無限集合の濃度も可算濃度であった。したがって、無限集合の濃度はすべてに等しいのではないかと思いたくなる。

しかし、この予想は正しくない。

次に、可算濃度ではない無限集合の実例をあげることにする。

 

（１）　実数全体の集合Rは可算集合ではない

実数の部分集合R₁=｛x∈R｜0<x<1｝とする。

R₁の要素xは、無限小数として、ただ一通りに表せる。

　　

R₁が可算であると仮定すると、その要素は次のように自然数の番号をつけることができる。

　　

ここで、上の表の対角線上の数を元に、

　　

とし、

　　

という実数を作る。

すると、0<b<1となり、b∈R₁である。

したがって、bは、あるに等しくならなければならないが、どのもbと小数点第n位が異なっており、である。

これは矛盾である。

したがって、R₁は可算ではなく、実数全体の集合Rも可算ではない。

 

これが有名なカントールの対角線論法である。

 

問　開区間(0,1)と実数全体の集合Rは対等であることを示せ。

【解】

　　

とすると、fは(0,1)からRへの全単射になる。

したがって、開区間(0,1)と実数全体の集合Rは対等である。

（解答終）

 

実数全体の集合Rの濃度は

　　

と表し、これを連続体の濃度という。

 

（補足）

代数的（実）数以外の実数を超越数という。

 

（２）　関数の濃度

実数全体の集合RからRへの関数全体の集合Fの濃度は、有限でも可算濃度でも連続体の濃度でもない。

【証明】

任意のx∈Rに対して実定数aに対応させる写像（関数）をfₐとおけば

　　

である。

fₐ全体が作るFの部分集合をCとする。

実数aにfₐを対応させれば、これはRからCへの全単射（１対１対応）。したがって、C〜Rである。よって、Fは高々可算集合ではない。

次に、FとRが対等でないことを示す。

RからFへの全単射gがあると仮定する。

すると、Fの任意の要素は、Rのある要素aのgによる像gₐである。

ここで、任意のa∈Rに対して

　　

という関数hを定義すると、h∈Fである。したがって、hはあるに等しい。つまり、任意のx∈Rに対して

　　

となり、

　　

である。

しかし、これは

　　

と矛盾する。

よって、実数全体の集合RからRへの関数全体の集合Fと実数全体の集合Rとは対等ではない。

（証明終）

 

RからRへの関数全体の集合Fの濃度を関数の濃度という。

 

実は、

　　

という関係があるのですが、たとえば、との間に濃度があるのかどうかはわからない。

というか、この間に濃度があると仮定してもよし、無しとしてもよし。

 

定理　全ての無限集合は可算である部分集合をもつ。

【略証】

集合Aが無限集合であれば、

　　

と、順次、要素を取り出すことができ、

　　

とすると、Bは可算集合、かつ、B⊂A。

（略証終）

第１０回 集合の濃度

第１０回　集合の濃度

 

これから述べる集合の濃度の定義は正確なものではなく、集合論でいう濃度がどのようなものであるか、その匂いを嗅ぐためのものことを先にことわっておく。

 

§１　集合の対等と濃度

 

A、Bを２つの集合とするとき、AからBの上への１対１の対応が少なくとも１つ存在するとき、AはBと対等であるといい、

　　

で表す。

 

例１　自然数全体の集合｛1, 2, 3, ・・・｝をA、偶数全体の集合｛2, 4, 6,・・・｝をBとすると、である。

なぜならば、f(n)=2nは、AからBへの全単射（上への１対１の対応）だからである。

 

定理１　A、B、Cを任意の集合とするとき、次の関係が成立する。

【証明】

（１）　Aの要素aにa自身を対応させる恒等写像はAからAへの全単射であるから。

（２）　だからAからBへの全単射fが存在する。そして、この逆写像f⁻¹はBからAへの全単射だから。

（３）　AからBへの全単射をf、BからCへの全単射をgとすれば、その合成写像はAからCへの全単射。

ゆえに、

　　

（証明終）

 

（補足）

２項関係「〜」は、反射律、交換律、推移律が成り立つことを表している。すなわち、２項関係「〜」は同値関係である。

〜をX上の同値関係とすると、Xの要素aと同値なX全体の集合

　　

をaの同値類といい、C(a)などで表す。

b∈C(a)をC(a)の代表元といい、特にaはC(a)の代表元である。

（補足終）

 

定理１より、あらゆる集合は、互いに対等なもの同士のいくつかのグループに分類できる。

このグループに付けられた目印、ラベルを濃度といい、集合Aの濃度を

で表す。

定義から、とは同じことを表す。

 

濃度は、有限集合の要素の個数の、一般の集合への拡張なので、有限集合の濃度には、要素の個数を用いる。

たとえば、集合｛a, b｝の濃度｜{a, b}｜は２であり、集合｛α, β, γ｝の濃度｜｛α, β, γ｝｝は３である。

 

例２　偶数全体の集合Bと自然数全体の集合Aの濃度は等しい。すなわち、｜B｜=｜A｜である。同様に、自然数全体の集合Aの濃度と奇数全体の集合Cの濃度も等しく｜A｜=｜B｜。したがって、偶数全体の集合の濃度｜B｜と奇数全体の集合の濃度｜C｜は等しい。

 

§２　可算集合

 

有限集合の濃度を有限濃度、これに対し無限集合の濃度を無限濃度という。

無限集合のうちでもっとも簡単な自然数全体の集合Nの濃度を記号

で表し、「アレフ・ゼロ」などと読む。

濃度の定義（と定理１）から、自然数全体の集合Nと対等な集合の濃度はすべてに等しく、逆にの濃度をもつ集合はNと対等である。Nと対等な、つまり、の濃度をもつ集合を可算集合（可付番集合）という。

 

Aを自然数全体の集合Nと対等な集合とすると、NからAへの全単射（１対１の対応）aが存在する。

自然数nの写像aによる像をで表わせば、

　　

と、集合Aのすべての要素に自然数の番号を付けることが可能（可付番）になる。

 

可算集合の例

 

（１）　整数全体の集合

整数全体の集合Zの要素を

と並べ、最初から順にとおけば、Zの要素全体に自然数の番号を付けて並べることができる。したがって、整数全体の集合Zは可算である。

 

（２）　有理数全体の集合

まず、正の有理数について考える。

1→2→1/2→3→2/2→1/3→・・・の順に進み、とおく。

ただし、途中ですでに出てきた数（たとえば、）は飛ばして進むことにする。そうすれば、正の有理数全体に番号が付けられ、次のように一列に並べることができる。

したがって、有理数全体の集合Qは

と並べられる。

こうして得られた数の列に、左から順に

とおけば、有理数全体に自然数の番号を付けて並べることができる。

したがって、有理数全体の集合Qは可算集合である。

 

（３）　代数的数全体の集合

整数を係数とする代数方程式

の解になるような実数を代数的実数または代数的数という。

任意の有理数は方程式px−q=0の解だから、有理数はすべて代数的数である。

なども、それぞれ、の解だから、なども代数的数である。

このような代数的数全体の集合も可付番集合であることが知られている。

 

有限集合と可算集合をあわせて高々可算な集合という。

 

問１　A、Bがともに高々可算集合ならば、A∪Bは高々可算集合であることを示せ。

【解】

A、Bが有限集合ならば、A∪Bが可算集合であることは明らか。

Aが有限集合、Bが可算集合のとき、

　　

と並べて先頭から番号をつければよい。

Aが可算集合、Bが有限のときも同様。

Aが可算、、Bが可算集合、のとき、

　　

と並べ先頭から番号をつければよい。

よって、

A、Bがともに高々可算集合ならば、A∪Bは高々可算集合である。

（解答終）

 

問２　有限集合の列の和集合は、高々可算であることを示せ。