Set 与 membership

Set 是由互不相同的对象组成的集合，其中的对象称为 element 或 member。我们用花括号把元素括起来，例如 $\{1,2,3\}$。

例：判断 membership

设

$$A=\{1,2,3\}.$$

$\in$ 是 membership symbol。$x\in A$ 读作“$x$ 是 $A$ 的一个元素”。$\notin$ 是 non-membership symbol，表示“不属于”。因此，

$$1\in A \qquad\text{and}\qquad 4\notin A.$$

Empty set

Empty set 是不含任何元素的集合，记作 $\varnothing$，也可以用空花括号表示：

$$\varnothing=\{\}.$$

Empty set 没有元素，所以对任意对象 $x$ 都有 $x\notin\varnothing$。特别地，

$$\varnothing\notin\varnothing.$$

也就是说，empty set 不是它自身的元素。它与 $\{\varnothing\}$ 不同：后者含有一个元素，这个元素就是 empty set：

$$\varnothing\in\{\varnothing\}.$$

Subset 与 set inclusion

$\subseteq$ 是 subset symbol。

$$A\subseteq B$$

读作“$A$ 是 $B$ 的 subset”，或“$A$ 包含于 $B$”。这种关系称为 set inclusion，意思是：$A$ 的每个元素也都是 $B$ 的元素。

这里允许两个集合相等，因此每个集合都是它自身的 subset：

$$A\subseteq A.$$

Proper subset 则要求至少少一个元素。符号 $\subset$ 在本笔记中表示“是真子集”。

$$A\subset B$$

读作“$A$ 是 $B$ 的 proper subset”。这要求 $A\subseteq B$，同时 $A\neq B$，也就是两个集合不能相等。

你也可能看到 $A\subsetneq B$。$\subsetneq$ 明确表示“是 subset，但不相等”。不同教材对 $\subset$ 的用法可能不同，本笔记统一用它表示 proper subset。

例：比较两个集合

设

$$A=\{1,2,3\} \qquad\text{and}\qquad B=\{1,2,3,4\}.$$

那么

$$A\subseteq B.$$

因为 $A$ 的每个元素都出现在 $B$ 中。这里还有 $A\subset B$，因为 $4$ 属于 $B$，却不属于 $A$，所以是 proper subset。

Empty set 是任意集合的 subset：

$$\varnothing\subseteq A.$$

如果这句话不成立，就必须在 $\varnothing$ 中找到一个不属于 $A$ 的元素。但 $\varnothing$ 根本没有元素，因此不可能找到这样的反例。特别地，$\varnothing\subseteq\varnothing$。

Element 与 subset 不是同一种关系

$\in$ 和 $\subseteq$ 检查的是不同的事情：

所以，

$$\varnothing\subseteq A$$

永远成立，而

$$\varnothing\in A$$

只有在 empty set 本身确实是 $A$ 的一个元素时才成立。

这两种关系有时可以同时成立。例如，若

$$A=\{1,2,\{1,2\}\},$$

则

$$\{1,2\}\in A$$

因为 $\{1,2\}$ 作为一个完整对象，是 $A$ 的一个元素。同时也有

$$\{1,2\}\subseteq A$$

因为 $1$ 和 $2$ 都是 $A$ 的元素。

常见的数集

本笔记把 $0$ 算作 $\mathbb N$ 的元素。有些教材的 $\mathbb N$ 从 $1$ 开始，使用时要先确认约定。

下面每个数集都是后一个数集的 subset：

$$\mathbb N^+\subseteq\mathbb N\subseteq\mathbb Z\subseteq\mathbb Q\subseteq\mathbb R.$$

把数看作数轴上的点时，$\mathbb N$ 和 $\mathbb Z$ 是 discrete 的，取值彼此分开。例如，$2$ 后面的整数是 $3$，两者之间没有其他整数。

实数轴则是 continuous 的。任意两个不同的实数之间总能找到更多实数，它的取值不是一步一步分开的。

定义 set 的两种方法

Definition by extension

Definition by extension 也叫 roster notation，就是把元素列在花括号内：

$$A=\{1,2,3\}.$$

元素的顺序不重要，重复写出同一个元素也不会改变集合：

$$\{1,2,3\} = \{3,2,1\} = \{1,1,2,3\}.$$

Set 只记录某个元素是否属于它，不记录元素的位置，也不记录它被写了几次。

Definition by comprehension

Definition by comprehension 也叫 set-builder notation，用元素需要满足的共同条件来描述集合：

$$A=\{x\in U\mid P(x)\}.$$

其中：

• $x$ 表示一个待判断的元素；
• $U$ 是 universe，也就是选取 $x$ 的范围；
• 竖线 $\mid$ 读作“使得”或“满足”；
• $P(x)$ 是 $x$ 必须满足的性质或条件。

例：natural numbers 与奇数

Natural numbers 可以定义为所有非负整数：

$$\mathbb N=\{x\in\mathbb Z\mid x\ge0\}.$$

条件 $x\ge0$ 表示“$x$ 大于或等于零”。也就是先从整数中选，再保留非负的那些数。

奇自然数可以用 extension 写成

$$O=\{1,3,5,7,\ldots\},$$

也可以用 comprehension 写成

$$O=\{2k+1\mid k\in\mathbb N\}.$$

当 $k$ 依次取 $0,1,2,3,\ldots$ 时，$2k+1$ 依次得到 $1,3,5,7,\ldots$。

例：rational numbers

Rational number 是能写成两个整数之比的数：

$$\mathbb Q= \left\{ \frac ab \;\middle|\; a,b\in\mathbb Z, \ b\neq0 \right\}.$$

条件 $b\neq0$ 排除了分母为零的情况。整数 $5$ 也是 rational number，因为 $5=\frac51$。

同一个 rational number 可以有多种分数写法：

$$\frac12=\frac24=\frac{-3}{-6}.$$

通常使用 reduced form：分母为正，分子与分母除了 $1$ 以外没有其他公因数。也就是说，它们的 greatest common divisor (GCD) 是 $1$。例如，

$$\frac{2}{-3}=-\frac23,$$

右边的写法就符合分母为正的约定。

Set equality

Principle of extensionality 指出：两个集合相等，当且仅当它们含有完全相同的元素。元素的顺序以及集合的定义方式都不影响相等性。

用 double-inclusion method 证明 $A=B$，需要分别证明两个方向：

$$A\subseteq B \qquad\text{and}\qquad B\subseteq A.$$

第一个方向说明 $A$ 中没有任何元素被 $B$ 遗漏；第二个方向说明 $B$ 中也没有任何元素被 $A$ 遗漏。

例：奇整数的两种写法

考虑

$$O=\{2k+1\mid k\in\mathbb Z\}$$

以及

$$A=\{2\ell-1\mid \ell\in\mathbb Z\}.$$

这两种描述都给出了所有奇整数。要证明 $O=A$，我们分别检查两个 inclusion。

任取 $x\in O$。存在某个整数 $k$，使得 $x=2k+1$。把它改写为

$$x=2k+1=2(k+1)-1.$$

$k+1$ 仍然是整数，所以 $x$ 符合 $A$ 中元素的形式。因此，

$$O\subseteq A.$$

再任取 $x\in A$。存在某个整数 $\ell$，使得 $x=2\ell-1$。把它改写为

$$x=2\ell-1=2(\ell-1)+1.$$

$\ell-1$ 仍然是整数，所以 $x$ 符合 $O$ 中元素的形式。因此，

$$A\subseteq O.$$

两个方向都成立，所以 $O=A$。

为什么不是任何条件都能定义 set

Unrestricted comprehension principle 假定任意条件 $P(x)$ 都能定义一个集合 $\{x\mid P(x)\}$。Russell's paradox 说明这个假定会出问题。

反例：Russell's paradox

假设我们想定义

$$R=\{x\mid x\text{ is a set and }x\notin x\}.$$

也就是说，$R$ 包含所有“不以自身为元素”的集合。按照这个规则，$\varnothing$ 符合条件，因为 $\varnothing\notin\varnothing$。

作个对比：某些版本的 set theory 允许包含自身的集合，称为 Quine atom，写作 $Q=\{Q\}$。因为 $Q\in Q$，它不符合 $R$ 的条件。

现在检查 $R$ 是否属于它自身：

• 如果 $R\in R$，那么 $R$ 必须满足自己规定的条件，所以 $R\notin R$。
• 如果 $R\notin R$，那么 $R$ 满足定义中的条件，所以按定义又有 $R\in R$。

无论选哪种情况，都会推出相反的结论。符号 $\iff$ 表示“当且仅当”，因此这个矛盾可以写成

$$R\in R\iff R\notin R.$$

这就是 Russell's paradox。

安全的做法是 restricted comprehension，在形式化 set theory 中称为 separation：先有一个已经定义好的 universe $U$，再从中选出满足 $P(x)$ 的元素：

$$\{x\in U\mid P(x)\}.$$

这样构造的是 $U$ 的一个 subset，而不是假定任意条件都能产生集合。这里的 $U$ 只是当前问题的 universal set，不是一个包含所有集合的集合。

Set operations

Set operations 用已有集合构造新集合。除非另有说明，以下所有 complement 都相对于固定的 universe $U$。

设 $A$ 和 $B$ 都是 $U$ 的 subset。为了看清每种运算，使用下面的例子：

$$A=\{1,3,5\} \qquad\text{and}\qquad B=\{1,2,3\}.$$

Union

Union 包含至少属于其中一个集合的所有元素：

$$A\cup B=\{x\in U\mid x\in A\text{ or }x\in B\}.$$

这里的“or”包括同时属于两个集合的情况：元素可以只在 $A$ 中、只在 $B$ 中，也可以同时在两者中。例子中，

$$A\cup B=\{1,2,3,5\}.$$

Intersection

Intersection 只包含两个集合共有的元素：

$$A\cap B=\{x\in U\mid x\in A\text{ and }x\in B\}.$$

因此，

$$A\cap B=\{1,3\}.$$

Difference

Set difference $A\setminus B$ 保留 $A$ 中不属于 $B$ 的元素：

$$A\setminus B=\{x\in U\mid x\in A\text{ and }x\notin B\}.$$

Difference 的顺序会影响结果：

$$A\setminus B=\{5\}, \qquad B\setminus A=\{2\}.$$

Complement

$A$ 的 complement 包含 $U$ 中所有不在 $A$ 中的元素：

$$\overline A=U\setminus A =\{x\in U\mid x\notin A\}.$$

Universe 的选择会改变 complement。若 $A=\{1,3,5\}$，并采用 $\mathbb N=\{0,1,2,\ldots\}$ 的约定，则

$$U=\mathbb N \quad\Longrightarrow\quad \overline A=\{0,2,4,6,7,8,\ldots\}.$$

如果 universe 改为 $\mathbb R$，则

$$\overline A =(-\infty,1)\cup(1,3)\cup(3,5)\cup(5,\infty).$$

$\overline A$ 并不是唯一的记法。不同课程或语境中也会用 $A^c$ 或 $U\setminus A$ 表示 complement。

Symmetric difference

Symmetric difference 包含恰好属于 $A$、$B$ 其中一个集合的元素：

$$A\mathbin\triangle B =\{x\in U\mid x\text{ belongs to exactly one of }A\text{ and }B\}.$$

在上面的例子中，

$$A\mathbin\triangle B=\{2,5\}.$$

有些资料把 symmetric difference 写作 $A\oplus B$。这些符号并非处处通用，语境不清楚时应先说明含义。

它有两种常用的等价写法：

$$A\mathbin\triangle B =(A\cup B)\setminus(A\cap B) =(A\setminus B)\cup(B\setminus A).$$

Set identities 与 Venn diagrams

Set identity 是对所有符合条件的集合都成立的等式。Venn diagram 把 universe 划分成所有可能的 membership 区域。如果两个表达式涂出的区域完全相同，它们就含有相同的元素，因此表示同一个集合。

这与前面的 double-inclusion 思路相同。若表达式 $X$ 和 $Y$ 涂出的区域一致，那么每个 $x\in X$ 也都在 $Y$ 的区域内，所以 $X\subseteq Y$。反过来同样得到 $Y\subseteq X$。因此，$X=Y$。

例：distributive law

设 $A$、$B$、$C$ 都是 $U$ 的 subset。Union 对 intersection 满足 distributive law：

$$A\cup(B\cap C)=(A\cup B)\cap(A\cup C).$$

左边保留整个 $A$，再加上 $B$ 与 $C$ 共有的部分。右边要求一个点同时属于 $A\cup B$ 和 $A\cup C$；如果它不在 $A$ 中，就必须既在 $B$ 中又在 $C$ 中。因此两边选中的区域相同。

A ∪ (B ∩ C)

1. Shade B2. Shade C3. Keep B ∩ C4. Add A5. Take the union

(A ∪ B) ∩ (A ∪ C)

1. Build A ∪ B2. Build A ∪ C3. Overlay both unions4. Keep their common part5. Same final region

Intersection 对 union 也满足 distributive law：

$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C).$$

常用的 set identities

下表中的恒等式对固定 universe $U$ 内的任意集合 $A$、$B$、$C$ 都成立。

例：用代数运算证明 identity

Set identities 可以像代数规则一样组合使用。例如，要证明

$$\overline{A\cup(B\cap C)} =(\overline C\cup\overline B)\cap\overline A,$$

从等式左边开始：

$$\begin{aligned} \overline{A\cup(B\cap C)} &=\overline A\cap\overline{(B\cap C)} &&\text{De Morgan's law}\\ &=\overline A\cap(\overline B\cup\overline C) &&\text{De Morgan's law}\\ &=(\overline C\cup\overline B)\cap\overline A &&\text{commutativity.} \end{aligned}$$

实心方块 $\blacksquare$ 或 QED 用来标记证明结束。QED 是一个拉丁语短语的缩写，意思是“这正是所要证明的”。

Cartesian products

Cartesian product 是一种 external operation：结果中的元素是 ordered pairs，而不是直接取自原来的两个集合。它改变了讨论对象所在的范围。

$$A\times B=\{(a,b)\mid a\in A\text{ and }b\in B\}.$$

每个 ordered pair 内部的顺序很重要，所以 $A\times B$ 通常不等于 $B\times A$。

例如，设

$$A=\{1,2,3\} \qquad\text{and}\qquad B=\{6,7\},$$

把 $A$ 的每个元素与 $B$ 的每个元素分别配对，得到

$$A\times B =\{(1,6),(1,7),(2,6),(2,7),(3,6),(3,7)\}.$$

一共有 $3\cdot2=6$ 个 ordered pairs。记号 $|A|$ 表示 $A$ 的 cardinality，即它含有的元素个数。若 $A$ 和 $B$ 都是有限集，则

$$|A\times B|=|A|\,|B|.$$

Cartesian plane 就是实数集与自身的 Cartesian product：

$$\mathbb R^2=\mathbb R\times\mathbb R =\{(x,y)\mid x,y\in\mathbb R\}.$$

Power sets

$A$ 的 power set 记作 $\mathcal P(A)$，是由 $A$ 的所有 subset 组成的集合：

$$\mathcal P(A)=\{X\mid X\subseteq A\}.$$

例如，当 $A=\{1,2,3\}$ 时，

$$\mathcal P(A)= \left\{ \varnothing, \{1\},\{2\},\{3\}, \{1,2\},\{1,3\},\{2,3\}, \{1,2,3\} \right\}.$$

构造 subset 时，$A$ 的每个元素都有两种选择：选入，或不选入。因此，含有 $n$ 个元素的集合共有 $2^n$ 个 subset：

$$|\mathcal P(A)|=2^{|A|}.$$

Empty set 只有一个 subset，就是它自身，所以

$$\mathcal P(\varnothing)=\{\varnothing\}.$$

Empty set 的 power set 并不空；它含有一个元素，这个元素是 empty set。