Levy 层次结构：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年7月27日 (日) 16:42的版本

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 \geq 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}$ 公式。

@@ 第11行： / 第11行： @@
 我们说一个性质(类，关系)是 <math>\Pi_{n}/\Sigma_{n}</math> 的，当且仅当它可以被表示成一个 <math>\Pi_{n}/\Sigma_{n}</math> 公式。
-一个函数 <math>F</math> 是 <math>\Sigma_{n}/\Pi_{n}</math> 的当且仅当关系 <math>y=F(x)</math> 是 <math>\Sigma_{n}/\Pi_{n}</math> 的。
+一个[[ZFC公理体系#函数|函数]] <math>F</math> 是 <math>\Sigma_{n}/\Pi_{n}</math> 的当且仅当关系 <math>y=F(x)</math> 是 <math>\Sigma_{n}/\Pi_{n}</math> 的。
 一个公式是 <math>\Delta_{n}</math> 的当且仅当它即是 <math>\Pi_{n}</math> 又是 <math>\Sigma_{n}</math> 。
@@ 第17行： / 第17行： @@
 == 引理 ==
-当 <math>n\leq 1</math> 时，
+当 <math>n\geq 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> 的。
@@ 第23行： / 第23行： @@
 # 如果 <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> 的[[ZFC公理体系#定义域|定义域]]是一个 <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> 的。
+# 如果 <math>F</math> 是 <math>\Sigma_{n}</math> 函数且 <math>P</math> 是 <math>\Sigma_{n}</math> 性质，则 <math>P(F(x))</math> 是 <math>\Sigma_{n}</math> 的。
-对于传递模型， <math>\Delta_0</math> 和 <math>\Delta_1</math> 公式具有'''绝对性'''，这是在说，任一 <math>\Delta_0</math> 或 <math>\Delta_1</math> 公式在不同的传递模型之间的真值是等同的。
+对于[[传递模型]]， <math>\Delta_0</math> 和 <math>\Delta_1</math> 公式具有'''绝对性'''，这是在说，任一 <math>\Delta_0</math> 或 <math>\Delta_1</math> 公式在不同的传递模型之间的真值是等同的。
 == <math>\Sigma_{n}</math> 初等嵌入 ==

2025年7月27日 (日) 16:42的版本

定义

引理

Σn 初等嵌入

$Σ_{n}$ 初等嵌入