集合の問題お願いします

質問

Aが有限集合ならば、その真部分集合への単射は存在しない。
これを数学的帰納法で証明せよ。

回答No.1

tmppassenger · ベストアンサー

先ず、自然数の公理を満たす集合Nを取ってきた時（0∈Nとする）、n∈Nに対してある集合Aが「n元集合」であるとは、{j∈N|j<N}とAとに一対一対応が存在する事をいい、あるm∈Nが存在して集合Bがm元集合となるとき、Bは「有限集合」である、という、という定義をここでは採用しておく。

で、「Aが有限集合ならば、その真部分集合への単射は存在しない。」というには、次の2つの証明が必要となる。真面目に書くとかなり長い。以下、m,n,i,j,p,qという記号はすべてNの要素（つまり自然数）とする。

(I) m>0とする。Bをm元集合の真部分集合とするとき、あるnが存在し、n<mかつBはn元集合となる
(ii) n<mとするときm元集合からn元集合への単射は存在しない

(i) m=1の時: 1元集合の部分集合は空集合しかないので、0元集合となるからよい。m=p(>0)の時主張が成り立つとしてm=p+1の時：Aを(p+1)元集合とすると、p元集合Xと1元集合{a}があって、A=X∪{a}, X∩{a}=∅と書ける。Aの真部分集合Bをとる。B⊂Xの時とB∋aの時で場合分けをして、あるq<p+1が存在してBがq元集合となることを証明せよ。

(ii) n=0の時明らか。n=qの時okとする。n=q+1の時、m(>q+1)元集合Aから(q+1)元集合Bへの単射fがあるとする。m>q+1≧1であるゆえ、m=p+1とおく。p>qである。先ほどと同様p元集合Xと1元集合{a}を用いて、A=X∪{a}, X∩{a}=∅と表す。fのXへの制限は、p元集合XからC=B\{f(a)}への単射である。CはBの真部分集合であるから、さっきの命題(i)からq元以下であり、p>qであるから仮定に反する。

(i)と(ii)を合わせると「Aが有限集合ならば、その真部分集合への単射は存在しない」という事が言える。

回答No.2

tmppassenger

>「n元集合」であるとは、{j∈N|j<N}とAとに一対一対応が存在する事をいい
「n元集合」であるとは、{j∈N|j<n}とAとに一対一対応が存在する事をいい