有限集合

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

また同じことだが、集合が有限であるとはその濃度（元の個数）が自然数である場合にいう。特に、濃度が n である集合を「n 元集合（n-set）」と総称する。例えば、−15 から 3 まで（両端を含まない）の整数の集合は17個の元があり、有限である。したがってこれは17元集合である。一方、全ての素数たちの成す集合は $\aleph _{0}$ の濃度を持つ無限集合である。

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

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

x, y がどんな元だったとしても、{}, {x}, {x, 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 | x < n} となる自然数の集まりとの全単射として定義できる。数学では一般に数の概念を集合論に基づいて定義するため、例えば有限の整列集合の順序型によって自然数をモデル化する。その場合、有限性について自然数に基づかない構造的定義が必要となる。

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

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

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

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

有限性の必要十分条件

基礎付け問題

関連項目

参考文献

Related Articles