基礎付け問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/12 07:41 UTC 版)
ゲオルク・カントールは、無限集合を数学的に扱える集合論を構築しようとした。従って、有限集合と無限集合の区別が理論の中核に存在することとなった。基礎付け主義者（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 の元の列 x1, x2, x3, ... があるとき、この列上の元に対しては f ( x i ) = x i + 1 {\displaystyle f(x_{i})=x_{i+1}} となり、それ以外の元については恒等関数として振舞う関数 f を定義できる。従って、デデキント無限集合には自然数と全単射的に対応する部分集合が含まれる。デデキント有限集合とは、全ての単射自己写像が全射でもある場合を指す。 クラトフスキの有限性の定義は次の通りである。任意の集合 S について、和集合の二項演算は冪集合 P(S) に半束構造を与える。空集合と単集合から生成した半束を K(S) と記し、S が K(S) に属する場合、S をクラトフスキ有限集合と呼ぶ。直観的に K(S) には S の有限な部分集合が含まれる。重要なのは、この定義では自然数による帰納も再帰も必要とせず、K(S) は単に空集合と単集合を含む全ての半束構造の積集合として得られる点である。 ZFでは、クラトフスキ有限はデデキント有限を包含するが、逆は真ではない。
※この「基礎付け問題」の解説は、「有限集合」の解説の一部です。
「基礎付け問題」を含む「有限集合」の記事については、「有限集合」の概要を参照ください。
- 基礎付け問題のページへのリンク
