标签（空格分隔）： 离散数学 北京交通大学 张铎
[toc]
集合(Sets)
- 集合论的创始人是德国数学家扛托（George Cantor）。他对集合论的思考与研究是从对三角级数的研究中产生的。1874年他发表了第一篇关于无穷集合的文章，开创了集合论。
- 当今，集合的概念和方法被广泛地应用于各种科学和技术领域，是当代科学技术研究中必不可少的数学工具和表述语言。它也是计算机科学与软件工程的理论基础，在程序设计、形式语言、关系数据库、操作系统等计算机学科中都有重要的应用。
吾人直观或思维之对象，如为相异而确定之物，其总括之全体即谓之集合，其组成此集合之物谓之集合之元素。
- 集合是数学中最基本的概念，较难给出严格精确定义。
- 通常将若干个可确定、可分辨的对象构成的无序整体称为 集合(set) ，常用大写英文字母：$A、B、C、X、Y、Z$ 等表示。
- 组成集合的对象称作该集合的元素(element)，常用小写英文字母：$a,b,c,x,y,z$ 等表示。
- 若对象 $a$ 是集合 $S$ 的元素，则记作 <>$a \in S$,读作 $a$ 属于 $S$；若对象 $a$ 不是集合 $S$ 的元素，则记作： $a \notin S$，读作 $a$ 不属于 $S$。
例子：
- R: "方程 $x^{2} - 2 = 0$ 的所有实数解"是集合
- S: "12 的所有正约数"是集合
- P: "复平面上的所有点"是集合
- Q: "清华大学的全体学生"是集合
- “很大的实数”不是集合
- “清华大学的全体年轻教师”都不是集合
- 组成一个集合的条件是能够明确地判断任意一个对象是或者不是该集合的元素，二者必居其一。
集合中的元素没有次序，一个集合中也没有相同的元素，如果一个集合中出现若干相同的元素，则将它们作为一个元素：
- 即一个集合由它的元素所决定而与描述它时列举其元素的特定顺序无关。
- 在同一个集合中的诸元素并不一定存在确定的关系。
- 为了体系的严谨性，规定：对于任意集合 $A$ 都有 $A \notin A$.
使用形式化方法表示一个集合有两种方式：
- （1）外延表示法（列举法）—— 逐个列出集合的元素，元素与元素之间用逗号隔开，并将所有元素写在花括号“{}”里面，
如：$A=\{a, b, c\}, B=\{0, 1, ..., 10\}, N=\{0, 1, 2, ...\}$
- （2）内涵表示法（描述法）—— 假设 $P(x)$ 是一个包含 $x$ 的陈述句，表示 $x$ 所具有的的性质；对于每个确定的 $x$，可以明确断定 $P(x)$ 的正确与否。集合 $\{x|P(x)\}$ 表示所有使 $P(x)$ 为真的对象 $x$ 所组成的集合。
- 如：$Z^{+}=\{x | x 是正整数\}， R=\{x | x^{2}-2=0 且 x 是实数\}$。
使用一些特定的符号表示一些常用集合：
- $N = \{x | x 是自然数\}$
- $Z = \{x | x 是整数\}$
- $R = \{x | x 是实数\}$
- $Q = \{x | x 是有理数\}$
- $C = \{x | x 是复数\}$
- $Z^{+} = \{x | x 是正整数\}$
设 $A$ 和 $B$ 是两个集合，如果 $A$ 的任意一个元素都是 $B$ 的元素，则称 $A$ 为 $B$ 的 子集（subset）,称 $B$ 为 $A$ 的 超集（superset）,记作 $A \subseteq B$ (或 $B \supseteq A$)，读作 $A$ 包含于 $B$ 或 $B$ 包含 $A$。
- (a) $\subseteq $ 表示集合与集合之间的关系，而 $\in$ 表示元素与集合之间的关系。
- (b) 设 $A、B、C$ 是三个集合，若 $A \subseteq B$ 且 $B \subseteq C$，则有 $A \subseteq C$。
设 $A$ 和 $B$ 是两个集合，如果 $A \subseteq B$ 且 $B \subseteq A$，则称 $A$ 与 $B$ 相等，记作： $A=B$否则称它们不相等，记作： $A \neq B$。
- 两个集合相等，当且仅当它们具有相同的元素。
设 $A$ 和 $B$ 是两个集合，如果 $A \subseteq B$ 且 $A \neq B$ ，则称 $A$ 为 $B$ 的 真子集(proper subset) 记作： $A \subset B$ (或 $B \supset A$)。
- 如果 $A$ 是 $B$ 的真子集，则集合 $A$ 中的每一个元素都属于 $B$，但集合 $B$ 中至少有一个元素不属于 $A$。
在讨论的具体问题中，所讨论对象全体称作 全集(universal set) ，记作 $U$。
- 在讨论的具体问题中，所提及的集合均是全集的子集。而针对不同的具体问题可能会有不同的全集。
- 不包含任何元素的集合称作 空集(empty set)，记作 $\phi$。
定理：
- 设 $A$ 是任意一个集合， $\phi$ 是空集，则有：
- (a) $A \subseteq A$
- (b) $\phi \subseteq A$
- 证明：
- （a）对于任意集合 $A$，它的任一元素都是其自身的元素，因而 $A \subseteq A$。
- （b）（反证法）若存在集合 $A$ 使得 $\phi$ 不是 $A$ 的子集，则由定义存在元素 $x \in \phi$ 而且 $x \notin A$；但这与空集的定义相互矛盾，因此假设不成立，原结论成立。
推论：
空集是唯一的。
- 证明：
设 $\phi_{1}$ 和 $\phi_{2}$ 都是空集，则 $\phi_{1} \subseteq \phi_{2}$ 且 $\phi_{2} \subseteq \phi_{1}$ ，有 $\phi_{1} = \phi_{2}$。
- 一个集合 $A$ 所包含的元素数目称为该集合的 基数 或 势(cardinality) 记作 $|A|$ 或 $\#A$ 或 $card(A)$。
若 $|A| < \infty$，则称 $A$ 为有限集或有穷集（finite set），否则称 $A$ 为无限集 或 无穷集（infinite set）。
- 例：
- card({a, b, 2, a, *}) = 4 #因为 'a' 重复，算做一个。
- card($\phi$) = 0.
假设 $A$ 是集合， $A$ 的所有子集所组成的集合称作 $A$ 的 幂集（power set），记作 $p(A)$，即 $p(A) = \{x | x \subseteq A\}$。
- 例：
- A = {a, b, c}
- p(A) = {$\phi$, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, {a, b, c}}