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

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

有限集合と無限集合

集合 $A$ の部分集合全体からなる集合を $A$ の冪集合といい, $\mathcal{P}(A)$ で表す.

$\mathcal{P}(A)$ の部分集合 $\mathcal{I}$ (すなわち, $A$ の部分集合を元とする集合) が帰納的 (inductive) とは, 次の $2$ つの条件を満たすときにいう.

・$\emptyset\in\mathcal{I}$.

・任意の $B\in\mathcal{I}$ と $a\in A$ に対して, $B\cup\{a\}\in\mathcal{I}$.

集合 $A$ が有限集合 (finite set) であるとは, 任意の帰納的な $\mathcal{I}\subseteq\mathcal{P}(A)$ に対して, $A\in\mathcal{I}$ となるときにいう.

$A$ が無限集合 (infinite set) であるとは, $A$ が有限集合でないときにいう.

集合の対等

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

集合 $A$, $B$, $C$ について, 以下のことが成り立つ.

・$A\sim A$.

・$A\sim B$ ならば $B\sim A$.

・$A\sim B$ かつ $B\sim C$ ならば, $A\sim C$.

任意の集合 $B$ に対して, 空集合 $\emptyset$ から $B$ への写像はただ $1$ つ存在し, 単射になる. そのような写像が全射になるのは, $B=\emptyset$ であるとき, またそのときに限る. したがって, 空集合と対等な集合は空集合しかない.

有限集合の元の個数

$\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}$ が成り立つとき, $n$ を $A$ の元の個数といい, $\#A$ で表すことにする.

定義より明らかに, 任煮の $n\in\mathbb{N}$ に対して, $\#I_{n}=n$ が成り立つ.

空集合と対等な集合は空集合しかないので, 集合 $A$ の元の個数が $0$ であることは $A$ が空集合であることとと同値である.

[定理] 集合 $A$ が有限集合であるための必要十分条件は, ある $n\in\mathbb{N}$ が存在して $A\sim I_{n}$ が成り立つことである.

[証明] 任意の帰納的な $\mathcal{I}\subseteq\mathcal{P}(A)$ に対して, $A\in\mathcal{I}$ が成り立つとする. $$ \mathcal{J} = \{ B\in\mathcal{P}(A)\mid B\sim I_{n}\;(\exists n\in\mathbb{N}) \} $$ とおくと, $\mathcal{J}$ は帰納的である. 仮定より, $A\in\mathcal{J}$ である. すなわち, ある $n\in\mathbb{N}$ が存在して, $A\sim I_{n}$ が成り立つ.

逆に, ある $n\in\mathbb{N}$ が存在して, $A\sim I_{n}$ が成り立つと仮定する. このとき, 任意の帰納的な $\mathcal{I}\subseteq\mathcal{P}(A)$ に対して $A\in\mathcal{I}$ となることを, $\#A$ に関する数学的帰納法により証明する.

$\#A = 0$ のとき, $A=\emptyset\in\mathcal{I}$.

$\#A = n$ のとき正しいと仮定する. $\#A = n+1$ のとき, $$ A = \{a_{0},\,a_{1},\,\ldots,\,a_{n}\} $$ とおくと, $$ A = \{a_{0},\,a_{1},\,\ldots,\,a_{n-1}\} \cup \{a_{n}\}\in\mathcal{I}. $$ したがって, $\#A=n+1$ のときも正しい. (証明終)

Dedekind 有限

集合 $A$ が Dedekind 有限 (Dedekind finite) あるいは Dedekind の意味で有限 (finite in the Dedekind sense) であるとは, $A$ の真部分集合で $A$ と対等なものが存在しないときにいう. またこのとき, $A$ を Dedekind 有限集合 (Dedekind finite set) という.

集合 $A$ が Dedekind 有限であれば, $A$ と対等な集合もまた Dedekind 有限である.

集合 $A$ が Dedekind 有限であれば, $A$ の部分集合もまた Dedekind 有限である.

有限集合はすべて Dedekind 有限である ($I_{n}$ が Dedekind 有限であることを示せば十分である. $n$ に関する数学的帰納法により証明できる). この命題の系として次のことがいえる. $A$, $B$ を有限集合とするとき, $A\sim B$ かつ $A\subseteq B$ ならば, $A=B$ が成り立つ.

可算集合 (=$\mathbb{N}$ と対等な集合) は Dedekind 有限ではない ($\mathbb{N}$ が Dedekind 有限でないことを示せば十分である). この命題の系として, 可算集合は有限集合でない (したがって, 無限集合である) ことがいえる.

Dedekind 有限集合が有限集合であることは, 選択公理を仮定すれば正しい. より詳しくは, 一般の無限集合が Dedekind 有限でないことを証明するために, すべての無限集合が可算部分集合をもつこと (この命題の証明に選択公理が使われる) を用いる.

以上より, 集合が有限集合であることと Dedekind 有限集合であることは (選択公理を仮定すれば) 同値である. このことは, 次のように言い換えることができる.

[定理] 集合 $A$ が無限集合であるための必要十分条件は, $A$ のある真部分集合 $B$ が存在して $A\sim B$ が成り立つことである.

参考文献

  • 篠田寿一, 米沢佳己:集合・位相演習, サイエンス社, 1995.
  • 日本数学会 (編):岩波数学辞典 第 4 版, 岩波書店, 2007.

関連記事

デデキント有限集合の部分集合もまたデデキント有限である
有限集合はデデキント有限である

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

プロフィール

よしいず

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

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

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

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

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

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示