Lecture 4: Set Theory

• Recap of Key Definitions
• Set Equality
• Laws of Set Operations
• Derived Laws
• Two Useful Results

主要定义方法之重述 Recap of Key Definitions

具体内容，可以参见：COMP9020 2.1 Sets and Formal Languages - 定义集合 Defining sets

1. 显式枚举
2. 下定义区间
3. 从已有集合中构造

集合相等 Set Equality

欲证明两集合相等，需证明两集合均包含相同的元素。以下是三种方法：

• 直接列出所有的元素并比较是均相同。
• 证明 $A \subseteq B$ 并且 $B \subseteq A$，构成当且仅当后即可证明。
• 使用集合运算法则（Law of Set Operation）。

注意：韦恩图可以作为可视化的辅助措施，但不能作为严谨的证明过程。

集合运算法则 Law of Set Operation

• 集合交换律 Commutativity：

• 集合结合律 Associativity：

• 集合分配律 Distribution：

• 补集性质 Complementation：

• 单位元性质 Identity：

• 幂等性 Idempotence：

• 双重补集性质 Double complementation：

• 消去律 Annihilation：

• 德摩根定律 De Morgan's Laws：

运算法则使用示例

两种有用的定理 Two Useful Results

对偶原理 Principle of Duality

对偶的定义：

如果集合 $A$ 是用 $\cap , \cup , \empty , U$ 定义的集合，那么它的对偶 $dual(A)$ 是将 $\cap$ 与 $\cup$ 、 $\empty$ 与 $U$ 相互替换后的产物。

举例说明：

因此，有对偶原理：

如果你能证明集合 $A_1 = A_2$，那么你同样可以得到 $dual(A_1)=dual(A_2)。$

补集唯一性 Uniqueness of complement

当且仅当 $B=A^C$ 时，能够同时存在以下条件：

• $A \cap B = \empty$
• $A \cup B = U$