# 关系

# $n$ 元关系和二元关系

关系采用集合进行定义。一个 $n$ 元关系 (relation) 是 $A^n$ 的子集。我们称 $a_1, a_2, \dots, a_n$ 具有 $n$ 元关系 $R$, 当且仅当 $(a_1, a_2, \dots, a_n) \in R$, 记作 $R(a_1, a_2, \dots, a_n)$.

特别地，非空集合 $A$ 上的一个二元关系 (binary relation) $R$ 定义为 $A \times A$ 的一个子集。若 $(a_1, a_2) \in R$, 那么称 $a_1, a_2$ 具有关系 $R$, 记作 $R(a_1, a_2)$ 或 $a_1 R a_2$.

# 等价关系和等价类

# 等价关系

对于 $A$ 上的二元关系 $R$, 若有

1. 反身性 (reflexive), 即 $aRa,\forall a \in A$.
2. 对称性 (symmetric), 即 $a_1Ra_2 \iff a_2Ra_1$.
3. 传递性 (transitive), 即 $a_1Ra_2,\, a_2Ra_3\,\Rightarrow a_1Ra_3$.

那么我们称 $R$ 是一个等价关系 (equivalence relation), 通常用 $\sim$ 表示。此时 $a_1$ 与 $a_2$ 等价，记作 $a_1 \sim a_2$.

# 集合的划分

若对集合 $A$, 存在一系列集合（有限个或无限个） $A_1, A_2, \dots, A_n, \dots$ 满足：

1. $A_i \cap A_j = \varnothing, \forall i, j \in \mathbb{N}_+, i \neq j$.
2. $\bigcup_{i=1}^\infty A_i = A$.

那么，称 $\{A_i|i \in \mathbb{N}_+\}$ 是集合 $A$ 的一个划分 (partition), 也称为 $A$ 的一个商集 (quotient set).

# 等价类

若 $A$ 上有等价关系 $\sim$, 那么 $\forall a \in A$, 称集合

$$\bar{a} \coloneqq \{x \in S|x \sim a\}$$

是 $a$ 的等价类，也记作 $[a]$, 并称 $a$ 是等价类 $\bar{a}$ 的一个代表元。

关于等价类，有如下基本性质：

1. $x \sim a \iff x \in \bar{a}$.
2. $\bar{a} = \bar{b} \iff a \sim b$.
3. 若 $\bar{a} \neq \bar{b}$, 则 $\bar{a} \cap \bar{b} = \varnothing$.
4. 若集合 $A$ 上存在等价关系 $\sim$, 则所有等价类组成的集合是 $A$ 的一个划分。

# 偏序关系和对偶原理

# 偏序关系

对于 $A$ 上的二元关系 $R$, 若有

1. 反身性 (reflexive), 即 $aRa,\forall a \in A$.
2. 反对称性 (antisymmetric), 即 $a_1Ra_2, a_2Ra_1 \Rightarrow a_1 = a_2$.
3. 传递性 (transitive), 即 $a_1Ra_2,\, a_2Ra_3\,\Rightarrow a_1Ra_3$.

那么我们称 $R$ 是一个偏序关系 (partial relation), 通常用 $\preceq$ 表示。

# 格

若

# 映射

# Ref

• 湫沨：离散数学笔记（8.1）格的基本概念