第一章 - 算法基础与算法分析 fundamentals of algorithms and algorithm analysis
- 1.2、数学基础：集合与关系 (Mathematical foundations: sets and relations)
- 1.2.1、集合、等价集合、基数(Sets, set equality, cardinality)
- 1.2.2、子集、超集、涉及子集的证明(Subsets and supersets, proofs involving subsets)
- 1.2.3、集合的运算与证明(Set operations and proofs)
- 1.2.4、对、元组与笛卡尔积（Pairs, tuples and Cartesian products）
- 1.2.5、关系:定义、例子、属性(Relations: definition, examples, properties)
- 1.2.6、等价关系与顺序关系(Equivalence relations, order relations
1.2、数学基础：集合与关系 (Mathematical foundations: sets and relations)
1.2.1、集合、等价集合、基数(Sets, set equality, cardinality)
(1)、集合
定义： 集合 A 是被称为元素或成员的对象的无序集合。
Definition: A set is an unordered collection of objects, called elements or members
of the set.
记法：
x
∈
A
x \in A
x∈A 表示
x
x
x 是集合
A
A
A 的元素
x
∉
A
x \notin A
x∈/A 表示
x
x
x 不是集合
A
A
A 的元素
我们将根据以下原则使用这个定义：
我们可以定义集合：
- 通过枚举元素：
A
:
=
0
,
1
,
2
,
3
,
4
,
5
=
0
,
1
,
2
,
⋅
⋅
⋅
,
5
.
A := {0, 1, 2, 3, 4, 5} = {0, 1, 2, · · · , 5}.
A:=0,1,2,3,4,5=0,1,2,⋅⋅⋅,5.
这被称为花名册方法(roster method)或扩展集表示法(extensional set notation)。 - 根据元素的特性：
- B :={x | x ∈ A and x is even}
={x ∈ A | x is even }
={x | x is a natural number and x is even and 0 ≤ x ≤ 5}.
这被称为集合构建符号(set builder notation)或内涵集合符号(intensional set notation)。(具体的记法 B := {0, 2, 4}).
我们总是用花括号(curly brackets)表示集合。竖栏’ | ‘可以读为’ such that ‘或者’with the property that’。例如：{x | x ∈ A and x is even} 能够被读作 ‘the set of all x such that x is
an element of A and x is even.’
同时也可能发现：
- 有时用 ‘:’ 而不是 ‘|’
- 用 ‘,’ 而不是 ‘and’
例如：B = {x: x ∈ A, x even}
注意：
- {x | 0 ≤ x ≤ 5} 不是一个集合，因为它不确定x是什么类型的数字(例如，x可以是实数，也可以是整数)。
- {A | A is a set, A ∉ \notin ∈/ A} 导致 罗素悖论 (Russell’s Paradox).
- Bertrand Russell (1872-1970): British philosopher, logician, mathematician,
historian, writer, social critic, political activist, and Nobel laureate.
罗素悖论表明，朴素集理论的一些形式化尝试导致了一个矛盾，即:
设A:= {B | B ∉ \notin ∈/ B}。那么A∈A iff A ∉ \notin ∈/ A
如何避免这些问题？
在有意的使用表示法时，记住要显式地提到集合中被选择的元素!
{x ∈ A | x has property (properties) P}, 其中A是一个集合，P是一个属性，或者属性列表，A的每个元素可能存在也可能不存在。
重要的基础属性：
- 集合中的所有元素都是不同的。即一个值要么是集合中的元素，要么不是。它不能在集合中出现多次。
- 集合中的元素没有固定的顺序。
- 同一个集合可以用不同的方法来描述
{1, 2, 3} = {1, 2, 2, 3} = {2, 1, 3} = {i | i integer, 0 < i ≤ 3}.
集合可以由“原子(‘atomic’)”或“组合(‘composed’)”元素构建。集合可以包含不同种类的元素。例如：
集合{1，(黑桃，8)，{红，蓝}，5,1}由以下元素组成:
元素1、元素(黑桃，8)、元素{red, blue}和元素5
标准数集的记法：
- 自然数集 N : = { 0 , 1 , 2 , 3 , . . . } N:=\{0, 1, 2, 3, . . .\} N:={0,1,2,3,...}
- 整数集 Z : = { 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , . . . } Z:=\{0, 1, -1, 2, -2, 3, -3, . . .\} Z:={0,1,−1,2,−2,3,−3,...}
- 正自然数集 Z > 0 : = { 1 , 2 , 3 , . . . } Z_{>0}:=\{1, 2, 3, . . .\} Z>0:={1,2,3,...}
- 有理数集 Q : = { a b ∣ a , b ∈ Z , b ≠ 0 } Q:=\{\frac{a}{b}|a, b\in Z, b\neq 0\} Q:={ba∣a,b∈Z,b=0}
- 实数集 R : = R:= R:=
- 正实数集 R > 0 : = R_{>0}:= R>0:=
(2)、等价集合
如果两个集合 A 和 B包含相同的元素，则它们相等。于是有：
所有
x
∈
A
x\in A
x∈A 满足
x
∈
B
x\in B
x∈B，并且：
所有
x
∈
B
x\in B
x∈B 满足
x
∈
A
x\in A
x∈A
例子：
{1, 2, 3} = {1, 2, 2, 3},
{1, 2, 3} = {2, 1, 3}
{1, 2, 3} = {i | i is an integer, 0 < i ≤ 3}.
(3)、空集(empty set)
定义：
空集是不包含元素的(唯一确定的)集。
我们表示为：
∅
\varnothing
∅ 或者
{
}
\{\}
{}
只有一个元素的集合被称为单例集(singleton set)。
注意:
Ø是一个集合，但是不含任何元素。
{Ø}是一个非空集合，集合只有空集这个元素。
一个常见的错误是将∅与{∅}混淆
类比: 空文件夹与包含空文件夹的文件夹不同。
(4)、基数(Cardinality)
一个集合叫做有限集，如果它只包含有限的元素，也就是说，如果有一个数n∈N，使这个集合恰好包含n个元素。
集合M是：
∣
M
∣
:
=
{
−
x
,
t
h
e
n
u
m
b
e
r
o
f
e
l
e
m
e
n
t
s
i
n
M
,
i
f
M
i
s
f
i
n
i
t
e
∞
,
o
t
h
e
r
(1)
|M|:= \begin{cases} -x,the\ number\ of\ elements\ in\ M,\ if\ M\ is\ finite\\ \infty, other \end{cases} \tag{1}
∣M∣:={−x,the number of elements in M, if M is finite∞,other(1)
举例：
|{2, 4, 6}| = 3
|∅| = 0
|{∅}| = 1
|N| = ∞
|{2, 4, 6, 4}| = 3
|{7, {7, 14}}| = 2
(4.1)、编程中的集合
在编程语言中，数据类型或类型的概念是建立在集合的概念之上的。特别是，数据类型或类型是集合的名称，以及可以对该集合中的对象执行的一组操作。
例如，boolean是集合{0,1}的名称以及该集合的一个或多个元素上的操作符，如AND、or和NOT
1.2.2、子集、超集、涉及子集的证明(Subsets and supersets, proofs involving subsets)
(1)、子集与超集(Subsets and supersets)
设A，B为集合
- A是B的子集(subset)(表示:A ⊆ \subseteq ⊆B)，当每一个A中的元素也是B中的元素
- A是B的真子集(proper subset)(表示:A ⊊ \subsetneq ⊊B)，当A ⊆ \subseteq ⊆B且A ≠ \neq =B
- A是B的超集(superset)(表示:A ⊇ \supseteq ⊇B)，当B ⊆ \subseteq ⊆A
- A是B的真超集(proper superset)(表示:A ⊋ \supsetneq ⊋B)，当A ⊇ \supseteq ⊇B且A ≠ \neq =B
维恩图：
维恩图(Venn Diagrams)能够用来说明集合之间的关系，然而，维恩图却不能用来代替证明。
表示 A
⊆
\subseteq
⊆B:
(2)、子集的证明(Proofs involving subsets)
- 证明 A 是 B 的子集: 要证明A ⊆ \subseteq ⊆ B, 就要证明 当 x 属于 A 则x 属于 B.
- 证明 A 不是 B的子集: 要证明 A ⊈ \not\subseteq ⊆ B，就要寻找一个x ∈ \in ∈A但是x ∉ \notin ∈/B
- 证明 A 是 B的真子集: 要证明A ⊊ \subsetneq ⊊ B，就要证明 A ⊆ \subseteq ⊆ B，并且就要寻找一个x ∈ \in ∈B但是x ∉ \notin ∈/A
举例：
- 所有小于10的奇数正整数集是所有小于10的正整数集的子集
- Q ⊆ R Q\subseteq R Q⊆R
这些事实中的每一个都紧跟着一个元素，它属于第一组，也属于第二组。
(3)、定理(Theorem)
对每一个集合 S S S
- S ⊆ S S\subseteq S S⊆S。这是正确的，因为第一个集合中的每个元素也是第二个集合中的一个元素。
- ∅ ⊆ S \emptyset\subseteq S ∅⊆S。这和Part (a)的原因是一样的。事实上，因为空集合(第一个集合)中没有元素，所以没有什么可显示的。
对于集合 A, B, C:
- A = B 当且仅当 A
⊆
\subseteq
⊆ B and B
⊆
\subseteq
⊆ A。 如果 A = B 那么 A 和 B 根据等价集合的定义则包含相同的元素，因此A中每一个元素也在B中(A
⊆
\subseteq
⊆ B)，并且B中每一个元素也在A中(B
⊆
\subseteq
⊆ A)。
相反的，假设A ⊆ \subseteq ⊆ B and B ⊆ \subseteq ⊆ A，我们得到A中的每一个元素都在B中，并且B中的每一个元素都在A中，因此A和B包含相同的元素，因此A = B。 - 如果 A ⊆ \subseteq ⊆ B 并且 B ⊆ \subseteq ⊆ C, 那么 A ⊆ \subseteq ⊆ C。假设A ⊆ \subseteq ⊆ B 并且 B ⊆ \subseteq ⊆ C，我们需要去证明 A ⊆ \subseteq ⊆ C，比如每一个 x ∈ \in ∈ A 都满足 x ∈ \in ∈ C。设 x ∈ \in ∈ A为任意元素。因此，通过假定A ⊆ \subseteq ⊆B，我们知道x ∈ \in ∈B，然后通过假定B ⊆ \subseteq ⊆C，我们知道x ∈ \in ∈C。由于x ∈ \in ∈ A是任意选取的，因此证明了A ⊆ \subseteq ⊆C。
1.2.3、集合的运算与证明(Set operations and proofs)
(1)、集合的运算(Set Operations)
从给定的集合中构建新的集合。
幂集(power set)：
集合S的幂集是集合S的所有子集的集合，比如：
P
(
{
a
,
b
}
)
=
{
∅
,
{
a
}
,
{
b
}
,
{
a
,
b
}
}
P(\{a, b\}) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}
P({a,b})={∅,{a},{b},{a,b}}
注意：在文献中，你也会发现P(S)用Pow(S)或 2 s 2^s 2s表示。
假设A 和 B 为集合
- 交集(Intersection)： A ∩ B : = { x : x ∈ A a n d x ∈ B } A\cap B:=\{x:x\in A\ and\ x\in B\} A∩B:={x:x∈A and x∈B}
- 并集(Union): A ∪ B : = { x : x ∈ A o r x ∈ B } A\cup B:=\{x: x\in A\ or\ x\in B\} A∪B:={x:x∈A or x∈B}
- 差集(Different): A − B : = { x ∈ A : x ∉ B } A - B:=\{x\in A:x\notin B\} A−B:={x∈A:x∈/B}
- 对称差(Symmetric difference): A ⊕ B : = ( A − B ) ∪ ( B − A ) A\oplus B:=(A - B)\cup(B-A) A⊕B:=(A−B)∪(B−A)
注意：
差集有时也写作
A
∖
B
A\setminus B
A∖B
对称差有时也写作
A
Δ
B
A\Delta B
AΔB
(2)、补数(complement)
我们想要集合
A
A
A的补数，简写为
A
‾
\overline{A}
A，是所有不属于
A
A
A 的元素的集合。
准确定义
A
‾
\overline{A}
A时要注意:
如果我们简单的假设：
A
‾
:
=
{
x
:
x
∉
A
}
\overline{A}:=\{x:x\notin A\}
A:={x:x∈/A}
空集合
∅
\varnothing
∅ 将包含一切——“所有集合的集合”(set of all sets)。
这个集合不可能存在，这就导致了罗素悖论(Russell’s paradox)。
因此，我们总是考虑一个固定全集(fixed universe)U中的集合，而U本身就是一个集合。
定义:设
U
U
U 为我们的固定全集，该全集本身是一个集合，设
A
⊂
U
A\subset U
A⊂U是一个集合。
在集合
U
U
U 中，
A
A
A的补数为集合:
A
‾
:
=
U
−
A
\overline A:=U-A
A:=U−A
(3)、定理(相交与并集定律)(Theorem (Laws for intersections and unions))
假设 A , B , C A, B, C A,B,C为集合，于是：
- 幂等定律(Idempotent laws): A ∩ A = A A\cap A = A A∩A=A和 A ∪ A = A A\cup A = A A∪A=A
- 交换律(Commutative laws): A ∩ B = B ∩ A A\cap B = B\cap A A∩B=B∩A和 A ∪ B = B ∪ A A\cup B = B\cup A A∪B=B∪A
- 结合律(Associative laws): A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C A\cap(B\cap C)=(A\cap B)\cap C A∩(B∩C)=(A∩B)∩C和 A ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C A\cup(B\cup C)=(A\cup B)\cup C A∪(B∪C)=(A∪B)∪C
- 吸收率(Absorption laws): A ∩ ( A ∪ B ) = A A\cap(A\cup B)=A A∩(A∪B)=A和 A ∪ ( A ∩ B ) = A A\cup(A\cap B)=A A∪(A∩B)=A
- 分配律(Distributive laws): A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) A\cap(B\cup C)=(A\cap B)\cup(A\cap C) A∩(B∪C)=(A∩B)∪(A∩C)和 A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ) A\cup(B\cap C)=(A\cup B)\cap(A\cup C) A∪(B∩C)=(A∪B)∩(A∪C)
(4)、前面定理的证明(Proof of the previous Theorem)
A
,
B
,
C
A, B, C
A,B,C 为任意集合:
(5)、定理 - 补数定律(Theorem - Laws for complements)
假设
U
U
U 是一个固定全集，它自身也是一个集合，假设集合
A
,
B
⊆
U
A, B\subseteq U
A,B⊆U，于是：
1.2.4、对、元组与笛卡尔积（Pairs, tuples and Cartesian products）
(1)、对与元组(Pairs and tuples)
- 对任意的 a , b a, b a,b，我们假设 ( a , b ) (a, b) (a,b)表示由组件(components) a a a和 b b b组成的(有序)对。
- 对于 k ∈ N k\in N k∈N和任意对象 a 1 , . . . , a k a_1, . . ., a_k a1,...,ak，我们假设 ( a 1 , . . . , a k ) (a_1, . . ., a_k) (a1,...,ak)表示由组件a_1, . . ., a_k组成的有序 k k k阶元组。
- 等价元组(Equality of tuples):对于所有
k
,
l
∈
N
k, l\in N
k,l∈N 并且
a
1
,
.
.
.
,
a
k
,
b
1
,
.
.
.
,
b
l
a_1, . . ., a_k, b_1, . . ., b_l
a1,...,ak,b1,...,bl
元组的组件也称为元素。
(1.1)、元组(Tuples)
- 对于k = 0，存在一个k阶元组，即空元组()，它没有任何组件。
- 注意元组(tuples)与集合(sets)之间的不同：
( 1 , 2 ) ≠ ( 2 , 1 ) (1, 2)\neq(2, 1) (1,2)=(2,1)，但是 { 1 , 2 } = { 2 , 1 } \{1, 2\}=\{2, 1\} {1,2}={2,1}，因为顺序问题
( 1 , 1 , 2 ) ≠ ( 1 , 2 ) (1, 1, 2)\neq(1, 2) (1,1,2)=(1,2)，但是 { 1 , 1 , 2 } = { 1 , 2 } \{1, 1, 2\}=\{1, 2\} {1,1,2}={1,2}，因为元组存在重复组件(元素)
(2)、两个集合的笛卡尔积(Cartesian product of two sets)
两个集合A, B的笛卡尔积，用A
×
\times
× B表示，是有序对(a, b)的集合，其中a属于A, b属于B。
换句话说：
A
×
B
:
=
{
(
a
,
b
)
∣
a
∈
A
a
n
d
b
∈
B
}
A\times B:=\{(a, b)|a\in A\ and\ b\in B \}
A×B:={(a,b)∣a∈A and b∈B}
举例：
假设
A
=
{
a
,
b
}
A=\{a, b\}
A={a,b} 并且
B
=
{
1
,
2
,
3
}
B = \{1, 2, 3\}
B={1,2,3}
A × B = {(a, 1),(a, 2),(a, 3),(b, 1),(b, 2),(b, 3)}.
A × {1} = {(a, 1),(b, 1)}.
A × ∅ = ∅.
集合
A
1
,
A
2
,
…
,
A
n
A_1, A_2, …, A_n
A1,A2,…,An 的笛卡尔积，表示为
A
1
×
A
2
×
.
.
.
×
A
n
A_1\times A_2\times . . .\times A_n
A1×A2×...×An，是有序n元组
(
a
1
,
a
2
,
.
.
.
,
a
n
)
(a_1, a_2, ..., a_n)
(a1,a2,...,an) 的集合，这里
a
i
a_i
ai 属于
A
i
A_i
Ai，其中
i
=
1
,
2
,
3
,
.
.
.
,
n
i = 1, 2, 3, ..., n
i=1,2,3,...,n
.
换句话说：
A
1
×
A
2
×
.
.
.
×
A
n
:
=
{
(
a
1
,
a
2
,
.
.
.
,
a
n
)
∣
a
1
∈
A
1
,
.
.
.
,
a
n
∈
A
n
}
A_1 × A_2 × . . . × A_n:= \{(a_1, a_2, . . . , a_n) | a_1 ∈ A_1, . . . , a_n ∈ A_n\}
A1×A2×...×An:={(a1,a2,...,an)∣a1∈A1,...,an∈An}
注意：
.如果
A
A
A是一个集合，我们用
A
2
A^2
A2 去表示
A
×
A
A\times A
A×A，笛卡尔积为
A
A
A 和它自己。
更普遍的说，对于 n ∈ N n\in N n∈N，我们设 A n : = A × . . . × A A^n:= A\times ...\times A An:=A×...×A，这里乘积包含 n n n个因子。
1.2.5、关系:定义、例子、属性(Relations: definition, examples, properties)
(1)、关系的定义(Relations: definition)
- 设 A A A 和 B B B 为集合， A A A 到 B B B 的关系是 A × B A\times B A×B 的子集
- 让
k
∈
Z
>
0
k\in Z_{>0}
k∈Z>0 并且 让
A
1
,
.
.
.
.
.
.
,
A
k
A_1, ......, A_k
A1,......,Ak为集合
A 1 , . . . . . . , A k A_1, ......, A_k A1,......,Ak 的一个关系是 A 1 × , . . . . . . , × A k A_1\times, ......, \times A_k A1×,......,×Ak的一个子集。数字 k k k 叫做关系的亲和性(arity)。 - 假设
A
A
A 是一个集合， 并且
k
∈
N
k\in N
k∈N。
A A A上的 K K K元关系是 A k A^k Ak的子集。
注意： 因此:关系是笛卡尔积的子集。
(2)、关系的例子(Relations: example)
为了在格式(day, month, year)中指定日期，我们使用范围
则有效日期(vaild date)是下列集合的子集：
例如：有效日期(vaild date)对于DayValues, MonthValues, YearValues来说
这个关系包含，比如说 tuple (23, 6, 1912), 但不包含 tuple (30, 2, 1912).
(2.1)、集合与自身的关系
集合A与自身之间的关系具有特殊的意义，设A是一个集合。集合A上的关系是A与自身的关系。
设A:={1, 2, 3, 4}。R对A的关系中有哪些对(paris)R:= {(a, b) | a 除以 b}?
(3)、关系的性质：自反 (Properties of relations: reflexive)
在某些关系中，一个元素总是与其自身相联系的。例如，如果A是所有人的集合，R是由a满足b的所有(a, b)对(paris)组成的关系，那么对于所有a∈A，(a, a)∈R。
定义：对于集合A上的每个元素a∈A，如果(a, a)∈R，R是集合A的关系，则称为自反关系。
这可以通过∀x (x, x)∈R在谓词逻辑中形式化，其中x的定义域是A中所有元素的集合。
(4)、关系的性质：对称的、反对称的(Properties of relations: symmetric, antisymmetric)
在某些关系中，第一个元素与第二个元素相关，当且仅当第二个元素也与第一个元素相关时。
由一对(x,y)组成的关系，其中x和y是计算机学院的学生，这些学生具有至少该属性的类。
由一对(x,y)组成的关系，其中x和y是人，然后x loves y不具备该属性。
定义：
如果对于所有a,b
∈
\in
∈A，(a,b)
∈
\in
∈R 能表示 (b,a)
∈
\in
∈R在集合A上的一个关系R叫做对称的(symmetric)。
在集合A上的一个关系R，使得对于所有a,b
∈
\in
∈A，如果(a,b)
∈
\in
∈R 并且 (b,a)
∈
\in
∈R，就有a=b，这种关系叫做反对称的(antisymmetric)。
对称性(symmetry)可以用谓词逻辑形式化为
∀
x
∀
y
(
(
x
,
y
)
∈
R
→
(
y
,
x
)
)
∈
R
\forall x\forall y((x,y)\in R\rightarrow (y,x))\in R
∀x∀y((x,y)∈R→(y,x))∈R
反对称性(antisymmetry)可以形式化为
∀
x
∀
y
(
(
(
x
,
y
)
∈
R
∧
(
y
,
x
)
∈
R
)
→
x
=
y
)
\forall x\forall y(((x,y)\in R\wedge (y,x)\in R)\rightarrow x=y)
∀x∀y(((x,y)∈R∧(y,x)∈R)→x=y)
这里，x和y的定义域是集合A的所有元素。
举例：
考虑下列所有整数集合上的关系
1.
{
(
a
,
b
)
∣
a
≤
b
}
\{(a,b) | a\le b\}
{(a,b)∣a≤b}
2.
{
(
a
,
b
)
∣
a
=
b
}
\{(a,b) | a = b\}
{(a,b)∣a=b}
3.
{
(
a
,
b
)
∣
a
+
b
≤
3
}
\{(a,b) | a + b \le 3\}
{(a,b)∣a+b≤3}
判断哪些关系是自反的(reflexive)?哪个是对称的(symmetric)?哪个是反对称的(antisymmertic)?
Reflexive: 1,2
Symmetric：2,3
Antisymmertic：1,2
所有的(a,a)都在R中，则R是自反关系。
所有的(a,a)都不在R中，则R是反自反关系。
a≠b时，(a,b)与(b,a)要么都在R中，要么都不在R中，那么R就是对称关系。
a≠b时，(a,b)与(b,a)要么都不在R中，要么只有一个在R中，那么R就是反对称关系。
(5)、关系的性质：传递性(Properties of relations: transitive)
如果我们考虑包含(x, y)的关系式R，如果x在班上所有学生的集合上比y年长，那么我们知道如果(x, y) ∈ \in ∈R和(y, z) ∈ \in ∈R，那么(x, z) ∈ \in ∈R。
定义：如果(a,b)
∈
\in
∈R，并且(b,c)
∈
\in
∈R，就有对于所有a,b,c
∈
\in
∈A有(a,c)
∈
\in
∈R，该集合A上的关系R被称为传递性(transitive)。
它可以使用谓词逻辑形式化为: ∀ x ∀ y ∀ z ( ( ( x , y ) ∈ R ∧ ( y , z ) ∈ R ) → ( x , z ) ∈ R ) \forall x\forall y\forall z(((x,y)\in R\wedge(y,z)\in R)\rightarrow(x,z)\in R) ∀x∀y∀z(((x,y)∈R∧(y,z)∈R)→(x,z)∈R)，这里x，y和z的定义域为集合A的所有元素。
(6)、关系的性质：全数的(Properties of relations: total)
定义：如果对所有a,b ∈ \in ∈A，满足：(a,b) ∈ \in ∈R或者(b,a) ∈ \in ∈R，则在集合A上的一个关系R称为全数的
它可以用谓词逻辑格式化为： ∀ x ∀ y ( ( x , y ) ∈ R ∨ ( y , x ) ∈ R ) \forall x\forall y ((x,y)\in R\vee(y,x)\in R) ∀x∀y((x,y)∈R∨(y,x)∈R)，这里定义域为集合A的所有元素。
举例：
考虑下列所有整数集合上的关系：
1.
{
(
a
,
b
)
∣
a
≤
b
}
\{(a,b)|a\le b\}
{(a,b)∣a≤b}
2.
{
(
a
,
b
)
∣
a
=
b
o
r
a
=
−
b
}
\{(a,b)|a=b\ or\ a=-b\}
{(a,b)∣a=b or a=−b}
3.
{
(
a
,
b
)
∣
a
+
b
≤
3
}
\{(a,b)| a+b\le 3\}
{(a,b)∣a+b≤3}
Transitive:1,2
Total:1
对所有a,b,c属于A，如果有(a, b) ∈ R，并且(b, c) ∈ R，那么有(a, c) ∈ R
对所有a, b ∈ A 满足 (a, b) ∈ R 或者(b, a) ∈ R.
1.2.6、等价关系与顺序关系(Equivalence relations, order relations
(1)、等价关系的定义(Equivalence relation: definition)
一个等价关系是一个二元关系(binary relation)，这种关系是自反的，传递的和对称的。
举例：
- 设
R
:
=
{
(
a
,
b
)
∣
a
=
b
o
r
a
=
−
b
}
R:=\{(a,b)|a=b\ or\ a=-b\}
R:={(a,b)∣a=b or a=−b} 为一个在整数上的关系。
R是一个等价关系吗？ - 设 L L L 为本班所有学生名字的关系，如果名字x和y有相同数量的字母，且x和y在L中，那么 L L L 为一个等价关系吗？
(2)、等价类、代表的定义(Equivalence classes, representatives: definition)
假设
E
E
E 为一个在集合
V
V
V上的等价关系。对于每个
v
∈
V
v\in V
v∈V 我们假设
[
v
]
E
:
=
{
v
′
∈
V
∣
(
v
,
v
′
∈
E
)
}
[v]_E:=\{v^{'}\in V|(v,v^{'}\in E)\}
[v]E:={v′∈V∣(v,v′∈E)}
表示
v
v
v 相对于
E
E
E的等价类(即等价类
[
v
]
E
[v]_E
[v]E由
v
v
v的所有元素组成，他们根据
E
E
E与
v
v
v而等价)。
如果存在一个 W = [ v ] E W=[v]_E W=[v]E的元素 v ∈ V v\in V v∈V，那么一个集合 W ⊆ V W\subseteq V W⊆V是一个等价类(是 E E E的)
元素 v v v 叫做 等价类 W W W的代表。
例子：
下列等价关系的等价类是什么？
- 整数上的关系 R : = { ( a , b ) ∣ a = b o r a = − b } R:=\{(a,b)|a=b\ or\ a=-b\} R:={(a,b)∣a=b or a=−b}
- 本班所有学生名字上的关系 L L L ，如果名字x和y有相同数量的字母，且x和y在L中，那么 两个名字x与y属于 R R R.
(3)、顺序关系的定义(Order relations: definition)
设
E
E
E是集合
V
V
V上的一个二元关系。
1.如果
E
E
E是自反的和传递的，
E
E
E是一个前序
2.如果
E
E
E是自反的、传递的和反对称的，
E
E
E是一个偏序
3.如果
E
E
E是自反的、传递的、反对称的和全数的，
E
E
E是一个线性序列或者全数序列。
例子：
1.
≤
\le
≤是
N
N
N(以及
Z
Z
Z、
Q
Q
Q 和
R
R
R)上的一个线性序列。相似的，
≥
\ge
≥是
N
N
N(以及
Z
Z
Z、
Q
Q
Q 和
R
R
R)上的一个线性序列。
2.对每一个集合
M
M
M，关系
⊆
\subseteq
⊆和
⊇
\supseteq
⊇在幂集
P
(
M
)
P(M)
P(M)(不是线性序列)上是部分序列。
"
⊆
"
"\subseteq"
"⊆" 和
M
=
{
1
,
2
}
M=\{1, 2\}
M={1,2} 的图解：
3.对每一个有限集
M
M
M，
E
:
=
{
(
A
,
B
)
∣
A
,
B
⊆
M
,
∣
A
∣
≤
∣
B
∣
}
E:=\{(A,B) | A,B\subseteq M, |A|\le |B|\}
E:={(A,B)∣A,B⊆M,∣A∣≤∣B∣}是一个在
P
(
M
)
P(M)
P(M)上的前序，但不是一个偏序。
M
=
1
,
2
M={1,2}
M=1,2的图解：