出典: フリー百科事典『ウィキペディア(Wikipedia)』
正則性公理 (せいそくせいこうり、英 : 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公理系 の他の公理の元で同値であり、どれを正則性公理 として採用しても差し支えない[ 1] 。
∀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 }
^ Kunen 1980 , p. 101, Ⅲ, §4.1