# 基本概念

# 不严格定义的概念

# 集合

作为整体研究的一堆东西，用大写字母 A, B, C, ⋯表示

# 元素

集合这一堆东西中的每一个，用小写字母 a, b, c, ⋯表示

# 属于

元素与集合间的关系

• 元素 a 属于集合 A ，记为 $a\in A$
• a 不属于 A，记为 $a\notin A$

# 全集

研究范围内的所有东西，记为 U

# 用逻辑语言严格定义的概念

# 子集关系

$$A \subseteq B \lrArr \forall x(x\in A \to x\in B)$$

# 集合相等

$$A = B \lrArr \forall x(x\in A \lrarr x\in B)$$

或者

$$A=B \lrArr A\subseteq B \land B \subseteq A$$

# 空集

$$\forall x(x\notin \varnothing)$$

# 朴素集合论

# 外延原则

两个集合只要有完全相同的元素则是相等的集合，不考虑集合名字本身的内涵

# 概念 (名字) 的外延

概念 (名字) 的外延是它所指称的对象，内涵是它有区别于其他概念的属性全体

# 集合 (名字) 的外延

对于集合 (名字)，外延是它包含的所有元素，内涵则视具体的应用而定

# 定义集合的方法

# 元素枚举法

将集合的所有元素一一罗列出来

• 适合元素比较少，或可按明显规律罗列元素时定义集合
• 元素罗列规律明显时可使用省略号

# 性质概括法

用谓词概括一个集合的所有元素满足的共同性质

# 基本形式

$$A = \{x∣P(x)\}$$

含义是:

$$\forall x(x\in A \lrarr P(x))$$

# 扩展形式

$$A=\{f(y)∣P(y)\}$$

含义是

$$\forall x(x\in A↔∃y(x=f(y)∧P(y)))$$

这里 f 是一个函数，或说 f (x) 是含有自由变量 x 的表达式

# 归纳定义法

给出基本元素和从已有元素构造其他元素的规则

从某种意义上说，集合的归纳定义给出了构造集合元素的算法

# 集合的划分 (partition)

# 定义

设 A 是非空集合，F 是集合族，其中每个集合都是 A 的子集。说集合族 F 是 A 的划分，如果：

• 非空：对任意的 $S\in \mathcal{F}$ , S\neq \mathcal
• 两两不交：对任意两个集合 $S_1, S_2\in F$ , $S_1\cap S_2=\varnothing$
• 覆盖集合 A：$\cup \mathcal{F}= A$

非空集合 A 的划分 $\mathcal{F}$ 中的每个集合称为这个划分的一个 划分块 (block)

# 非空集合 A 上的等价关系与它的划分有一一对应关系

A 关于一个等价关系的商集是 A 的划分，而 A 的一个划分导出的 “在同一划分块” 关系是等价关系

进一步，A 关于 “在同一划分块” 这个等价关系的商集就是这个划分，而 A 关于等价关系的商集作为 A 的划分所导出的 “在同一划分块” 关系就是这个等价关系本身

# 常用集合

# 模 m 剩余类

是一种常用等价类

对任意整数 $a\in \mathbb{Z}$ , a 在 R 下的等价类 $[a]_R$ 称为整数集 $\mathbb Z$ 的一个（与 a 同余的）模 m 剩余类，并记为:

$$\overline{a}=\{x\in \mathbb Z ∣ x ≡ a(\mod m) \}=\{x\in \mathbb Z∣m∣x-a\}=\{a+mz∣z\in \mathbb Z \}$$

# 模 m 剩余类的商集

$$\mathbb{Z}_m = \{ \overline 0,\overline 1,...,\overline{m-1} \} = \{ 0,1,...,m-1 \}$$

# 有序对

集合论定义的有序对

从二元有序对开始定义，归纳定义 n 元有序对

# 二元有序对

$$<a,b>=\{\{a\},\{a,b\}\}\\ <b,a>=\{\{b\},\{a,b\}\}$$

# 三元有序对

$$<a,b,c>=<<a,b>,c>$$

# n 元有序对

$$<a_1,a_2,...a_n>=<<a_1,a_2,...,a_{n-1}>,a_n>$$

# 有序 n 元组性质定理

$$<a_1,a_2,...a_n>=<b_1,b_2,...b_n> \lrArr a_i=b_i \ ,\ i=1,2,3,...,n$$