Sets

Basic Definition

Definition

A set is an unordered collection of distinct objects.

无序
唯一

The objects in a set are called the elements / members of the set.

\begin{aligned} A & = {2, 3, 4, 5} \\ = {5, 3, 2, 4} \end{aligned}

$S = {2, 3, 5, 3, 7}$ is not a set due to duplicated objects $3$
$S = {{a}, a}$ is a set because the objects in the set are unordered and distinct

Definition

Power set is set of all subsets of $A$
Let $A = {x, y}$

$pow (A) = {\emptyset, {x}, {y}, {x, y}}$
$| pow (A) | = 2^{| A |}$

Defining Sets by Properties

背景： 有时候只靠列出所有 elements 来定义一个 sets 是不可能的，因此我们可以用公式来定义 sets，只要 element 符合公式，则为 set 的元素

Define the set by ${x \in A | P (x)}$ .

e.g. $S = {x \in R | - 2 < x < 5}$ means $S$ is a real number which is in $(- 2, 5)$ .
e.g. $S = {x \in Z | x \geq 0}$ means $S$ is non-negative integer

Definition

$| S |$ is the size of $S$
e.g. $| \emptyset | = 0$

Membership

Definition

$x \in A$ : $x$ is an element of $A$
$x \notin A$ : $x$ is not an element of $A$
$A \subseteq B$ : $A$ is a subset of $B$
- For any $x \in A$ , we have $x \in B$
- 通俗来说： $A$ 在 $B$ 里面， $A$ 可能等于 $B$
$A = B$ : $A \subseteq B$ and $B \subseteq A$
$A \subset B$ : $A$ is proper subset of $B$
- $A \subseteq B$ and $A \neq B$
- 通俗来说： $A$ 在 $B$ 里面，但是 $A$ 不等于 $B$

Operations on Sets

Intersection

A \cap B = {x \in \underset{Universe}{\underset{⏟}{U}} | x \in A and x \in B}

- Two sets are disjoint if $A \cap B = \emptyset$

Union

A \cup B = {x \in U | x \in A or x \in B}

- $| A \cup B | = | A | + | B | - | A \cap B |$

Complement

\bar{A} = A^{c} = {x \in U | x \notin A}

- If $A \subseteq B$ , then $\bar{B} \subseteq \bar{A}$

Difference

A - B = {x \in U | x \in A and x \notin B}

- $| A - B | = | A | - | A \cap B |$

Indexed Collection of Sets

Tip

Indexed collection of sets 跟上文的 intersection 和 union 无异。
区别在于其支持批量运算，可以求一大堆 sets 的 intersection 和 union。

\begin{aligned} ⋃_{i = 0}^{n} A_{i} & = {x \in U ∣ x \in A_{i} for at least one i = 0, 1, 2, \dots, n} \\ ⋃_{i = 0}^{\infty} A_{i} & = {x \in U ∣ x \in A_{i} for at least one nonnegative integer i} \\ ⋂_{i = 0}^{n} A_{i} & = {x \in U ∣ x \in A_{i} for all i = 0, 1, 2, \dots, n} \\ ⋂_{i = 0}^{\infty} A_{i} & = {x \in U ∣ x \in A_{i} for all nonnegative integers i} \end{aligned}

Tip

Union 是至少任一一个 set 里面有
Intersection 是每一个 set 里面都有

Example

For each positive integer $i$ , let $A_{i} = {x \in R | - \frac{1}{i} < x < \frac{1}{i}}$
Equivalently, $A_{i} = (- \frac{1}{i}, \frac{1}{i})$
a. Find $A_{1} \cup A_{2} \cup A_{3}$ and $A_{1} \cap A_{2} \cap A_{3}$
b. Find $⋃_{i = 1}^{\infty} A_{i}$ and $⋂_{i = 1}^{\infty} A_{i}$

\begin{aligned} A_{1} \cup A_{2} \cup A_{3} & = (- 1, 1) \cup (- \frac{1}{2}, \frac{1}{2}) \cup (- \frac{1}{3}, \frac{1}{3}) \\ = (- 1, 1) \\ A_{1} \cap A_{2} \cap A_{3} & = (- 1, 1) \cap (- \frac{1}{2}, \frac{1}{2}) \cap (- \frac{1}{3}, \frac{1}{3}) \\ = (- \frac{1}{3}, \frac{1}{3}) \\ ⋃_{i = 1}^{\infty} A_{i} & = (- 1, 1) \cup (- \frac{1}{2}, \frac{1}{2}) \cup (- \frac{1}{3}, \frac{1}{3}) \cup \dots \\ = (- 1, 1) \\ ⋂_{i = 1}^{\infty} A_{i} & = (- 1, 1) \cap (- \frac{1}{2}, \frac{1}{2}) \cap (- \frac{1}{3}, \frac{1}{3}) \cap \dots \\ = {0} \end{aligned}

Partitions of Sets

Definition

A collection of non-empty sets ${A_{1}, \dots, A_{n}}$ is a partition of a set $A ⟺$

$A = A_{1} \cup A_{2} \cup \dots \cup A_{n}$
$A_{1}, A_{2}, \dots, A_{n}$ are mutually disjoint / pairwise disjoint

Cartesian Products

Definition

Given 2 sets $A$ and $B$ , the Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ , where $a \in A, b \in B$

A \times B = {(a, b) | a \in A, b \in B}

It can be generalized to any number of sets

A \times B \times C = {(a, b, c) | a \in A, b \in B, c \in C}

Tip

For ordered pairs, the ordering is important, i.e. $(1, 2) \neq (2, 1)$

Important

If $| A | = n$ and $| B | = m$ ,
- then $| A \times B | = n m$
- If $| C | = l$ , then $| A \times B \times C | = n m l$
$| A_{1} \times A_{2} \times \dots \times A_{k} | = | A_{1} | \times | A_{2} | \times \dots \times | A_{k} |$
$\emptyset \times A = \emptyset$
- $| \emptyset \times A | = 0$

Example

\begin{aligned} Let A & = {a, b}, B = {0, 1} \\ A \times A & = {(a, a), (a, b), (b, a), (b, b)} \\ A \times B & = {(a, 0), (a, 1), (b, 0), (b, 1)} \\ B \times B & = {(0, 0), (0, 1), (1, 0), (1, 1)} \end{aligned}

Set Identities

Distributive Law
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
Associative Law
- $A \cup (B \cup C) = (A \cup B) \cup C$
- $A \cap (B \cap C) = (A \cap B) \cap C$
De Morgan's Law
- $\overset{―}{(A \cup B)} = \overset{―}{A} \cap \overset{―}{B}$
- $\overset{―}{(A \cap B)} = \overset{―}{A} \cup \overset{―}{B}$
Complement Law
- $A \cup \overset{―}{A} = U$
- $A \cap \overset{―}{A} = \emptyset$
Commutative Law
- $A \cup B = B \cup A$
- $A \cap B = B \cap A$
Identity Law
- $A \cup \emptyset = A$
- $A \cap U = A$
Set Difference Law
- $A - B = A \cap \overset{―}{B}$

Example

Prove $A - (A \cap B) = A - B$

\begin{aligned} L . H . S . & = A - (A \cap B) \\ = A \cap \overset{―}{A \cap B} & Set Difference Law \\ = A \cap (\overset{―}{A} \cup \overset{―}{B}) & De Morgan’s Law \\ = (A \cap \overset{―}{A}) \cup (A \cap \overset{―}{B}) & Distributive Law \\ = \emptyset \cup (A \cap \overset{―}{B}) \\ = A \cap \overset{―}{B} & Identity Law \\ = A - B & Set Difference Law \\ = R . H . S . \end{aligned}

Prove $(A \cup B) - C = (A - C) \cup (B - C)$

\begin{aligned} L . H . S . & = (A \cup B) - C \\ = (A \cup B) \cap \overset{―}{C} \\ = (A \cap \overset{―}{C}) \cup (B \cap \overset{―}{C}) \\ = (A - C) \cup (B - C) \\ = R . H . S . \end{aligned}

Prove $\overset{―}{(A \cup B \cup C)} = \overset{―}{A} \cap \overset{―}{B} \cap \overset{―}{C}$

\begin{aligned} L . H . S . & = \overset{―}{(A \cup B \cup C)} \\ = \overset{―}{(A \cup B)} \cap \overset{―}{C} \\ = \overset{―}{A} \cap \overset{―}{B} \cap \overset{―}{C} \\ = R . H . S . \end{aligned}

Russell's Paradox 罗素悖论

Caution

以下内容由 AI 基于 Lecture Note 撰写，作者仅进行小幅度的修改。

W := {S \in Sets ∣ S \notin S}

即 “ $W$ 是所有"不包含自己"的集合的集合”。
现在问: $W$ 在不在 $W$ 里?

假设 $W \in W$ ：那么 $W$ 就属于 $W$ ，而 $W$ 是"不包含自己的集合的集合"，所以 $W$ 应该不包含自己，矛盾。
假设 $W \notin W$ ：那么 $W$ 不属于 $W$ ，说明 $W$ 是"不包含自己的集合"，按 $W$ 的定义，这种集合就应该属于 $W$ ，矛盾。
两条假设都推出矛盾——这就是著名的罗素悖论。它告诉我们: "任意性质都能定义出一个集合"是错的。比如"所有集合的集合"、"所有不包含自己的集合"这种"过于庞大"的定义,会落入自指的陷阱。

用"理发师悖论"帮助理解

一个理发师声称：“我给所有不自己剃头的人剃头,但我不给那些自己剃头的人剃头。”
问：理发师给不给自己剃头？
如果他给自己剃头，那按规矩他就不该给自己剃头——矛盾。
如果他不给自己剃头，那按规矩他就应该给自己剃头——矛盾。

只需记住：不能把"任意满足性质的全体"都默认成集合。

一点延伸：与停机问题的关系

罗素悖论和 Propositional Logic 中所提到的停机问题 (Halting Problem) 在推理结构上非常相似。