正則性公理

正則性公理（せいそくせいこうり、英: axiom of regularity）は、別名「基礎の公理」（きそのこうり、英: axiom of foundation） とも呼ばれ、ZF公理系を構成する公理の一つで、1925年にジョン・フォン・ノイマンによって導入された。選択公理と同様、様々な同値な命題が存在する。 空でない集合は必ず自分自身と交わらない要素を持つ。 ∀ A ( A ≠ ∅ ⟹ ∃ x ∈ A , ∀ t ∈ A ( t ∉ x ) ) {\displaystyle \forall A{\bigl (}A\neq \varnothing \implies \exists x\in A,\forall t\in A(t\notin x){\bigr )}} 以下の3つの主張はいずれもZF公理系の他の公理の元で同値であり、どれを正則性公理として採用しても差し支えない。 ∀x ≠ ∅ に対して、∃y∈x; x ∩ y = ∅ ∀xについて、∈ が x 上整礎関係 V = WF ここで、V は集合論の宇宙を指し、WF は整礎的集合全体のクラス（フォン・ノイマン宇宙）を指す。 ZF公理系内に限って話を進める。各順序数 α に対して R(α) を次のように定義する（ P {\displaystyle {\mathcal {P}}} は冪集合）。 R ( 0 ) = ∅ {\displaystyle R(0)=\varnothing } R ( α + 1 ) = P ( R ( α ) ) {\displaystyle R(\alpha +1)={\mathcal {P}}(R(\alpha ))} α が極限順序数のとき、 R ( α ) = ⋃ β < α R ( β ) {\displaystyle R(\alpha )=\bigcup _{\beta <\alpha }R(\beta )} クラス WF はこれらを全て集めたものとして定義される。 W F = ⋃ α ∈ O N R ( α ) {\displaystyle {\mathit {WF}}=\bigcup _{\alpha \in {\mathit {ON}}}R(\alpha )} ZF公理系の他の公理から得られる種々の集合演算(対集合、和集合、冪集合) の結果としての集合は常に WF 内に含まれる。すなわち V = WF の仮定は、全ての集合を ∅ に通常の集合演算を施すことによって得られるものだけに制限することを主張している。したがって、例えばx = {x}のような集合やx ∈ yかつy∈ xなる集合は正則性の公理の下では集合にはなり得ない。 定理 ―  任意の α ∈ ON に対して、 R ( α ) {\displaystyle R(\alpha )} は推移的 ∀ β ≤ α ; R ( β ) ⊆ R ( α ) {\displaystyle \forall \beta \leq \alpha ;R(\beta )\subseteq R(\alpha )} 証明 — 超限帰納法による。α = 0 のときは明らかである。∀β < α に対して成り立っていると仮定する。α = β + 1 のとき、仮定より R(β) は推移的であり、 R ( α ) = P ( R ( β ) ) {\displaystyle R(\alpha )={\mathcal {P}}(R(\beta ))} も推移的になる。また、 R ( β ) ⊂ P ( R ( β ) ) = R ( α ) {\displaystyle R(\beta )\subset {\mathcal {P}}(R(\beta ))=R(\alpha )} となる。α が極限順序数のとき、仮定より ∀β < α に対して R(β) は推移的であり推移的集合の和集合が推移的になることにより R ( α ) = ⋃ β < α R ( β ) {\displaystyle R(\alpha )=\bigcup _{\beta <\alpha }R(\beta )} も推移的になる。さらに ∀ β < α ; R ( β ) ⊂ ⋃ β < α R ( β ) = R ( α ) {\displaystyle \forall \beta <\alpha ;R(\beta )\subset \bigcup _{\beta <\alpha }R(\beta )=R(\alpha )} も同様。 WF の定義より、x ∈ WF のとき、x ∈ R(α) を満たす最小の順序数 α は後続順序数になる。実際、α を極限順序数として x ∈ R(α) 及び ∀β < α, x ∉ R(β) が成り立っているとすると、 x ∉ ⋃ β < α R ( β ) = R ( α ) {\displaystyle x\notin \bigcup _{\beta <\alpha }R(\beta )=R(\alpha )} となって矛盾する。 そこで、集合 x のランクを次のように定義する。 x ∈ WF のとき、x ∈ R(β + 1) を満たす最小の β を集合 x のランクといい、rank(x) で表す。 よって、rank(x) = β ならば ∀ α > β ; x ∈ R ( α ) {\displaystyle \forall \alpha >\beta ;x\in R(\alpha )} が成り立ち、x ∈ R(β) かつ x ⊂ R(β) となる。また、このランクの概念を用いて R(α) は次のように特徴付けられる。 ∀ α ; R ( α ) = { x ∈ W F ∣ rank ⁡ ( x ) < α } {\displaystyle \forall \alpha ;R(\alpha )=\{x\in {\mathit {WF}}\mid \operatorname {rank} (x)<\alpha \}} 及び、 ∀ x ∈ W F ( rank ⁡ ( x ) < α ⟺ ∃ β < α ; x ∈ R ( β + 1 ) ⟺ x ∈ R ( α ) ) {\displaystyle \forall x\in {\mathit {WF}}{\bigl (}\operatorname {rank} (x)<\alpha \iff \exists \beta <\alpha ;x\in R(\beta +1)\iff x\in R(\alpha ){\bigr )}} ランクを計算するときに次の補題を使う。 y ∈ W F {\displaystyle y\in {\mathit {WF}}} のとき、 x ∈ y ⟹ x ∈ W F {\displaystyle x\in y\implies x\in {\mathit {WF}}} かつ rank ⁡ ( x ) < rank ⁡ ( y ) {\displaystyle \operatorname {rank} (x)<\operatorname {rank} (y)} rank ⁡ ( y ) = α {\displaystyle \operatorname {rank} (y)=\alpha } とすると y ∈ R ( α + 1 ) = P ( R ( α ) ) {\displaystyle y\in R(\alpha +1)={\mathcal {P}}(R(\alpha ))} x ∈ y {\displaystyle x\in y} ならば x ∈ R ( α ) = { x ∈ W F ∣ rank ⁡ ( x ) < α } {\displaystyle x\in R(\alpha )=\{x\in {\mathit {WF}}\mid \operatorname {rank} (x)<\alpha \}} だから rank ⁡ ( x ) < α {\displaystyle \operatorname {rank} (x)<\alpha }