二元关系
二元关系
pcfx一、有序对与笛卡儿积
有序对就是std::pair误（
有序对：由两个元素x，y按照一定顺序组成的二元组，记作<x,y>。其中x是它的第一元素，y是它的第二元素。
有序对的性质
- 有序性，\(<x,y>\ne<y,x>(当x\ne y时)\)
- \(<x,y> = <u,v>\Leftrightarrow x=u \land y=v\)
笛卡尔积
- 设A，B为集合，由A的元素作为第一元素，B的元素作为第二元素组成的全部有序对的集合。
- 记作：\(A\times B\)
- 元素个数：\(假设|A|=m,|B|=n。那么|A\times B|=mn。\)
笛卡尔积的性质
- 不适合交换律
- \(A\times B \ne B \times A(A\neq B,A\neq \emptyset,B\neq \emptyset)\)
- 不适合结合律
- \((A\times B)\times C\neq A\times(B\times C)(A\neq \emptyset,B\neq \emptyset,c\neq \emptyset)\)
- 对于\(\cup\)或\(\cap\)运算满足分配率
- \(A\times(B\cup C)=(A\times B)\cup(B\times C)\)
- \(A\times(B\cap C)=(A\times B)\cap(B\times C)\)
- \((B\cup C)\times A=(B\times A )\cup(C\times A)\)
- \((B\cap C)\times A=(B\times A)\cap(C\times A)\)
- 若A或B有一个是空集，则\(A\times
B\)就是空集
- \(A\times \emptyset=\emptyset \times B=\emptyset\) 5 \(A\subseteq C\land B\subseteq D \Rightarrow A\times B\subseteq C\times D\)
二、二元关系的定义与表示法
关系的定义
如果一个集合满足一下条件之一：
- 集合非空，且它的元素都是有序对
- 集合是空集 则称该集合为一个二元关系，简称关系，记作R 如果\(<x,y>\in R\)，可记作\(xRy\)
A到B的二元关系：\(A\times B\)的任何子集所定义的关系R\((R\subseteq A\times B)\)
A上的二元关系：\(A\times A\)的任何子集所定义的关系R\((R\subseteq A\times A)\)
二元关系的数量： 集合A，若\(|A|=n\)，则A上所有二元关系的数 是多少？
\(|A\times A|=n^2,|P(|A\times A|)|=2^{n^2}\)
关系的表示
1.枚举法
将关系中的所有有序对一一列出，写到大括号内。
如：\(R=\{ <1,2>,<a,b> \}\)
2.谓词公式法
用谓词公式来表述关系包含的有序对的共同特征，如全部有序对的第一元素与第二元素之间的关系。
如：\(R=\{ <x,y>|x<y \}\)
3.关系图法（有向图法）
\(R\subseteq A\times B\) ，用两组小圆圈（节点）分别表示A和B的元素，当\(<x,y>\in R\)时，从x到y引一条有向边。
4.关系矩阵法
设有限集\(A=\{ a_{1},a_{2},\dots,a_{m} \},B=\{ b_{1},b_{2},\dots,b_{m} \},R\subseteq A\times B\),
那么定义R的关系矩阵$ M_{R}=(r_{ij})_{m\times n}$ 其中，
\[r_{i j}=\left \{ \begin{array}{ll}1 & \text { 若 }<a_{i}, b_{j}>\in R \\ 0 & \text { 若 }<a_{i}, b_{j}>\notin R\end{array}\right.\]
特殊关系
1.空关系
\(\emptyset=\{\}\)，没有有序对。
2.完全关系
\(E_{A}=\{ <x,y>|x \in A\land y\in A \}=A\times A\) 任何两个元素中都有有序对。
3.恒等关系
\(I_{A}=\{ <x,x>|x\in A \}\) 每个元素都跟自己且只跟自己有有序对
其他关系
小于等于关系 \(L_{A}=\{<x,y>|x,y\in A\land x\le y\}\quad A:实数子集\) 类似的，还有小于关系，大于等于关系，大于关系
整除关系 \(D_{B}=\{ <x,y>|x,y\in B \land x整除y \}\quad\) \(B\)：整数子集，\(x\)是除数，\(y\)是被除数
包含（子集）关系 \(R_{\subseteq}=\{ <x,y>|x,y\in A\land x\subseteq y \}\) A:集合族 类似地，还有真包含（真子集）关系
三、关系的运算
关系的定义域，值域，域
定义域：R中所有有序对的第一元素组成的集合 \[ domR = \{ x|\exists y(<x,y>\in R) \} \] 值域：R中所有有序对的第二元素组成的集合 \[ ranR=\{ y|\exists x(<x,y>\in R) \} \] 域：定义域和值域的并集 \[ fldR=domR\cup ranR \]
关系的逆运算
\[ R^{-1} =\{ <y,x>|<x,y>\in R \} \]
关系的合成运算
\[ R \circ S =\{ <x,y>|\exists y(<x,y>\in R\land<y,z>\in S) \} \]
关系的限制与像
R在B上的限制记作\(R↾B\) \[ R\upharpoonright B=\{ <x,y>|x\in B\land xRy \} \] 把关系缩小到一个子集B
B在R上的像记作\(R[B]\) \[ R[B]=ran(R\upharpoonright B) \]
其他定理
设F，G，H，R是任意的关系 \[ (F^{-1})^{-1} =F \]
\[ domF^{-1}=ranF,ranF^{-1}=domF \]
\[ (F\circ G)\circ H = F\circ(G\circ H) \]
\[ (F\circ G)^{-1}=G^{-1}\circ F^{-1} \]
\[ R\circ I_{A}=I_{A}\circ R=R \]
\(\circ\)对\(\cup\)或\(\cap\)的分配率 设F为关系，A，B为集合
- \[ 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)\subseteq F\circ G \cap F\circ H \]
- \[ (G\cap H)\circ F \subseteq G\circ F \cap H\circ \]
\(\upharpoonright\)和像对\(\cup\)或\(\cap\)的规律
- \[ F\upharpoonright(A \cup B)=F\upharpoonright A\cup F\upharpoonright B \]
- \[ F[A\cup B]=F[A]\cup F[B] \]
- \[ F\upharpoonright(A\cap B)=F\upharpoonright A\cap F\upharpoonright B \]
- \[F[A\cap B]\subseteq F[A]\cap F[B]\]
关系的幂运算
设R为A上的关系，n为自然数，则R的n次幂定义为：
- \(R^0=I_{A}={<x,x>|x\in A}\)
- \(R^{n+1}=R^{n}\circ R\)
我看到这个式子时，想到一个问题，因为关系的合成运算式子左右不能交换 但是其实对同一个关系R做符合，且关系的合成满足结合律，所以放在左边乘和放在右边乘结果是一样的。
四、关系的性质
注意：下面讨论的关系都是集合A上的关系，也就是A到A的关系
自反性
若\(\forall x(x\in A\to<x,x>\in R)\)，则称R在A上是自反的
（每一个节点都有一条自环）
反自反性
若\(\forall x(x\in A\to<x,x>\not\in R)\)，则称R在A上是反自反的
（所有节点都没有自环）
自反和反自反虽然对立，但不互补。 因为有些关系的关系图中，有些节点有自环，有些没有。
对称性
若\(\forall x\forall y(<x,y>\in R\to<y,x>\in R)\)，则称R在A上是对称的
（两个节点可以没有边，要是有边，就是双向的边）
（矩阵以对角线对称）
反对称性
若\(\forall x\forall y(<x,y>\in R\land<y,x>\in R\to x=y)\)，则称R在A上是反对称的
（两个节点可以没有边，要是有边只能有一条有项边）
（以对角线对称的两个元素最多只能有一个是1）
对称和反对称不一定对立，有些关系既可以是对称也是反对称 如：空关系，恒等关系
传递性
\(\forall x\forall y\forall z(x,y,z\in A\land<x,y>\in R\land<y,z>\in R\to<x,z>\in R)\),则称R在A上是传递的
（也就是 x到y有边，y到z有边，则x到z一定有边）
（如果两个点有双向的边，那么两个点有自环）
定理
设R为A上的关系，则
- R在A上 自反 当且仅当\(I_{A}\subseteq R\)
- R在A上 反自反 当且仅当 \(R\cap I_{A}=\emptyset\)
- R在A上 对称 当且仅当 \(R=R^{-1}\)
- R在A上 反对称 当且仅当 \(R\cap R^{-1}\subseteq I_{A}\)
- R在A上 传递 当且仅当 \(R\circ R\subseteq R\)
