离散数学
有序对和笛卡尔积
定义 1.1 (有序对).由两个元素 a, b，按照顺序组成的二元组称为有序对，记作 ⟨a, b⟩.
有序对的性质： • 有序性 $⟨a, b⟩ \neq ⟨b, a⟩ (当a \neq b).$ •$ ⟨a, b⟩ = ⟨u, v⟩ ⇐⇒ a = u ∧ b = v.$
定义 1.2 (笛卡尔积). 设 A, B 为集合，A 与 B 的笛卡尔积（Cartesian product）记作 A × B，A × B = {⟨a, b⟩|a ∈ A ∧ b ∈ B}.
关系
等价关系
在我看来，等价关系类似与一些物体共同具有的某种性质，可以用其进行分类
定义
给定一个集合 A，
在 A 上的一个关系 R⊆A×A
称为 等价关系，如果它满足以下三个性质：
| 性质 | 名字 | 数学形式 | 意思 |
|---|---|---|---|
| ① | 自反性 | ∀a∈A,(a,a)∈R | 自己和自己等价 |
| ② | 对称性 | ∀a,b∈A,(a,b)∈R⇒(b,a)∈R | 如果a等价b，那b也等价a |
| ③ | 传递性 | ∀a,b,c∈A,(a,b)∈R∧(b,c)∈R⇒(a,c)∈R | a等价b，b等价c → a也等价c |
同余
在整数集合 Z 上，给定一个正整数 n，
我们说两个整数 a,b 模 n 同余，记作：
$a≡b(modn)$
意思是：
n 能整除它们的差，即
n∣(a−b)
也就是说，a−b=k×n，其中 k 是整数。
等价类
给定一个集合 A，和一个等价关系 ∼，
对于集合里的某个元素 a∈A，我们定义它的等价类为：
[a]={x∈A∣x∼a}
商集
当我们在集合 A 上定义了一个等价关系 ∼ 之后，
每个元素 a∈A 都属于某一个等价类：
[a]={x∈A∣x∼a}
然后，我们把所有这些等价类都“收集”起来，组成一个新的集合：
A/∼={[a]∣a∈A}
这个集合 A/∼ 就叫做—— 商集（quotient set）
集合的划分
定义
等价划分
等价关系导出
其他次序关系
偏序关系
拟序关系
全系关系
良序关系
总结
偏序关系>全系关系>良序关系