有限集合のソースを表示

[[数学]]において、[[集合]]が'''有限'''（ゆうげん、{{lang-en|''finite''}}）であるとは、[[自然数]] ''n'' を用いて {1,&nbsp;2,&nbsp;...,&nbsp;''n''} という形にあらわされる集合との間に[[全単射]]が存在することをいう（ただしここでは、''n''&nbsp;=&nbsp;0 の場合も許される。この場合は[[空集合]]であることを意味するのであり、これも有限集合の一種と考えるということである）。このような集合を'''有限集合'''（ゆうげんしゅうごう、{{lang-en|''finite set''}}）とよび、有限でない集合を[[無限集合]]と呼ぶ。

また同じことだが、集合が有限であるとはその[[濃度 (数学)|濃度]]（[[元 (数学)|元]]の個数）が自然数である場合にいう。特に、濃度が ''n'' である集合を「''n'' 元集合（''n''-set）」と総称する。例えば、&minus;15 から 3 まで（両端を含まない）の[[整数]]の集合は17個の元があり、有限である。したがってこれは17元集合である。一方、全ての[[素数]]たちの成す集合は <math>\aleph_0</math> の濃度を持つ無限集合である。

どんな[[部分集合|真部分集合]]との間にも全単射が存在しないような集合は、'''[[デデキント無限集合|デデキント有限集合]]'''と呼ばれる。[[可算選択公理]]（弱い形の[[選択公理]]）が成り立つなら、集合が有限であることとデデキント有限であることは[[同値]]である。そうでない場合には（奇異なことに）無限かつデデキント有限な集合が存在しうる（「基礎付け問題」の節を参照）。

全ての有限集合は[[可算集合|可算]]であるが、全ての可算集合が有限というわけではない。ただし、書籍によっては「可算」を「可算無限」の意味に使っており、その場合は有限集合は可算ではない。

== 有限集合の構成 == <!-- property は数学では「性質」くらいの意味, closure は閉包という意味もあるが, ここでは「(ある種の操作について) 閉じているような」程度の意味だろうと思われる. 原文では「何について」の部分が省略してあるが, 「有限集合に適当な操作をして有限性を保つかどうかということ」というような趣旨のタイトルだと思われる. 少なくとももともとの訳「閉包属性」では何のことかわからないので, 原文を訳すことをやめて, 無難そうなタイトルに変更した. -->
* ''x'', ''y'' がどんな元だったとしても、{}, {''x''}, {''x'',&nbsp;''y''} といったような集合は有限集合である。
* 有限個の有限集合たちの[[合併 (集合論)|和集合]]はふたたび有限集合となる。
* 有限集合の[[冪集合]]はやはり有限集合である。
* 有限集合の任意の[[部分集合]]は有限である。
* 有限集合を定義域とする関数の値域は有限である。
* 有限個の有限集合たちから成る[[直積集合]]はまた有限である。
一方で、（[[無限公理]]によって存在が保証されるところの）自然数全体の成す集合というのは有限集合ではない。

== 有限性の必要十分条件 ==
[[公理的集合論|ツェルメロ＝フレンケルの集合論]] (ZF) では、以下の条件は全て等価である。

# ''S'' は有限集合である。すなわち、''S'' の元はある特定の自然数未満の自然数の集合の元と一対一対応する。
# ''S'' は、空集合を始点として元を1つずつ追加していく数学的帰納法で証明可能な全属性を持つ。（[[カジミェシュ・クラトフスキ]]）
# ''S'' にはある全順序が存在し、かつその全順序はどちらの方向にも整列順序となる。すなわち、（ある全順序の元に）''S'' の空でない全ての部分集合には最小元と最大元がある。
# P(P(''S''))からそれ自身への一対一関数は全単射である。すなわち、''S'' の[[冪集合]]の冪集合はデデキント有限である。
# P(P(''S''))からそれ自身への全射は全て一対一対応である。
# ''S'' の部分集合の空でない[[族 (数学)|族]]は、いずれも包含関係上の極小元を持つ。（[[アルフレト・タルスキ]]）
# ''S'' 上にはある整列順序が存在し、かつ''S''上の任意の2つの整列順序は順序同型である。言い換えれば、''S'' の整列順序はただ1つの順序型を持つ。

[[選択公理]]も成り立つ場合、以下の条件は全て等価である。

# ''S'' は有限集合である。
# ''S'' からそれ自身への一対一関数は全単射である。（[[リヒャルト・デーデキント]]）
# ''S'' からそれ自身への全射はいずれも一対一対応である。
# ''S'' は空集合であるか、もしくは''S''上の任意の半順序は[[順序集合|極大元]]を持つ。

== 基礎付け問題 ==
[[ゲオルク・カントール]]は、無限集合を数学的に扱える集合論を構築しようとした。従って、有限集合と無限集合の区別が理論の中核に存在することとなった。基礎付け主義者（foundationalist）の中でも特に[[有限主義]]者は無限集合の存在を認めず、有限集合にのみ基づいた数学を提唱した。多くの数学者は厳密な有限主義は制限しすぎていると見なしたが、その相対的な一貫性は認めていた。すなわち、遺伝的（hereditarily）有限集合の領域は、[[無限公理]]をその否定と置換した[[公理的集合論|ツェルメロ＝フレンケルの公理的集合論]]のモデルを構成する。

無限集合を擁護する数学者にとっても、ある重要な文脈では、有限集合と無限集合の形式的区別は微妙な問題として残った。これは[[ゲーデルの不完全性定理]]に端を発している。遺伝的有限集合は[[ペアノの公理|ペアノ算術]]で解釈でき（逆もまた同様）、従ってペアノの理論体系の不完全性は遺伝的有限集合の理論にも存在することが暗に示されている。特に、どちらの理論にもいわゆる非標準モデルの過剰が存在する。見かけ上のパラドックスとして、遺伝的有限集合の非標準モデルは無限集合を含んでいるが、それら無限集合はそのモデル内では有限に見える（これは、それら集合の無限性を証明するのに必要な集合や関数をモデルが持たない場合に生じる）。不完全性定理があるため、[[一階述語論理]]やその再帰的適用では、そのようなモデルすべての標準部分を特徴付けることができない。従って、一階述語論理の観点からは、有限性をおおよそ特徴付けることしか望めない。

より一般化すると、[[集合]]や有限集合といった非形式的観念は、様々な[[形式体系]]の公理的機構と論理的機構によって解釈される。よく知られた公理的集合論として[[ツェルメロ＝フレンケルの公理系]] (ZF) 、[[公理的集合論|ZF に選択公理を加えたもの]] (ZFC)、[[NBG集合論]]（ノイマン＝ベルナイス＝ゲーデル）、[[非有基的集合論]]、[[バートランド・ラッセル]]の[[型理論]]、および各種モデルの理論がある。場合によっては、古典的な一階述語論理、各種高階論理、[[直観論理]]などを選択する場合もある。

[[形式主義 (数学)|形式主義]]の観点では、「集合」の意味は系によって異なる。プラトン主義的には、ある特定の形式体系をその根底にある現実の近似と見る。

[[自然数]]の概念が論理的に集合の前に前提としてある場合、[[集合]] ''S'' が有限であることを {''x''&nbsp;|&nbsp;''x''&nbsp;&lt;&nbsp;''n''} となる[[自然数]]の集まりとの[[全単射]]として定義できる。数学では一般に数の概念を[[集合論]]に基づいて定義するため、例えば有限の整列集合の順序型によって[[自然数]]をモデル化する。その場合、有限性について[[自然数]]に基づかない構造的定義が必要となる。

興味深いことに、ZFCにおいて有限集合を集合全般から区別する様々な特性は、より弱い体系であるZFや直観主義的集合論の場合とは論理的に等価ではないことが判っている。よく知られている有限性の定義として、[[リヒャルト・デーデキント]]の定義と[[カジミェシュ・クラトフスキ]]の定義がある。

単射だが全射ではない関数 ''f'':&nbsp;''S''&nbsp;&rarr;&nbsp;''S'' が存在するとき、集合 ''S'' を[[デデキント無限集合]]と呼ぶ。そのような関数は ''S'' と ''S'' の真部分集合（''f'' の像）との間の全単射を表している。デデキント無限集合 ''S'' の元 ''x'' が ''f'' の像に属さないとき、''x'', ''f''(''x''), ''f''(''f''(''x'')), ... のようにして ''S'' の異なる元の無限の列を得ることができる。逆に ''S'' の元の列 ''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ... があるとき、この列上の元に対しては <math>f(x_i)=x_{i+1}</math> となり、それ以外の元については恒等関数として振舞う関数 ''f'' を定義できる。従って、デデキント無限集合には自然数と全単射的に対応する部分集合が含まれる。デデキント有限集合とは、全ての単射自己写像が全射でもある場合を指す。

クラトフスキの有限性の定義は次の通りである。任意の集合 ''S'' について、和集合の二項演算は[[冪集合]] ''P''(''S'') に半束構造を与える。空集合と単集合から生成した半束を ''K''(''S'') と記し、''S'' が ''K''(''S'') に属する場合、''S'' をクラトフスキ有限集合と呼ぶ。直観的に ''K''(''S'') には ''S'' の有限な部分集合が含まれる。重要なのは、この定義では自然数による帰納も再帰も必要とせず、''K''(''S'') は単に[[空集合]]と[[単集合]]を含む全ての半束構造の積集合として得られる点である。

ZFでは、クラトフスキ有限はデデキント有限を包含するが、逆は真ではない。

== 関連項目 ==
*[[ペアノの公理]]
*[[順序数]]
*[[有限]]

== 参考文献 ==
* Patrick Suppes, ''Axiomatic Set Theory'', D. Van Nostrand Company, Inc., 1960

{{集合論}}
{{DEFAULTSORT:ゆうけんしゆうこう}}
[[Category:離散数学]]
[[Category:集合論]]
[[Category:数学に関する記事]]