关系

 从某种意义上来说，关系是一个比函数更为广泛的概念。本节将给出数学研究中常常出现的两种关系：等价关系和全序关系。
 定义 集合\(A\)上的一个关系（relation）是笛卡尔积\(A\times A\)的一个子集\(C\)。
 如果\(C\)是\(A\)中的一个关系，我们用记号\(xCy\)表示\((x,y)\in C\)，读作“\(x\)与\(y\)有关系\(C\)”。
 前面我们所学到的函数\(f:A\rightarrow A\)的指派法则\(R\)其实也是一种特殊的关系，它使得\(A\)的每一个元素作为\(R\)的元素的第一个分量恰好出现一次。而\(A\times A\)的任意子集都是关系。
等价关系与分拆

 集合\(A\)中的一个等价关系（equivalence relation）是\(A\)上满足下面三条性质的一个关系\(C\)：
 (1)（自反性）对于\(A\)中每一个\(x\)，有\(xCx\)；
 (2)（对称性）若\(xCy\)，则\(yCx\)；
 (3)（传递性）若\(xCy\)和\(yCz\)，则\(xCz\)。
 虽然关系是一个集合，但并不一定要用大写字母或任何类型的字母来记关系。用另外的符号将更为合适。经常用以表示一个等价关系的是波浪号\(\sim\)。应用这个记号，等价关系的性质可写成：
 (1)（自反性）对于\(A\)中每一个\(x\)，有\(x\sim x\)；
 (2)（对称性）若\(x\sim y\)，则\(y\sim x\)；
 (3)（传递性）若\(x\sim y\)和\(y\sim z\)，则\(x\sim z\)。
 不难看出，等价关系将我们最常见的等于关系=进行了推广，使其能在更广泛的集合、更多样的意义下使用。学习等价关系时，读者可以参照=进行类比学习，但要注意区分二者的不同。
 给定集合\(A\)的一个等价关系\(\sim\)，和\(A\)的一个元素\(x\)，可以由下式定义\(A\)的子集\(E\)，称为由\(x\)决定的等价类（equivalence class）:

\[E=\{y|y\sim x\}\]
注意，由\(x\)决定的等价类\(E\)包含\(x\)，这是因为\(x\sim x\)，等价类具有以下性质：
 引理 3.1 两个等价类\(E\)和\(E'\)或者无交或者相等。
 证明 设\(E\)是由\(x\)决定的等价类，\(E'\)是由\(x'\)决定的等价类。若\(E\cap E'\ne \varnothing\)，则有\(y\in E\cap E'\)。下面证明\(E=E'\)。
 根据定义可知\(y\sim x\)和\(y\sim x'\)。根据对称性可知\(x\sim y\)和\(y\sim x'\)。应用传递性则有\(x\sim x'\)。若\(w\)为\(E\)的任意一点，根据定义有\(w\sim x\)。再用一次传递性得到\(w\sim x'\)。因此\(E\subset E'\)。
 可以完全对称地推出\(E'\subset E\)，所以\(E=E'\)。

$\square$

 给定集合$A$上的一个等价关系，用$\mathcal{E}$记由这个关系决定的所有等价类的族。上述引理证明了$\mathcal{E}$中不同元素无交。进一步，由于$A$的每一个元素属于某一等价类中，于是$\mathcal{E}$中元素的并等于$A$。族$\mathcal{E}$就是称之为$A$的分拆的一特例。 定义 集合\(A\)的一个分拆（partition）是\(A\)的无交非空子集的一个族，其并是\(A\)。
 所谓的分拆，其实就是将集合\(A\)像切西瓜一样分成几个无交非空子集，并将这些子集放在一个集合内。
 既然\(A\)的每一个等价关系都对应于\(A\)的一个分拆，那么\(A\)的每一个分拆是否对应一个等价关系呢？答案是肯定的。要证明这一点并不难。对于\(A\)的分拆\(\mathcal{E}\)，我们定义\(A\)上的等价关系\(C\)为

\[xCy\iff \text{存在}E\in \mathcal{E},\text{使得}x,y\in E\]
 要验证\(C\)的自反性，注意到\(\mathcal{E}\)的并是\(A\)，对任意\(x\in A\)，一定存在\(E\in \mathcal{E}\)，使得\(x\in E\)。故\(xCx\)。对称性的验证显然。而对于传递性，当\(xCy\)，\(yCz\)时，有\(x,y\in E\)，\(y,z\in E'\)，\(E\)和\(E'\)都含\(y\)，其不是无交的。由\(\mathcal{E}\)的无交性可知\(E=E'\)，故\(x,z\in E=E'\)，有\(xCz\)。容易验证，\(C\)是由\(\mathcal{E}\)唯一确定的，我们定义的\(C\)的等价类就是\(\mathcal{E}\)。总之，一个集合上的等价关系与该集合的分拆一一对应。
序关系

 集合\(A\)中的一个关系\(C\)称为序关系（order relation）（或全序（simple order），线序（linear order）），如果满足下列性质：
 (1)（可比较性）对于\(A\)中满足\(x\ne y\)的每一个\(x\)和\(y\)，或者\(xCy\)，或者\(yCx\)；
 (2)（非自反性）\(A\)中没有\(x\)，使得\(xCx\)成立；
 (2)（传递性）若\(xCy\)并且\(yCz\)都成立，则\(xCz\)。
具有全序关系\(C\)的集合\(A\)我们称之为全序集（totally ordered set）。
 请注意，性质(1)并没有排除\(A\)中可能有某元素偶对\(x\)，\(y\)，使\(xCy\)和\(yCx\)都成立（还记得基本概念这一节中集合的“并”与“或”的含义关于“或”含义的讨论吗？）。但是与性质(2)和(3)合在一起，就排除了这种可能：如果\(xCy\)和\(yCx\)都成立，由传递性可知\(xCx\)，这与非自反性矛盾。

 不难发现，其实序关系是大于关系\(>\)和小于关系\(