2020.5.28 离散数学笔记

《离散数学》[1]进入了集合论的学习。我们使用的教材主要是面向工科，对集合的定义还停留在粗浅的阶段。作为数学系的学生，老师带领我们去体会更严谨更深刻的集合定义，故开篇使用教材《数学基础》[2]。
下面梳理一下今天课程学到的知识，大部分整理自老师PPT和课堂教学内容。

引入

什么是集合？

Cantor (1895) A set is a collection of certain distinct objects of our
intuition or of our thought into a whole.

理发师悖论
小城里的理发师放出豪言：他只为，而且一定要为城里所有不为自己刮胡子的人刮胡子。
那么，理发师应该为自己刮胡子吗?

罗素悖论
考虑“由所有集组成的集 $S$ ”. 那么是否有 $S ∈ S$ ?
设 $b =$ { $集a | a\notin a$ }.
现问: 是 $b \in b$ , 还是 $b\notin b$ ?

这里出现一个悖论，故后人修正，提出了ZFC公理系统。

ZF语言

ZF0 (集存在公理)

$∃x(x = x)$

意思是：存在一个集合x/集合是存在的。
这条公埋是为了保证集论论域非空，才能让后面的内容有意义。

Q：为什么要出现 $(x = x)$ ？
A： $(x = x)$ 是一个永真式，当我们用存在语言，需要给一个式子描述，用一个永真式，那么就一定是存在的（老师原话大意）。
我们需要知道大概在干什么就好，不用想的特别特别清楚，如果想不清楚，你最好不要想太多，中间状态很危险。

以下的内容，都需要给定集合，任意给定。

ZF1 (外延公理 the axiom of extensionality)

$∀x(x ∈ a ↔ x ∈ b) → a = b.$

ZF2 (内涵公理 the axiom scheme of comprehension)

设 $s$ 为已知集, 则
$∃y∀x(x ∈ y ↔ x ∈ s ∧ p(x)),$
其中 $p(x)$ 是任一公式, $y$ 不在其中出现.

命题1

内涵公理涉及的 $y$ 是唯一的, 记作
$y = {x | x ∈ s ∧ p(x)}或y = {x ∈ s | p(x)}.$

证明:
利用ZF1即可。假设 $\exists y_1,y_2$ ，可推出它们相等。

ZF2可以避免罗素悖论。

命题

存在唯一的集合 $∅$ , 称为空集, 使得对任意集合 $a$ , 均有 $∅ ⊆ a.$

证明：
存在性证明：
$∀s, ∃!∅s =$ { $x ∈ s | x \not= x$ } $\qquad(1)$
$∀a, b, ∅_a = ∅_b$ $\qquad(2)$
故可 $∅ = ∅_a$ 与集 $a$ 的选取无关.
从而由定义知, $∀a, ∃∅ = ∅_a ⊆ a.$ $\qquad(3)$
唯一性证明：
假设 $∃∅’$ 满足该性质，
则有 $∅’⊆∅$ 和 $∅⊆∅’$ ，
故 $∅=∅’.$

提示：

$(1)$ $(3)$ 由内涵公理得出：
给定一个公式(有点像描述性的语言) $p(x)=x \not= x$ ，一定存在相应的一个集合满足这个性质。
由 $s$ 界定这个集合，这个集合为 $s$ 的子集。
$(2)$ 由外延公理得出：
外延公理中的 $∀x(x ∈ a ↔ x ∈ b) → a = b.$
由于 $x ∈ a$ 和 $x ∈ b$ 是永假式，故 $x ∈ a ↔ x ∈ b$ 是永真式，得到 $a = b.$