有限集合

数学において、有限集合とは有限個の異なるものの集まりのことです。これらのものは集合の要素またはメンバーと呼ばれ、通常は数、記号、空間上の点、線、その他の幾何学的形状、変数、または他の集合などの数学的な対象です。

非公式には、有限集合とは、原理的には数え終えることができる集合のことである。例えば、 $${\displaystyle \{2,4,6,8,10\}}$$ は 5 つの要素を持つ有限集合です。有限集合の要素数は自然数（0 の場合もある）であり、その集合の濃度（または基数）と呼ばれます。有限集合ではない集合は無限集合と呼ばれます。例えば、集合 は $${\displaystyle \{1,2,3,\ldots \}}$$ すべての正の整数の数は無限である。

有限集合は、組み合わせ論、つまり数を数える数学において特に重要である。有限集合に関する多くの議論は、より大きな有限集合からより小さな有限集合への単射関数は存在しないという鳩の巣原理に基づいている。

自然数はペアノ公理によって抽象的に定義され、集合論的に構成することができる（例えば、フォン・ノイマン順序数によって）。そして形式的には、集合は${\displaystyle S}$全単射が存在する場合、有限であると呼ばれる。$${\displaystyle f\colon S\to \{1,2,\cdots ,n\}}$$ ある自然数に対して${\displaystyle n}$要素を数えるのと同様です。${\displaystyle S}$空である、これは空虚に満たされる${\displaystyle n=0}$空の関数で。数値${\displaystyle n}$は集合の濃度であり、次のように表される。${\displaystyle |S|}$。

空でない集合が有限集合である場合、その要素は次のような数列で表すことができます。 $${\displaystyle x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).}$$n ≥ 2 の場合、そのような数列は複数存在する。組み合わせ論では、有限集合は${\displaystyle n}$要素は、${\displaystyle n}$-集合と部分集合${\displaystyle k}$要素は${\displaystyle k}$-部分集合。例えば、集合${\displaystyle \{5,6,7\}}$は3要素集合 （3つの要素を持つ有限集合）であり 、${\displaystyle \{6,7\}}$それはその2部分集合である。

この表記法${\displaystyle \{1,\cdots ,n\}}$再帰的に定義すると

$${\displaystyle \{1,\cdots ,n\}=\left\{{\begin{array}{lll}\varnothing {\text{ (空集合)}}&{\text{if}}&n=0\\\{1,\cdots ,n-1\}\cup \{n\}&{\text{if}}&n\geq 1\\\end{array}}\right.}$$

有限集合の任意の真部分集合${\displaystyle S}$は有限であり、 S自体よりも要素数が少ない。したがって、有限集合SとSの真部分集合との間に全単射は存在しない。この性質を持つ集合はデデキント有限と呼ばれる。集合論の標準的なZFC公理を用いると、すべてのデデキント有限集合は有限でもあるが、この含意はZF (選択公理を除いたツェルメロ・フレンケル公理​​) だけでは証明できない。選択公理の弱いバージョンである可算選択公理があれば、この同値性を証明するのに十分である。

同じ濃度を持つ2つの有限集合間の単射関数は、全射関数（射影）でもある。同様に、同じ濃度を持つ2つの有限集合間の全射も単射である。

2 つの有限集合の和集合は有限であり、 $${\displaystyle |S\cup T|\leq |S|+|T|.}$$

実際、包含排除原理によれば： $${\displaystyle |S\cup T|=|S|+|T|-|S\cap T|.}$$ より一般的に言えば、有限個の有限集合の和集合は有限である。有限集合の直積も有限であり、次のようになる。 $${\displaystyle |S\times T|=|S|\times |T|.}$$ 同様に、有限個の有限集合の直積は有限である。${\displaystyle n}$要素には$2n$異なる部分集合。つまり、冪集合${\displaystyle \wp (S)}$有限集合Sの要素数は有限であり、$\displaystyle 2^{|S|}}$。

有限集合の任意の部分集合は有限である。有限集合の要素に関数を適用したときの値の集合は有限である。

すべての有限集合は可算集合であるが、すべての可算集合が有限集合であるとは限らない。（ただし、著者によっては「可算」を「可算無限」という意味で用いる場合があり、その場合は有限集合を可算集合とはみなさない。）

有限集合上の自由半束とは、その集合の空でない部分集合の集合であり、結合演算は集合の和集合によって与えられる。

選択公理のないツェルメロ・フレンケル集合論（ZF）では、以下の条件はすべて同値である： ^{[ 1 ]}

1. ${\displaystyle S}$は有限集合です。つまり、${\displaystyle S}$それらは、ある特定の自然数より小さい自然数の集合と1対1に対応させることができる。
2. （カジミエシュ・クラトフスキ）${\displaystyle S}$空集合から始めて一度に1つの新しい要素を追加していく数学的帰納法によって証明できるすべての性質を備えている。
3. （ポール・シュテッケル）${\displaystyle S}$には順方向と逆方向の両方で整列した全順序付けを与えることができる。つまり、 の空でない部分集合はすべて${\displaystyle S}$部分集合には、最小値と最大値の両方が含まれている。
4. すべての1対1機能${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$自身への冪集合はに上付きである。つまり、の冪集合の冪集合はに上付きである。${\displaystyle S}$はデデキント有限です (以下を参照)。^{[ 2 ]}
5. すべての全射関数${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$それ自身と対になるのは1対1対応である。
6. （アルフレッド・タルスキー）空でない部分集合の族${\displaystyle S}$包含関係に関して最小要素を持つ。 ^{[ 3 ]}（同等に、空でない部分集合の族はすべて${\displaystyle S}$包含関係に関して最大​​要素を持つ。）
7. ${\displaystyle S}$は整列可能であり、その上の任意の 2 つの整列は順序同型である。言い換えれば、上の整列は${\displaystyle S}$注文タイプは正確に1つだけあります。

選択公理も仮定する場合（可算選択公理で十分である）、^{[ 4 ]}次の条件はすべて同値である。

1. ${\displaystyle S}$は有限集合である。
2. （リチャード・デデキント）すべての1対1関数${\displaystyle S}$自身への内包は全射である。この性質を持つ集合はデデキント有限集合と呼ばれる。
3. すべての全射関数${\displaystyle S}$それ自身と対になるのは1対1対応である。
4. ${\displaystyle S}$空であるか、またはすべての部分順序${\displaystyle S}$最大要素を含む。

有限集合の重要な性質の一つは、例えば集合の濃度が4であれば、濃度が5になることはない、ということである。直感的には、集合はちょうど4つの要素とちょうど5つの要素の両方を持つことはできない、という意味である。しかし、これはそれほど自明に証明されているわけではない。以下の証明は、Terence Tao著『Analysis I』^{[ 8 ]}から引用したものである。

補題：集合が${\displaystyle X}$カーディナリティを持つ${\displaystyle n\geq 1,}$そして${\displaystyle x_{0}\in X,}$それからセット${\displaystyle X-\{x_{0}\}}$（つまり）${\displaystyle X}$要素と共に${\displaystyle x_{0}}$削除済み）のカーディナリティ${\displaystyle n-1.}$

証明:${\displaystyle X}$上記のとおり、${\displaystyle X}$カーディナリティを持つ${\displaystyle n,}$全単射が存在する${\displaystyle f}$から${\displaystyle X}$に${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$それから、${\displaystyle x_{0}\in X,}$何らかの数字が存在するはずだ${\displaystyle f(x_{0})}$で${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$から全単射を見つける必要があります${\displaystyle X-\{x_{0}\}}$に${\displaystyle \{1,\dots n-1\}}$（空でも構いません）。関数を定義します。${\displaystyle g}$そのため${\displaystyle g(x)=f(x_{0})}$もし${\displaystyle f(x)=n}$、 そして${\displaystyle g(x)=f(x)}$そうでなければ。${\displaystyle g}$は全単射である${\displaystyle X-\{x_{0}\}}$に${\displaystyle \{1,\dots n-1\}.}$

定理：集合が${\displaystyle X}$カーディナリティを持つ${\displaystyle n,}$そうすれば、他の濃度を持つことはできません。つまり、${\displaystyle X}$基数性を持つことはできない${\displaystyle m\neq n.}$

証明: もし${\displaystyle X}$が空集合（濃度が 0）である場合、からの全単射は存在しない。${\displaystyle X}$任意の空でない集合へ${\displaystyle Y,}$なぜなら、空虚に、何もマッピングできないから${\displaystyle y_{0}\in Y.}$帰納法によって、結果がある濃度まで証明されたと仮定する。${\displaystyle n.}$もし${\displaystyle X,}$カーディナリティを持つ${\displaystyle n+1,}$基数も持っていると仮定する${\displaystyle m.}$私たちはそれを示したい${\displaystyle m=n+1.}$上記の補題により、${\displaystyle X-\{x_{0}\}}$基数を持つ必要があります${\displaystyle n}$そして${\displaystyle m-1.}$帰納法により、濃度が の集合の濃度は一意である。${\displaystyle n,}$きっとそうに違いない${\displaystyle m-1=n,}$そしてこうして${\displaystyle m=n+1.}$

• フィンセット
• 離散点集合
• 序数
• ペアノ算術

• アポストル、トム・M. (1974)、数学解析（第2 版）、メンローパーク：アディソン・ウェスリー、LCCN 72011473 
• コーン、ポール・モリッツ、FRS (1981)、ユニバーサル代数、ドルドレヒト: D. Reidel、ISBN 90-277-1254-9、LCCN 80-29568 {{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)
• デデキント、リチャード(2012)、Was sind und was sollen die Zahlen?、ケンブリッジ図書館コレクション (ペーパーバック 版)、ケンブリッジ、英国: Cambridge University Press、ISBN 978-1-108-05038-8
• デデキント、リチャード（1963）、『数の理論に関するエッセイ』、ドーバー数学叢書、ビーマン、ウースター・ウッドラフ（ペーパーバック 版）、ドーバー出版、ISBN 0-486-21010-3{{citation}}ISBN /日付の不一致（ヘルプ）
• デラクルス、オマール。ジャファロフ、ダミール D. Hall、Eric J. (2006)、「順序特性に基づく有限性の定義」(PDF)、Fundamenta Mathematicae、189 (2): 155–172、doi : 10.4064/fm189-2-5、MR 2214576 
• Herrlich、Horst (2006)、「選択の公理」、数学の講義ノート。 1876 年、ベルリン: Springer-Verlag、ISBN 3-540-30989-6
• ハワード、ポール、ルービン、ジーン E. (1998)、『選択公理の帰結』、プロビデンス、ロードアイランド州：アメリカ数学会、ISBN 9780821809778
• Kuratowski, Kazimierz (1920)、「Sur la notion d'ensemble fini」(PDF)、Fundamenta Mathematicae、1 : 129–131、doi : 10.4064/fm-1-1-129-131、オリジナルから 2011-05-15 にアーカイブ(PDF)
• ラバール、アンソニー・E・ジュニア（1968）、『中級数学解析』、ニューヨーク：ホルト・ラインハート・アンド・ウィンストン、LCCN 68019130 
• レヴィ、アズリエル（1958）「有限性の様々な定義の独立性」（PDF）、『Fundamenta Mathematicae』、46：1–13、doi：10.4064/fm-46-1-1-13、2003年7月5日にオリジナルからアーカイブ（PDF）
• ルディン、ウォルター（1976）、『数学解析の原理』（第3 版）、ニューヨーク：マグロウヒル、ISBN 0-07-054235-X
• サップス、パトリック(1972) [1960]、『公理的集合論』、ドーバー数学叢書（ペーパーバック 版）、ドーバー出版、ISBN 0-486-61630-4
• Tao, Terence (2022), Analysis I , Texts and Readings in Mathematics (第4 版), Singapore: Springer Science+Business Media , doi : 10.1007/978-3-662-00274-2 , ISBN 978-981-19-7261-4ISSN 2366-8717​ 
• Tarski, Alfred (1924)、「Sur les ensembles finis」(PDF)、Fundamenta Mathematicae、6 : 45–95、doi : 10.4064/fm-6-1-45-95、2011 年 5 月 15 日にオリジナルからアーカイブ(PDF)
• Tarski, Alfred (1954), 「基数の後継者の存在に関する定理と選択公理」、Nederl. Akad. Wetensch. Proc. Ser. A, Indagationes Math.、16 : 26– 32、doi : 10.1016/S1385-7258(54)50005-3、MR 0060555 
• ホワイトヘッド、アルフレッド・ノース、ラッセル、バートランド（2009年2月）[1912]、『プリンキピア・マテマティカ』第 2巻、マーチャント・ブックス、ISBN 978-1-60386-183-0

• Barile、マルゲリータ、「有限集合」、MathWorld