离散数学/Zermelo-Frankel公理

简介

Zermelo-Fraenkel集合论，包括选择公理，通常缩写为ZFC，是公理化集合论的标准形式，因此也是数学最常见的基石。

ZFC包含一个原始概念，即集合，以及一个假设，即所有数学对象都是集合。存在一个原始二元关系，即集合成员关系；集合a是集合b的成员，记为$a\in b$ （通常读作“a是b的元素”或“a在b中”）。ZFC的公理规定了集合的行为和相互作用。

公理

1. 外延公理：两个集合相等（是同一个集合）当且仅当它们具有相同的元素。

$\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y].$

此公理的逆命题来自等式的替换性质。如果背景逻辑不包括等式“=”，则x=y可以定义为缩写∀z[z∈x↔z∈y] ∧ ∀z[x∈z↔y∈z]，在这种情况下，该公理可以重新表述为$\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow \forall z(x\in z\Leftrightarrow y\in z)]$ — 如果x和y具有相同的元素，则它们属于相同的集合。

2. 正则公理（也称为基础公理）：每个非空集合x包含一个成员y，使得x和y是不相交的集合。

$\forall x[\exists y(y\in x)\Rightarrow \exists y(y\in x\land \lnot \exists z(z\in y\land z\in x))].$

3. 规格化公理模式（也称为分离公理模式或受限理解公理模式）：如果z是一个集合，并且$\phi \!$ 是任何可以刻画z的元素x的性质，则存在z的一个子集y，包含满足该性质的z中的x。更正式地说

$\forall z\forall w_{1}\ldots w_{n}\exists y\forall x[x\in y\Leftrightarrow (x\in z\land \phi )].$

规格化公理可以用来证明空集的存在，记为$\varnothing$，一旦建立了至少存在一个集合（见上文）。一个常见的做法是使用规格化公理的某个实例来表示所有集合都不具有的性质。例如，如果w是已经存在的集合，则空集可以构建为

$\varnothing =\{u\in w\mid (u\in u)\land \lnot (u\in u)\}$.

如果背景逻辑包含等式，则也可以将空集定义为

$\varnothing =\{u\in w\mid \lnot (u=u)\}$.

因此，空集公理可以从这里提出的九个公理推导出来。外延公理意味着空集是唯一的，如果它存在的话。通常会进行定义上的扩展，将符号 $\varnothing$ 添加到 ZFC 的语言中。

4. 配对公理： 如果 *x* 和 *y* 是集合，那么存在一个包含 *x* 和 *y* 作为元素的集合。

$\forall x\forall y\exists z(x\in z\land y\in z).$

5. 并集公理： 对于任何集合 ${\mathcal {F}}$，存在一个集合 *A*，它包含 ${\mathcal {F}}$ 的每个成员的每一个元素。

$\forall {\mathcal {F}}\,\exists A\,\forall Y\,\forall x(x\in Y\land Y\in {\mathcal {F}}\Rightarrow x\in A).$

6. 集合替换公理模式： 这个公理指出，如果一个函数 *f* 的定义域是一个集合，并且 *f*(*x*) 是定义域中任何 *x* 的一个集合，那么 *f* 的值域是一个集合的子类，受限于避免悖论所需的限制。

7. 无穷公理： 设 $S(x)\!$ 简写 $x\cup \{x\}\!$，其中 $x\!$ 是某个集合。那么存在一个集合 *X*，使得空集 $\varnothing$ 是 *X* 的成员，并且，当一个集合 *y* 是 *X* 的成员时，$S(y)\!$ 也是 *X* 的成员。

$\exists X\left[\varnothing \in X\land \forall y(y\in X\Rightarrow S(y)\in X)\right].$

更通俗地说，存在一个具有无限多成员的集合 *X*。

8. 幂集公理： 设 $z\subseteq x$ 简写 $\forall q(q\in z\Rightarrow q\in x).$ 对于任何集合 *x*，存在一个集合 *y*，它是一个包含 *x* 的幂集的超集。*x* 的幂集是所有 *x* 的所有可能的子集的类。

$\forall x\exists y\forall z[z\subseteq x\Rightarrow z\in y].$

公理 **1–8** 的另一种形式经常被使用。一些 ZF 公理化系统包括一个公理断言空集的存在。配对、并集、替换和幂集的公理通常被表述为，集合 *x* 的成员的存在被断言，仅仅是那些公理断言 *x* 必须包含的集合。

**9. 良序定理：**对于任何集合 *X*，存在一个良序 *X* 的二元关系 *R*。这意味着 *R* 是 *X* 上的一个线性序，使得 *X* 的每个非空子集都有一个关于 *R* 最小的成员。

$\forall X\exists R(R\;{\mbox{well-orders}}\;X).$

给定公理 **1-8**，有许多与公理 **9** 等价的命题，其中最著名的是选择公理（AC），内容如下。设 *X* 是一个集合，它的成员都是非空的。那么存在一个函数 *f*，称为“选择函数”，它的定义域是 *X*，它的值域是一个集合，称为“选择集”，它的每个成员都是 *X* 中每个成员的单个成员。由于当 *X* 是一个有限集时，选择函数的存在很容易从公理 **1-8** 中证明出来，所以 AC 仅仅对某些无限集有效。AC 的特点是非构造性的，因为它断言选择集的存在，但没有说明选择集是如何被“构造”的。许多研究试图描述由 AC 断言存在的某些集合的可定义性（或不可定义性）。