查看“︁Levy 层次结构”︁的源代码

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

=== 定义 ===
我们将 [[ZFC公理体系|ZFC 集合论]]所讨论的一阶公式进行以下的分层：

* <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> )。

我们说一个性质(类，关系)是 <math>\Pi_{n}/\Sigma_{n}</math> 的，当且仅当它可以被表示成一个 <math>\Pi_{n}/\Sigma_{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> 。

=== 引理 ===
当 <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> 的。
# 如果 <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> 的[[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>\Delta_0</math> 和 <math>\Delta_1</math> 公式具有'''绝对性'''，这是在说，任一 <math>\Delta_0</math> 或 <math>\Delta_1</math> 公式在不同的传递模型之间的真值是等同的。

=== <math>\Sigma_{n}</math> 初等嵌入 ===
我们说一个[[模型]] <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> 公式。

[[分类:集合论相关]]