スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

有限集合はデデキント有限である

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

集合 $A$ が集合 $B$ と対等であるとは, $A$ から $B$ への全単射が存在するときにいう. このことを $A\sim B$ で表す.

$\mathbb{N}$ を自然数全体からなる集合とする ($0$ も自然数に含めるものとする). また, $$ I_{0} = \emptyset,\quad I_{n} = \{0,\,1,\,\ldots,\,n-1\}\quad (n=1,\,2,\,\ldots) $$ とおく. 集合 $A$ が有限集合であるとは, ある $n\in\mathbb{N}$ が存在して $A\sim I_{n}$ が成り立つときにいう.

集合 $A$ が Dedekind 有限であるとは, $A$ の真部分集合で $A$ と対等なものが存在しないときにいう.

[定理] 有限集合は Dedekind 有限である.

[証明] Dedekind 有限集合と対等な集合は Dedekind 有限であるから, 任意の $n\in\mathbb{N}$ に対して $I_{n}$ が Dedekind 有限であることを証明すれば十分である. これを $n$ に関する数学的帰納法により証明する.

$I_{0} = \emptyset$ の部分集合は $I_{0}$ 自身しかない. よって, $I_{0}$ は真部分集合をもたない. 特に, $I_{0}$ と対等な真部分集合は存在しない. したがって, $I_{0}$ は Dedekind 有限である.

$I_{1} = \{0\}$ の真部分集合は空集合 $\emptyset$ のみである. $\emptyset$ と対等な集合は $\emptyset$ のみであるから, $\emptyset$ は $I_{0}$ と対等にならない. したがって, $I_{1}$ は Dedekind 有限である.

$n\geq 1$ とし, $I_{n}$ が Dedekind 有限であると仮定する. $B$ を $I_{n+1}$ の部分集合とし, 全単射 $f:I_{n+1}\rightarrow B$ が存在するものとする. さらに, $B'=B\setminus\{f(n)\}$ とおく. すると, $f$ の $I_{n}$ への制限 $f\mid I_{n}:I_{n}\rightarrow B'$ もまた全単射である.

もし仮に $n\not\in B$ とすると, $B$ は $I_{n}$ の部分集合であり, $f(n)\in I_{n}$ かつ $f(n)\not\in B'$ であるから, $B'$ は $I_{n}$ の真部分集合である. 一方, 全単射 $f\mid I_{n}$ の存在と帰納法の仮定により, $B'$ は $I_{n}$ の真部分集合ではない. これは矛盾である. ゆえに, $n\in B$ でなければならない.

$n\in B$ かつ $f(n)=n$ のとき. $B'=B\setminus\{n\}$ は $I_{n}$ の部分集合である. 全単射 $f\mid I_{n}$ の存在と帰納法の仮定により, $B'=I_{n}$ が得られる. このとき, $$ B=B'\cup\{n\} = I_{n}\cup\{n\} = I_{n+1} $$ となる.

$n\in B$ かつ $f(n)\neq n$ のとき. ある $i\in I_{n+1}$ が存在して, $f(i)=n$ かつ $i\neq n$ である. 写像 $g:I_{n+1}\rightarrow B$ を, $$ g(x) = \begin{cases} f(x), & \mbox{$x\neq i$ かつ $x\neq n$ のとき}, \\ f(n), & \mbox{$x=i$ のとき}, \\ n, & \mbox{$x=n$ のとき} \end{cases} $$ とおくことにより定める. $g$ は全単射かつ $g(n)=n$ である. 先の議論により, $B=I_{n+1}$ となる.

したがって, $I_{n+1}$ の任意の部分集合 $B$ に対して, $I_{n+1}$ から $B$ への全単射が存在すれば $B=I_{n+1}$ である. この対偶を考えると, 任意の真部分集合 $B$ に対して, $I_{n+1}$ から $B$ への全単射は存在しない. ゆえに, $I_{n+1}$ もまた Dedekind 有限である. (証明終)

上の定理から直ちに, 次の系が得られる.

[系] $A$, $B$ を有限集合とする. このとき, $A\sim B$ かつ $A\subseteq B$ ならば, $A=B$ が成り立つ.

関連記事

有限集合とデデキント有限集合

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。