关系

写法习惯注意

本文以下内容表示$x,y$的一个二元关系$R$的写法表现为$(x,y)\in R$ 也有如同 $xRy$ 表示二元关系的

五种关系

由集合$S$上的元素构成二元关系$R$

• 自反
  • 定义：对于 $\forall x\in S$ 都有 $(x,x)\in R$
  • 证明思路：
    • 设$x\in S$
    • 根据基于$R$的具体定义构造x与x的关系并且满足于R
    • 因此$(x,x)\in R$
• 对称
  • 定义：$\forall x,y\in S$,如果 $(x,y)\in R$,那么$(y,x)\in R$
  • 证明思路：
    • 设$x，y\in S$且$(x,y)\in R$
    • 根据$(x,y)\in R$ 与$R$的具体定义，推导出$y$与$x$也满足关系 $R$
    • 因此$(y,x)\in R$
• 传递
  • 定义：$\forall x,y,z\in S$,如果$(x,y)\in R$且$(y,z)\in R$ 那么 $(x,z)\in R$
  • 证明思路：
    • 设 $x,y,z\in S$ 且 $(x,y)\in R\text{and}(y,z)\in R$
    • 根据$R$推导出$x$与$z$也满足关系
    • 因此$(x,z)\in R$
• 反对称
  • 定义：$\forall x,y\in A$ 如果$(x,y)\in R$且$(y,x)\in R$ 那么$x=y$
  • 证明思路：
    • 设$x,y\in S$ 且 $(x,y)\in R$ 且 $(y,x)\in R$
    • 根据$R$推导出如果假设成立则必须有$x=y$
    • 因此 $x=y$,故$R$是反对称的

等价类

等价类代表某一特性在这个等价关系中是 等价的 如在$x\equiv y(\mathrm{mod}3)$关系下有三个等价类： $[0]=\{x|x\mathrm{mod}3=0,x\in I\}$ $[1]=\{x|x\mathrm{mod}3=1,x\in I\}$ $[2]=\{x|x\mathrm{mod}3=2,x\in I\}$

等价关系与偏序关系

若一个二元关系R满足自反 对称 传递 则这个二元关系为等价关系 若一个二元关系R满足自反 反对称 传递 则这个二元关系为偏序关系

关系的运算

关系的复合运算一般使用矩阵形式展开

$$A_{ij}=\{\begin{array}{ll}1& (i,j)\in R\\ 0& (i,j)\notin R\end{array}$$

• 复合关系 $R\circ S$ 则使用$R$矩阵与$S$矩阵进行矩阵乘法
• 逆关系矩阵为原矩阵的转置