置換公理
置換公理(axiom schema of replacement)または置換の公理型は、公理的集合論におけるZF公理系を構成する公理の一つである。この公理は、任意の任意の集合間のすべての写像は、また集合であることを主張していて、ZF公理系での無限集合の構成に必要である。この公理は「あるクラスが集合かどうかは、階数ではなく濃度に依存する」という要請から動機付けされる。つまり、「集合になれるだけ小さい濃度を持つ」集合AからクラスBに全射があるとき、クラスBは集合であることを主張している。しかしながら、ZF公理系ではクラスに関して厳密な言及がないため、置換公理の主張の対象は論理式によって定義可能な写像に対してのみである。
PはクラスAに関する二項関係であり、すべてのxに対してP(x, y)なるyがただ一つ存在しているとする。これに対してF_P(x)=y \iff P(x, y) を満たす構成可能な関数F_P
を考える。ここで、クラス(かもしれない)Bを、y \in B \iff \exist x \in A (F_P(x) = y)として定義する。またB = \{F_P(x)\mid x \in A \}であり、BはA上のF_Pによる値域と呼び、F_P[A]と書く。
置換公理の主張は、ここでF_Pが定義可能でAが集合ならば、Bもまた集合であることである。
より厳密には、すべての式を一階述語論理によって量化することはできないので、メタ変項として式\phi、及びその変数w_1,\dotsc,w_n,A,x,yを用いて、
\begin{align}\forall w_1,\ldots,w_n \, \forall A \, ( [ \forall x \in A &\, \exists ! y \, \phi(x, y, w_1, \ldots, w_n, A) ]\ \Longrightarrow\ \exists B \, \forall y \, [y \in B \Leftrightarrow \exists x \in A \, \phi(x, y, w_1, \ldots, w_n, A) ] )\end{align}
とする。\exist!はただ一つ存在することを表す。
置換公理は、通常の数学におけるほとんどの定理の証明に必ずしも必要ではない。実際、ツェルメロ集合論 (Z) ではすでに二階算術と多くの有限型の型理論を扱うことができ、数学の大部分を定式化するには十分である。置換公理はこんにちの集合論の標準的な公理であるものの、型理論のシステムやトポス理論における基礎的システムでは省略されることも多い。
多かれ少なかれこの公理は、ZFで証明可能な定理(たとえば集合の存在証明)や証明論的な無矛盾性の強さの点において、Zと比べて劇的にZFを強固にする。以下に重要な例を示す。
フォン・ノイマンの現代的な定義を使うと、ω より大きい任意の極限順序数の存在証明に置換公理が必要である。順序数 ω·2 = ω + ω はそのような順序数の最初の例である。無限公理は無限集合 ω = {0, 1, 2, ...} の存在を主張する。ω·2 を数列 {ω, ω + 1, ω + 2,...} の合併として定義したいとする。しかし、そのような順序数のクラスは集合にはならない(例えば、すべての順序数のクラスは集合ではない)。置換公理を用いると、ω における有限の数 n それぞれを、対応する ω + n に置き換えることができ、そうすることでこのクラスを集合とみなすことができる。補足として、置換公理に頼らず ω·2 と同型な整列集合を簡単に構築できることに注意(単に二つの ω に対して、一方が他方より大きくなるように直和をとればよい)。しかし、内包によって完全に順序付けられていないため、これは順序数ではない。
大きな順序数ほど直接的には置換公理を使わなくなる。例えば、最小の非可算順序数 ω1 は、以下のように構築できる。分出公理と冪集合公理より、可算整列集合は P({\mathbb N}\times {\mathbb N}) の部分集合として存在する(A 上の関係は A\times A の部分集合であるため、冪集合 P(A\times A)の元となる。それゆえ、関係の集合は P(A\times A)の部分集合となる)。各整列集合をその順序数で置き換えると可算順序数の集合 ω1 となり、これは非可算であることが示せる。この構築法では置換公理を2回使っている。まず各整列集合に順序数を割り当てるところで用い、そして整列集合をその順序数で置き換えるところで使っている。これはハルトークス数の結果の特別な場合であり、一般の場合も同様に証明できる。
上記のように、順序数をすべての整列集合へ割り当てるのにも置換公理が必要である。同様に、基数を各集合に割り当てるフォン・ノイマンの割り当てには置換公理と選択公理が必要である。
A^n=A^{n-1}\times A として再帰的に定義される組の集合を考える。大きな A に対して、集合 \{A^n\mid n\in {\mathbb N}\} は、冪集合公理と選択公理を含み置換公理を含まない集合論において、その存在を証明できないほど高い階数を持つ。
同様に、ハーベイ・フリードマンはボレル集合の決定性を示すのに置換公理が必要であることを示した。
集合 Vω·2 を Z のモデルとすると、その存在を ZF で証明できるため、ZF+置換公理で Z の無矛盾性を証明できる。基数 \aleph_\omega はその存在を ZF で証明できるが Z で証明できない最小のものである。補足として、これらの理論それぞれが理論自身の無矛盾性を「表現する」文を含むが、理論が無矛盾である限り、理論の無矛盾性を理論自身の中では証明できないことがゲーデルの第二不完全性定理によって示されていることに注意。この結果はしばしば「どの理論も、理論が無矛盾である限り、自身の無矛盾性を証明できない」と大まかに表現される。
集まりの公理型(axiom schema of collection)は置換公理と密接に関連し、かつよく混同される。
他のZF公理系のもとでは、置換公理と等価である。集まりの公理は冪集合公理やそのZFの構成可能な部分が不要である分、置換公理よりも強いが、排中律がない IZF の枠組みにおいては弱い。
置換公理は関数の像が集合であると読めるが、集まりの公理は関係の像に関するもので、単に関係の像の上位クラスに集合であるものがあることを主張するのみである。
言い換えれば、集合 B は最小性を要せず、 \phi における唯一性も必要ない。
つまり、 \phi で定義される関係が関数である必要はない(x\in A の中には、 B に属する複数の y と対応するものがありうる)この場合、存在を主張する像集合 B には、もとの集合の元 x それぞれに対して少なくとも1つ(必ず1つとは限らない)対応する y が含まれる。
\phi の自由変数が w_1,\dotsc,w_n,x,y 上にあるとする。ただし、 A も B も \phi の自由変数ではない。すると集まりの公理は以下のようになる。
\forall w_1,\ldots,w_n \,[(\forall x\, \exists\, y \phi(x, y, w_1, \ldots, w_n)) \Rightarrow \forall A\, \exists B\, \forall x \in A\, \exists y \in B\, \phi(x, y, w_1, \ldots, w_n)]
集まりの公理は上記の述語に関する制限なしで表現されることもあり(B 以外に \phi に自由変数がない)、\phi は以下のようになる:
\forall w_1,\ldots,w_n \, \forall A\, \exists B\,\forall x \in A\, [ \exists y \phi(x, y, w_1, \ldots, w_n) \Rightarrow \exists y \in B\,\phi(x, y, w_1, \ldots, w_n)]
この場合、\phi で他の集合と対応付けられない A の元 x が存在しうる。しかし、集まりの公理は前述の通り 「A の元 x が少なくとも1つの集合 y と対応付けられれば、像集合 B は少なくとも1つそのような y を含む」ことを要請する。結果として、集まりの公理は境界性の公理型(axiom schema of boundedness)とも呼ばれる。
ZFCのほかの公理型である分出公理は置換公理と空集合の公理から導かれる。分出公理が集合論の言語における各論理式 \theta に対して以下を含むことを思い出そう(B は自由変数でない)。
\forall A\, \exists B\, \forall C\, (C \in B \Leftrightarrow [C \in A \land \theta(C)])
証明は以下のとおりである。まず B に関して言及しない論理式 \theta(C) と集合 A から始める。もし \theta(E) を満たす A の元 E がなければ、分出公理に必要な集合 B は空集合である。そうでない場合、 \theta(E) が成り立つ A の元 E を選ぶ。次にクラス関数 F を以下のように定義する:任意の元 D に対して \theta(D) が成り立つ場合は F(D)=D 、成り立たない場合は F(D)=E。すると F による A の像、すなわち集合 B = FA := \{F(x):x\in A\}=A\cap\{x:\theta(x)\} が存在し(置換公理による)、まさしく分出公理に必要な集合 B となる。
この結果から、ZFCが一つの無限の公理型で公理化可能であることがわかる。少なくとも1つはそのような無限の公理型が必要であるので(ZFCは有限公理か可能でない)、必要であれば置換公理はZFCにおける唯一の無限の公理型とできることがわかる。分出公理は独立でないため、ZF公理系の現代的な定義からはよく省略される。
しかし、歴史的経緯によるZFCの一要素としての扱いや、他の集合論との比較において、 分出公理は重要である。置換公理を含まない集合論の定式化では、そのモデルに十分に多くの集合の集まりが含まれることを保証するため、よく分出公理が用いられる。集合論のモデルの研究において、フォン・ノイマン階層におけるモデル V_\delta のように、置換公理を含まないZFCのモデルを考えると有用であることがある。
上記の証明では、A が空集合でないなら元を含むという仮定において、排中律を用いている(直観論理において、集合が元を含まなければその集合は「空集合」であり、「空集合でない」というのは、この形式的な否定である。これは「元を含まない」という命題よりも弱い)。
分出公理は直観集合論に含められる。
置換公理はエルンスト・ツェルメロの1908年の集合論公理(Z)には含まれていなかった。非公式な類例はカントールの未発表の仕事や、ディミトリー・ミリマノフ(1917)の仕事に見られる。
1922年のアドルフ・フレンケルの置換公理の発表は、現代的な集合論であるツェルメロ-フレンケル集合論 (ZFC) をなすものであった。置換公理は同年、トアルフ・スコーレムによって独立に発見・発表された(そして1923年に出版された)。ツェルメロはフレンケルの公理を自身の公理の改訂版に組み込み、1930年に発表した。この改訂版では新しい公理としてフォン・ノイマンの正則性公理が取り入れられた。 今日使われているのはスコーレムによる一階述語版の公理だが、各公理はツェルメロかフレンケルによるものとされるため、スコーレムの仕事とみなされることは少ない。「ツェルメロ・フレンケル集合論」という用語は、フォン・ノイマンが1928年に書面で初めて用いたものである。
1921年、ツェルメロとフレンケルは密に連絡を取り合っており、置換公理はその主要なトピックであった。 フレンケルはツェルメロと1921年3月に連絡を取り始めた。しかし1921年6月までの彼の手紙はなくなっている。ツェルメロは1921年5月9日のフレンケルへの返信の中で、まず自身の公理系のギャップを認めた。1921年7月10日には、フレンケルは任意の置換を許容する公理を記した論文を完成させ、投稿した(1922年に出版)。公理の内容は以下の通り:「M が集合であり、M の各元が[集合かアトム]で置換されるならば、M はまた集合である(括弧内はハインツ・ディーター・エビングハウスによる)」。フレンケルの1922年の出版では、ツェルメロの助言に謝意を示している。この出版に先立って、フレンケルは自身の新しい公理を1921年9月22日、イェーナで開かれたドイツ数学会の会合で発表した。ツェルメロもこの会合に同席し、フレンケルの公演後の議論で置換公理を大筋認めたが、その程度については表明を留保した。
トアルフ・スコーレムは、1922年7月6日にヘルシンキで開催された the 5th Congress of Scandinavian Mathematicians において、ツェルメロ集合論の(フレンケルが見つけたものと同じ)ギャップの発見を公表した。この会議の抄録は1923年に発行されている。スコーレムは一階述語で定義可能な置換公理に関する解決策を発表した:「U をドメイン B 内の特定の部分 (a, b) で明確に定義できる命題とする。さらに、すべての a について、U が真であるような b が高々1つ存在するとする。すると、a の値域は集合 Ma の元となるため、b の値域は集合 Mb のすべての元にわたる。」同年、フレンケルはスコーレムの論文のレビューを執筆し、そこではフレンケルはスコーレムの考察は自身の理論に対応していると簡潔に述べている。
ツェルメロ自身はスコーレムによる置換公理の定式化を決して認めなかった。 彼は一時期スコーレムの方法を「貧弱な集合論」と表現していた。巨大基数を許容するシステムを想定していたのである。 彼はまた、スコーレムの一階述語公理化から導かれる、スコーレムのパラドックスの哲学的含意にも強く異議を唱えていた。 エビングハウスによるツェルメロの伝記によれば、ツェルメロのスコーレムに対する非難は、集合論や論理学の発展におけるツェルメロの大きな影響力を特徴づけるものであったという。