定义

关系 $:=$ 空集/元素全是有序对的集合

• 从 $A$ 到 $B$ 的二元关系 $:= \forall R \subset A\times B$
• $A$ 的二元关系 $:= \forall R \subset A\times A$
• 若 $\langle x,y \rangle \in R$，则 $xRy$

特殊关系

• 空关系 $\emptyset$
• 全域关系 $E_{A}:=A\times A$
• 恒等关系 $I_{A}:=\left{ \left< x,x \right> | x \in A \right}$
• 小于等于关系 $L_{A}:=\left{ \left< x,y \right>|x,y\in A,x\leq y \right}$
• 整除关系 $D_{A}:=\left{ \left< x,y \right> | x,y \in A, x|y \right}$
• 包含关系 $R_{\subset}:=\left{ \left< x,y \right> | x,y \in A, x \subset y \right}$

运算

• 取定义域 $\mathrm{dom}R := \left{ x | \left< x,y \right> \in R \right}$
• 取值域 $\mathrm{ran}R := \left{y|\left< x,y \right> \in R\right}$
• 取域 $\mathrm{fld}R:=\mathrm{dom}R\cup \mathrm{ran}R$
• 逆关系 $R^{-1} := \left{\left< x,y \right>|\left< y,x \right>\in R\right}$
  • $(F^{-1})^{-1}=F$
  • $\mathrm{dom}F^{-1}=\mathrm{ran}F$, $\mathrm{ran}F^{-1}=\mathrm{dom}F$
• 右复合 $F \circ G := \left{ \left< x,y \right> | \left< x,t \right> \in F \land \left< t,y \right>\in G \right}$
  • 结合律 $(F \circ G) \circ H = F \circ (G\circ H)$
  • 类矩阵逆 $(F\circ G)^{-1}=G^{-1}\circ F^{-1}$
  • 并等分配
    • $F \circ (G \cup H) = (F \circ G) \cup (F \circ H)$
    • $(G \cup H) \circ F = (G \circ F) \cup (H \circ F)$
  • 交子分配
    • $F \circ (G \cap H) \subset (F \circ G) \cap (F \circ H)$
    • $(G \cap H) \circ F \subset (G \circ F) \cap (H \circ F)$
• 限制 $R|_{A}:=\left{\left< x,y \right>| xRy \land x \in A \right}$
• 像 $R[A]:=\mathrm{ran}R|_{A}$

特殊性质

• 自反性 $\forall a\in A$ 且 $R=A\times A$ 且 $aRa$
• 对称性 $aRb \Rightarrow bRa$
• 传递性 $xRz \land zRy \Rightarrow xRy$
  • 证 $R \circ R = R$
  • 证 $\forall\left<x,y\right>\in R$ $\exists z (\left<x,z\right>\in R \land \left<z,y\right>)$