Levy 层次结构：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年7月20日 (日) 23:38的版本

Levy 层次结构，是一阶集合论语言中运用复杂度对公式进行分类的一种方式。

定义

我们将ZFC集合论所讨论的一阶公式进行以下的分层：

$Δ_{0} / Π_{0} / Σ_{0}$ 公式：一个拥有的量词唯一且是有界的公式。
$Σ_{n + 1}$ 公式：可以写成 $\exists x φ$ 的形式，当 $φ$ 为 $Π_{n}$ 公式 (可以推广到任意有限多个 $\exists x$ )。
$Π_{n + 1}$ 公式：可以写成 $\forall x φ$ 的形式，当 $φ$ 是 $Σ_{n}$ 公式 (可以推广到任意有限多个 $\forall x$ )。

我们说一个性质(类，关系)是 $Π_{n} / Σ_{n}$ 的，当且仅当它可以被表示成一个 $Π_{n} / Σ_{n}$ 公式。

一个函数 $F$ 是 $Σ_{n} / Π_{n}$ 的当且仅当关系 $y = F (x)$ 是 $Σ_{n} / Π_{n}$ 的。

一个公式是 $Δ_{n}$ 的当且仅当它即是 $Π_{n}$ 又是 $Σ_{n}$ 。

引理

当 $n \leq 1$ 时，

如果 $P, Q$ 是 $Σ_{n}$ 性质，则 $\exists x P, P \land Q, P \lor Q, (\exists u \in x) P, (\forall u \in x) P$ 都是 $Σ_{n}$ 的。
如果 $P, Q$ 是 $Π_{n}$ 性质，则 $\forall x P, P \land Q, P \lor Q, (\exists u \in x) P, (\forall u \in x) P$ 都是 $Π_{n}$ 的。
如果 $P$ 是 $Σ_{n}$ 的，那么 $P$ 的反命题是 $Π_{n}$ 的，如果 $P$ 是 $Π_{n}$ 的， $P$ 的反命题是 $Σ_{n}$ 的。
如果 $P$ 是 $Π_{n}$ 且 $Q$ 是 $Σ_{n}$ 公式，则 $P \to Q$ 是 $Σ_{n}$ 公式， $P$ 为 $Σ_{n}$ 且 $Q$ 为 $Π_{n}$ 的情况下， $P \to Q$ 是 $Π_{n}$ 公式。
如果 $P, Q$ 都是 $Δ_{n}$ 的，那么 $P$ 的反命题 $, P \land Q, P \lor Q, P \to Q, P \Leftrightarrow Q, (\forall u \in x) P, (\exists u \in x) P$ 也都是 $Δ_{n}$ 。
如果 $F$ 是一个 $Σ_{n}$ 函数，则 $F$ 的定义域是一个 $Σ_{n}$ 类。
如果 $F$ 是一个 $Σ_{n}$ 函数且 $F$ 的定义域是 $Δ_{n}$ 的， $F$ 也是 $Δ_{n}$ 的。
如果 $F, G$ 都是 $Σ_{n}$ 函数，它们的复合函数也是 $Σ_{n}$ 函数。
让 $F$ 是 $Σ_{n}$ 函数且 $P$ 是 $Σ_{n}$ 性质，则 $P (F (x))$ 是 $Σ_{n}$ 的。

对于传递模型， $Δ_{0}$ 和 $Δ_{1}$ 公式具有绝对性，这是在说，任一 $Δ_{0}$ 或 $Δ_{1}$ 公式在不同的传递模型之间的真值是等同的。

$Σ_{n}$ 初等嵌入

我们说一个模型 $(M, \in) Σ_{n}$ 初等嵌入于模型 $(N, \in)$ ，当且仅当， $M \subset N$ 且 $M$ 和 $N$ 满足同样的 $Σ_{n}$ 公式。

@@ 第1行： / 第1行： @@
-我们将ZFC集合论所讨论的一阶公式进行以下的分层
+'''Levy 层次结构'''，是一阶集合论语言中运用复杂度对公式进行分类的一种方式。
-Δ0/Π0/∑0公式：一个拥有的量词唯一且是有界的公式
+== 定义 ==
-∑n+1公式：可以写成∃xφ的形式，当φ为Πn公式（可以推广到任意有限多个∃x）
+我们将[[ZFC公理体系|ZFC集合论]]所讨论的一阶公式进行以下的分层：
-Πn+1公式：可以写成∀xφ的形式，当φ是∑n公式（可以推广到任意有限多个∀x）
+* <math>\Delta_0/\Pi_0/\Sigma_0</math> 公式：一个拥有的量词唯一且是有界的公式。
+* <math>\Sigma_{n+1}</math> 公式：可以写成 <math>\exist x\varphi</math> 的形式，当 <math>\varphi</math> 为 <math>\Pi_{n}</math> 公式 (可以推广到任意有限多个 <math>\exist x</math> )。
+* <math>\Pi_{n+1}</math> 公式：可以写成 <math>\forall x\varphi</math> 的形式，当 <math>\varphi</math> 是 <math>\Sigma_{n}</math> 公式 (可以推广到任意有限多个 <math>\forall x</math> )。
-我们说一个性质（类，关系）是Πn/∑n的，当且仅当它可以被表示成一个Πn/∑n公式
+我们说一个性质(类，关系)是 <math>\Pi_{n}/\Sigma_{n}</math> 的，当且仅当它可以被表示成一个 <math>\Pi_{n}/\Sigma_{n}</math> 公式。
-一个函数F是∑n/Πn的当且仅当关系y=F（x）是∑n/Πn的
+一个函数 <math>F</math> 是 <math>\Sigma_{n}/\Pi_{n}</math> 的当且仅当关系 <math>y=F(x)</math> 是 <math>\Sigma_{n}/\Pi_{n}</math> 的。
-一个公式是Δn的当且仅当它即是Πn又是∑n
+一个公式是 <math>\Delta_{n}</math> 的当且仅当它即是 <math>\Pi_{n}</math> 又是 <math>\Sigma_{n}</math> 。
-引理：当n≥1
+== 引理 ==
-.如果P，Q是∑n性质，则∃xP，P∧Q，P∨Q，（∃u∈x）P，（∀u∈x）P都是∑n的
+当 <math>n\leq 1</math> 时，
+# 如果 <math>P,Q</math> 是 <math>\Sigma_{n}</math> 性质，则 <math>\exist xP,P\and Q,P\or Q,(\exist u\in x)P,(\forall u\in x)P</math> 都是 <math>\Sigma_{n}</math> 的。
+# 如果 <math>P,Q</math> 是 <math>\Pi_{n}</math> 性质，则 <math>\forall xP,P\and Q,P\or Q,(\exist u\in x)P,(\forall u\in x)P</math> 都是 <math>\Pi_{n}</math> 的。
+# 如果 <math>P</math> 是 <math>\Sigma_{n}</math> 的，那么 <math>P</math> 的反命题是 <math>\Pi_{n}</math> 的，如果 <math>P</math> 是 <math>\Pi_{n}</math> 的， <math>P</math> 的反命题是 <math>\Sigma_{n}</math> 的。
+# 如果 <math>P</math> 是 <math>\Pi_{n}</math> 且 <math>Q</math> 是 <math>\Sigma_{n}</math> 公式，则 <math>P\rightarrow Q</math> 是 <math>\Sigma_{n}</math> 公式， <math>P</math> 为 <math>\Sigma_{n}</math> 且 <math>Q</math> 为 <math>\Pi_{n}</math> 的情况下， <math>P\rightarrow Q</math> 是 <math>\Pi_{n}</math> 公式。
+# 如果 <math>P,Q</math> 都是 <math>\Delta_{n}</math> 的，那么 <math>P</math> 的反命题 <math>,P\and Q,P\or Q,P\rightarrow Q,P\Leftrightarrow Q,(\forall u\in x)P,(\exist u\in x)P</math> 也都是 <math>\Delta_{n}</math> 。
+# 如果 <math>F</math> 是一个 <math>\Sigma_{n}</math> 函数，则 <math>F</math> 的定义域是一个 <math>\Sigma_{n}</math> 类。
+# 如果 <math>F</math> 是一个 <math>\Sigma_{n}</math> 函数且 <math>F</math> 的定义域是 <math>\Delta_{n}</math> 的， <math>F</math> 也是 <math>\Delta_{n}</math> 的。
+# 如果 <math>F,G</math> 都是 <math>\Sigma_{n}</math> 函数，它们的复合函数也是 <math>\Sigma_{n}</math> 函数。
+# 让 <math>F</math> 是 <math>\Sigma_{n}</math> 函数且 <math>P</math> 是 <math>\Sigma_{n}</math> 性质，则 <math>P(F(x))</math> 是 <math>\Sigma_{n}</math> 的。
-.如果P，Q是Πn性质，则∀xP，P∧Q，P∨Q，（∃u∈x）P，（∀u∈x）P都是Πn的
+对于传递模型， <math>\Delta_0</math> 和 <math>\Delta_1</math> 公式具有'''绝对性'''，这是在说，任一 <math>\Delta_0</math> 或 <math>\Delta_1</math> 公式在不同的传递模型之间的真值是等同的。
+== <math>\Sigma_{n}</math> 初等嵌入 ==
-.如果P是∑n的，那么P的反命题是Πn的，如果P是Πn的，P的反命题是∑n的
+我们说一个[[模型]] <math>(M,\in )\Sigma_{n}</math> [[模型#子模型|初等嵌入]]于模型 <math>(N,\in )</math> ，当且仅当， <math>M\subset N</math> 且 <math>M</math> 和 <math>N</math> 满足同样的 <math>\Sigma_{n}</math> 公式。
-.如果P是Πn且Q是∑n公式，则P→Q是∑n公式，P为∑n且Q为Πn的情况下，P→Q是Πn公式
-.如果PQ都是Δn的，那么P的反，P∧Q，P∨Q，P→Q，P⇔Q，（∀u∈x）P，（∃u∈x）P也都是Δn
-.如果F是一个∑n函数，则F的定义域是一个∑n类
-.如果F是一个∑n函数且F的定义域是Δn的，F也是Δn的
-.如果F，G都是∑n函数，它们的复合函数也是∑n函数
-.让F是∑n函数且P是∑n性质，则P（F（x））是∑n的
-对于传递模型，Δ0和Δ1公式具有绝对性，这是再说，任一Δ0或Δ1公式在不同的传递模型之间的真值是等同的
-我们接着定义∑n初等嵌入
-我们说一个模型（M，∈）∑n初等嵌入于模型（N，∈），当且仅当，M⊂N且M和N满足同样的∑n公式

2025年7月20日 (日) 23:38的版本

定义

引理

Σn 初等嵌入

$Σ_{n}$ 初等嵌入