Levy 层次结构

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

定义

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

• ${\mathrm{\Delta }}_0/{\mathrm{\Pi }}_0/{\mathrm{\Sigma }}_0$ 公式：一个拥有的量词唯一且是有界的公式。
• ${\mathrm{\Sigma }}_{n+1}$ 公式：可以写成 $\mathrm{\exists }x\phi$ 的形式，当 $\phi$ 为 ${\mathrm{\Pi }}_n$ 公式 (可以推广到任意有限多个 $\mathrm{\exists }x$ )。
• ${\mathrm{\Pi }}_{n+1}$ 公式：可以写成 $\mathrm{\forall }x\phi$ 的形式，当 $\phi$ 是 ${\mathrm{\Sigma }}_n$ 公式 (可以推广到任意有限多个 $\mathrm{\forall }x$ )。

我们说一个性质(类，关系)是 ${\mathrm{\Pi }}_n/{\mathrm{\Sigma }}_n$ 的，当且仅当它可以被表示成一个 ${\mathrm{\Pi }}_n/{\mathrm{\Sigma }}_n$ 公式。

一个函数 $F$ 是 ${\mathrm{\Sigma }}_n/{\mathrm{\Pi }}_n$ 的当且仅当关系 $y=F(x)$ 是 ${\mathrm{\Sigma }}_n/{\mathrm{\Pi }}_n$ 的。

一个公式是 ${\mathrm{\Delta }}_n$ 的当且仅当它即是 ${\mathrm{\Pi }}_n$ 又是 ${\mathrm{\Sigma }}_n$ 。

引理

当 $n\ge 1$ 时，

1. 如果 $P,Q$ 是 ${\mathrm{\Sigma }}_n$ 性质，则 $\mathrm{\exists }xP,P\wedge Q,P\vee Q,(\mathrm{\exists }u\in x)P,(\mathrm{\forall }u\in x)P$ 都是 ${\mathrm{\Sigma }}_n$ 的。
2. 如果 $P,Q$ 是 ${\mathrm{\Pi }}_n$ 性质，则 $\mathrm{\forall }xP,P\wedge Q,P\vee Q,(\mathrm{\exists }u\in x)P,(\mathrm{\forall }u\in x)P$ 都是 ${\mathrm{\Pi }}_n$ 的。
3. 如果 $P$ 是 ${\mathrm{\Sigma }}_n$ 的，那么 $P$ 的反命题是 ${\mathrm{\Pi }}_n$ 的，如果 $P$ 是 ${\mathrm{\Pi }}_n$ 的， $P$ 的反命题是 ${\mathrm{\Sigma }}_n$ 的。
4. 如果 $P$ 是 ${\mathrm{\Pi }}_n$ 且 $Q$ 是 ${\mathrm{\Sigma }}_n$ 公式，则 $P\to Q$ 是 ${\mathrm{\Sigma }}_n$ 公式， $P$ 为 ${\mathrm{\Sigma }}_n$ 且 $Q$ 为 ${\mathrm{\Pi }}_n$ 的情况下， $P\to Q$ 是 ${\mathrm{\Pi }}_n$ 公式。
5. 如果 $P,Q$ 都是 ${\mathrm{\Delta }}_n$ 的，那么 $P$ 的反命题 $,P\wedge Q,P\vee Q,P\to Q,P\iff Q,(\mathrm{\forall }u\in x)P,(\mathrm{\exists }u\in x)P$ 也都是 ${\mathrm{\Delta }}_n$ 。
6. 如果 $F$ 是一个 ${\mathrm{\Sigma }}_n$ 函数，则 $F$ 的定义域是一个 ${\mathrm{\Sigma }}_n$ 类。
7. 如果 $F$ 是一个 ${\mathrm{\Sigma }}_n$ 函数且 $F$ 的定义域是 ${\mathrm{\Delta }}_n$ 的， $F$ 也是 ${\mathrm{\Delta }}_n$ 的。
8. 如果 $F,G$ 都是 ${\mathrm{\Sigma }}_n$ 函数，它们的复合函数也是 ${\mathrm{\Sigma }}_n$ 函数。
9. 如果 $F$ 是 ${\mathrm{\Sigma }}_n$ 函数且 $P$ 是 ${\mathrm{\Sigma }}_n$ 性质，则 $P(F(x))$ 是 ${\mathrm{\Sigma }}_n$ 的。

对于传递模型， ${\mathrm{\Delta }}_0$ 和 ${\mathrm{\Delta }}_1$ 公式具有绝对性，这是在说，任一 ${\mathrm{\Delta }}_0$ 或 ${\mathrm{\Delta }}_1$ 公式在不同的传递模型之间的真值是等同的。

${\mathrm{\Sigma }}_n$ 初等嵌入

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