フォン・ノイマン＝ベルナイス＝ゲーデル集合論
有限公理化 問題点:ツェルメロは彼の分出公理において、「定値命題関数」の不正確な概念を用いていた。 解決策:スコーレムはのちに ZFC で用いられる分離の公理型を導入し、フレンケルは等価な解決策を用いた。 しかし、ツェルメロは「彼自身の観点では、集合論の土台となる自然数の概念をも暗に巻き込む部分があるため」いずれの方法も拒否した。 フォン・ノイマンは「定値命題関数」の概念を有限個の公理から構築できる関数で定式化することにより、公理型を除外した。これによって、フォン・ノイマンの理論は有限公理化できるようになった。 1961年、リチャード・モンタギューは ZFC が有限公理化できないことを証明した。
正則性公理 問題点:ツェルメロ集合論は空集合と無限集合から議論を始め、対の公理の反復、和集合、冪集合、分出公理、選択公理によって新たな集合を得る。しかし、この集合論では集合をこれらの形に制限していない。例えば、集合 x が x ∈ x を満たすような、整礎でない集合の存在が許容される。 解決策:フレンケルはこうした集合を除外するために公理を導入した。フォン・ノイマンはフレンケルの公理を分析し、「厳密な定式化」がなされていないと大雑把に指摘した:「集合に加えて ... その存在は公理に対して絶対必要になる、これ以上に集合はなく。」 フォン・ノイマンは正則性公理を整楚でない集合を除外する方法として提案したが、ツェルメロ公理系には取り入れられなかった。1930年になって初めて、ツェルメロは正則性公理を取り入れた公理系を発表した。
1929年、フォン・ノイマンは NBG につながる公理を含む論文を発表した。この論文はサイズ制限公理の無矛盾性に対する懸念がきっかけだった。この公理をフォン・ノイマンは「たくさん、実際には多すぎる」と述べている。また、分出公理と置換公理は整列可能定理を含意するほか、濃度が V より小さいどのクラスも集合であることをも含意する。フォン・ノイマンは後者について、カントール集合論を越えたと考え、以下のように結論づけた:「ゆえに(公理の)無矛盾性は、それが問題にならないかだけではなく、必須となるカントールのフレームワークを越えない集合論の公理化となるかを議論しなければならない。」
フォン・ノイマンは無矛盾性の調査を1929年の公理系を導入することで始めた。この公理系はサイズ制限公理以外は1925年の公理系すべてを含む。彼は、サイズ制限公理は、そこから得られる 2 つの結果である、置換公理と選択公理に置き換えた。フォン・ノイマンの選択公理は以下の通り:「どの関係 R も、 R と同じ定義域の写像を部分クラスとしてもつ。」
S をフォン・ノイマンの1929年の公理系とする。フォン・ノイマンは公理系 S + Regularity (S と正則性公理からなる)を導入し、自身の1925年の公理系が S と相対的に無矛盾であることを示した。また、以下を証明した:
S が無矛盾であれば、 S + Regularity は無矛盾である。
組の補題の言明 4 を P {\displaystyle P} に適用することで、 x i ∈ x j {\displaystyle x_{i}\in x_{j}} を満たすすべての順序対 ( x j , x i ) {\displaystyle (x_{j},x_{i})} を含むクラス P ′ {\displaystyle P'} を生成する。拡大の公理を P ′ {\displaystyle P'} に適用することで、 E i , j , n = { ( x 1 , ... , x n ) : x i ∈ x j } {\displaystyle E_{i,j,n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in x_{j}\}} を得る。
Case c: φ {\displaystyle \phi } が x i ∈ x j {\displaystyle x_{i}\in x_{j}} ( i = j {\displaystyle i=j} )のとき、正則性の公理よりこの論理式は偽であるため、これを満たす n {\displaystyle n} -組は存在せず、ゆえに E i , j , n = ∅ {\displaystyle E_{i,j,n}=\emptyset } である。
Case 2: φ {\displaystyle \phi } が x i ∈ Y k {\displaystyle x_{i}\in Y_{k}} のとき、 x i ∈ Y k . {\displaystyle x_{i}\in Y_{k}.
, x j − 1 {\displaystyle x_{i+1},\dots ,x_{j-1}} を一つずつ追加する。この操作により、 R ( x i , x j ) . {\displaystyle R(x_{i},x_{j}).} を満たすすべての j {\displaystyle j} -組 ( ( ( ⋯ ( ( x 1 , ... , x i ) , x i + 1 ) , ⋯ ) , x j − 1 ) , x j ) = ( x 1 , ... , x j ) {\displaystyle (((\cdots ((x_{1},\dots ,x_{i}),x_{i+1}),\cdots ),x_{j-1}),x_{j})=(x_{1},\dots ,x_{j})} を含むクラス P 2 {\displaystyle P_{2}} が生成される。
j = n {\displaystyle j=n} のとき、 P 3 = P 2 {\displaystyle P_{3}=P_{2}} とする。 j < n {\displaystyle j<n} のとき、 x j {\displaystyle x_{j}} のあとに成分が追加される:組の補題の言明 3 を用いて x j + 1 , ... , x n {\displaystyle x_{j+1},\dots ,x_{n}} を一つずつ追加する。この操作により、 R ( x i , x j ) . {\displaystyle R(x_{i},x_{j}).} を満たすすべての n {\displaystyle n} -組 ( ( ⋯ ( ( x 1 , ...
, x n ) : x i ∈ x j } {\displaystyle E_{i,j,n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in x_{j}\}} を構成する。
Case a: φ {\displaystyle \phi } が x i ∈ x j {\displaystyle x_{i}\in x_{j}} ( i < j {\displaystyle i<j} )のとき、帰属の公理より、 x i ∈ x j {\displaystyle x_{i}\in x_{j}} を満たすすべての順序対 ( x i , x j ) {\displaystyle (x_{i},x_{j})} を含むクラス P {\displaystyle P} を生成する。拡張の補題を P {\displaystyle P} に適用することで、 E i , j , n = { ( x 1 , ... , x n ) : x i ∈ x j } {\displaystyle E_{i,j,n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in x_{j}\}} を得る。
Case b: φ {\displaystyle \phi } が x i ∈ x j {\displaystyle x_{i}\in x_{j}} ( i > j {\displaystyle i>j} )のとき、帰属の公理より、 x i ∈ x j {\displaystyle x_{i}\in x_{j}} を満たすすべての順序対 ( x i , x j ) {\displaystyle (x_{i},x_{j})} を含むクラス P {\displaystyle P} を生成する。
Case 2: φ ( x 1 , ... , x n , Y → ) = ψ 1 ( x 1 , ... , x n , Y → ) ∧ ψ 2 ( x 1 , ... , x n , Y → ) {\displaystyle \phi (x_{1},\ldots ,x_{n},{\vec {Y}})=\psi _{1}(x_{1},\ldots ,x_{n},{\vec {Y}})\land \psi _{2}(x_{1},\ldots ,x_{n},{\vec {Y}})} のとき、 ψ 1 {\displaystyle \psi _{1}} と ψ 2 {\displaystyle \psi _{2}} はいずれも k {\displaystyle k} 未満の個数の論理記号を含むため、帰納仮説は以下を満たす n {\displaystyle n} -組のクラス A {\displaystyle A} がただ一つ存在することを含意する:
( x 1 , ... , x n ) ∈ A 1 ⟺ ψ 1 ( x 1 , ... , x n , Y → ) . ( x 1 , ... , x n ) ∈ A 2 ⟺ ψ 2 ( x 1 , ... , x n , Y → ) . {\displaystyle {\begin{aligned}\quad &(x_{1},\ldots ,x_{n})\in A_{1}\iff \psi _{1}(x_{1},\ldots ,x_{n},{\vec {Y}}).\\&(x_{1},\ldots ,x_{n})\in A_{2}\iff \psi _{2}(x_{1},\ldots ,x_{n},{\vec {Y}}).\end{aligned}}}
Y k ∈ Γ {\displaystyle \,Y_{k}\in \Gamma } を ∃ z i ( z i = Y k ∧ z i ∈ Γ ) {\displaystyle \exists z_{i}(z_{i}=Y_{k}\,\land \,z_{i}\in \Gamma )} に変換する。
外延性公理を用いて、 Δ = Γ {\displaystyle \Delta =\Gamma } を ∀ z i ( z i ∈ Δ ⟺ z i ∈ Γ ) {\displaystyle \forall z_{i}(z_{i}\in \Delta \iff z_{i}\in \Gamma )} に変換する。
論理的同一性を用いて、 ∨ , ⟹ , ⟺ , {\displaystyle \lor ,\implies ,\iff ,} and ∀ {\displaystyle \forall } が含まれるサブ論理式を ¬ , ∧ , ∃ {\displaystyle \neg ,\land ,\exists } のみが含まれるサブ論理式に変換する。
変換規則:束縛変数. 例 1の合成関数論理式について、集合の自由変数を x 1 {\displaystyle x_{1}} と x 2 {\displaystyle x_{2}} に置き換えることを考える: ∃ t [ ( x 1 , t ) ∈ F ∧ ( t , x 2 ) ∈ G ] {\displaystyle \exists t[(x_{1},t)\in F\,\land \,(t,x_{2})\in G]} 。