2004/05/11の問題の解答

問題
(1)集合D={1,2,3}とするとき、Dのべき集合P(D)を具体的に示しなさい。
(2)補題3の証明では、AからP(A)への全単射写像が存在すると仮定して証明したが、
これをP(A)からAへの全単射写像が存在すると仮定して証明しなさい。

[証明]

(1) P(D)={
{1},{1,2},{1,3},{1,2,3},
{2},{2,3},{3},φ}

(2) P(A)からAへの全単射写像fがあるとする。
fは全射であるので、Aの任意の元xに対して、P(A)のある元が対応している。
また、fは単射な写像なので、xに対して、Aの元が1つしかない部分集合がただ一つ対応する。
すると、P(A)の元φに対して、Aのある元に対応しているのだから、
これは、fが単射であることに矛盾する。
よって、P(A)からAへの全単射写像は存在しないことが示された。
したがって、P(A)とAの間に全単射写像は存在しない。

これは

考えてみると、自分では気が付かなかったがこれは思っていた以上にいい方法かもしれない。問題はあとひとつか。。。[end]

集合族とは?

「集合族」とは、集合を元に持つ集合のことである。
以下に例を示す。

(ex1)集合Bを分類された植物の集合を元とする集合とする。

B := { D | Dは分類された植物の集合:例えば稲とか杉とか }

集合Cを桜の集合とする。
桜は植物で、かつ桜と分類されているので、CはBの元である。

(ex2)自然数の集合Nに対して、Nの部分集合からなる集合P(N)は、

P(N) := { M | M⊂N }

と定義される。

集合{1,2}を例にとれば、1も2も自然数であるので、集合{1,2}はNの部分集合である。
したがって、集合{1,2}は、P(N)の元である。


上の(ex2)の場合のように、ある集合の部分集合からなる集合を、「べき集合(power set)」という。
集合Aのべき集合は、

P(A) あるいは 2^P (2^Pの記述は、指数と同じ)

と書かれる。ここでは、P(A)を採用する。


補題1:Aのべき集合P(A)の濃度card(P(A))は、2^(card(A))である。

[証明]
数学的帰納法を用いる。Aを任意の集合とする

(i)card(A)=0のとき、Aは元がないということだから、Aは空集合である。
したがって、P(A)={φ}である。よって、card(P(A))=1=2^0より成立する。

(ii)card(A)=nのとき、card(P(A))=2^nであるとする。
このとき、AにAの元でない元xを1つ加えた集合をBとする。つまり、card(B)=n+1となる。
Bの任意の部分集合Cは、Cがxを含む部分集合であるか、Cがxを含まないAの部分集合であるかのどちらかなので、

card(P(B)) = 2*card(P(A)) = 2*2^n = 2^(n+1) = 2^(card(B))

となる。よって、(i),(ii)より、証明された。□


補題2:集合Aとする。P(A)をAのべき集合とする。
このとき、AとP(A)の間に全単射写像は存在しない。

[証明]
背理法を用いて矛盾を導く。
全単射写像f:A→P(A)が存在したとする。
Aの任意の部分集合Bについて、B∈P(A)である。
fは全単射であるから、あるx∈Aがただ一つ存在して,f(x)=Bとなる。
このとき、f(x)∋xであるか、f(x)がxを元に持たないかのどちらかであるので場合分けして考える。

(i)x∈f(x)であるとすると、x∈Bである。
ところで、Aの任意の元を1つだけ元に持つ集合もAの元である。
この1つしか元を持たない集合に対して、fは全単射であるから、
Aの何かの元がただ一つ対応する。仮定から、この元を1つだけ持つ集合は、その元を含むのだから、
{x}というAの部分集合に対して、xが対応することになる。
空集合φを考えると、これもAの部分集合であるが、
Aのどの元xをとってきても、{x}が対応しているので、φに対応するAの元が存在すると、
fが写像であることに矛盾する。

(ii)f(x)がxを元に持たないとすると、{x}という部分集合に対して、
fは全単射であるから、x≠zととなるz∈Aがただ一つ存在して、f(z)={x}となる。
したがって、元が1つだけの集合に対して、Aのある元が対応している。
すると、fは全射なのでφに対応するAの元aが存在するとすると、
aはある1つしか元がない集合に対応しているので、fが写像であることに矛盾する。

(i)(ii)から、全単射写像f:A→P(A)は存在しないことが示された。
したがって、AとP(A)の間に全単射写像は存在しない。□


補題3:空集合でない集合A,Bに対して、
AからBへの全単射写像が存在するならば、BからAへの全単射写像が存在する

[証明]
仮定から、写像f:A→Bが全単射であるとする。
fは全射であるから、Bの任意の元bに対して、Aのある元aが対応する。
さらにfは単射であるから、bに対応する元aはただ一つである。
よって、g(b)=aとすれば、gはBからAへの写像で、単射でありかつ全射である。
したがって、BからAへの全単射写像が存在する。□

補題3の対偶を取れば、BからAへの全単射写像が存在しないならば、
AからBへの全単射写像は存在しないということになる。

また、補題3において、gはfの「逆写像(ぎゃくしゃぞう,inverse)」あるいは「逆」という。
gは、しばしばf^(-1)と書かれる。

補題3から

系4: fが全単射であることの必要十分条件は、fの逆写像が存在する

が示される。

[問題]
(1)集合D={1,2,3}とするとき、Dのべき集合P(D)を具体的に示しなさい。
(2)補題3の証明では、AからP(A)への全単射写像が存在すると仮定して証明したが、
これをP(A)からAへの全単射写像が存在すると仮定して証明しなさい。

無理

また書き込んだ先で荒れるかもしれないと思うと、恐くてコメントできない。。。
話し合いができる状態などというものは無い。。。

前回の問題の証明

集合A,B,Cについて、

(1) A∪B⊃A, A∪B⊃B
(2) A∩B⊂A, A∩B⊂B
(3) (A∩B)∪C = (A∪C)∩(B∪C)
(4) (A∪B)∩C = (A∩C)∪(B∩C)

を証明せよ。

[証明]

(1) Aの任意の元aについて、a∈A∪Bであるので、A∪B⊃Aである。
A∪B⊃Bも同様。

(2) A∩Bの任意の元aについて、a∈A かつ a∈Bより、
A∩B⊂Aであり、A∩B⊂Bである。

(3) a∈(A∩B)∪C
⇔ a∈A∩B or a∈C
⇔ (a∈A and a∈B) or a∈C
⇔ (a∈A or a∈C) and (a∈B or a∈C)
⇔ (a∈A∪C) and (a∈B∪C)
⇔ a∈(A∪C)∩(B∪C)

(4) (3)と同様

熱

ふらふらする。風邪を引いて、昨日悪化。一日寝込んだ。

てすと

てすと