二元关系

二元关系
定义：从A到B的二元关系\(R\subseteq A\times B\). 若\((a,b)\in R\), 记作\(aRb\).
\(dom(R) := \{a|\exists b, aRb\}\); \(ran(R):= \{b|\exists a, aRb\}.\) 类似可定义n元关系。

关系矩阵
给定二元关系\(R\subseteq A\times B\), R的关系矩阵\(M(R)=(m_{i,j})\)定义为\(m_{i,j}=1_{a_iRb_j}.\)

关系的运算
\(R_1\cap R_2, R_1\cup R_2, R_1-R_2, \bar{R_1}\)可类似集合运算定义。

逆运算\(R^{-1}=\{(b,a)|aRb\}.\) \(M(R^{-1}) = (M(R))^T.\)

复合运算 \(R_3= R_1\circ R_2=\{(a,c)|\exists b, aR_1 b\land bR_2 c\}\)
运算律：
(1) 结合律
(2) 分配律
\(R_1\circ(R_2\cup R_3) = (R_1\circ R_2)\cup (R_1\circ R_3)\)
\(R_1\circ(R_2\cap R_3) = (R_1\circ R_2)\cap (R_1\circ R_3)\)
(3) \( (R_1\circ R_2)^{-1} = R_2^{-1}\circ R_1^{-1}\)

幂运算
\(R^{n+1}:=R^n\circ R\).

连通关系 \(R^\infty=\cup^{\infty}_1 R^n\). 当基集为有限集合时，连通关系表示有向道路。

定理1. 设A是n元集，R是A上二元关系。则存在\(0\le s < t\le 2^{n^2}\)使得\(R^s=R^t\).

定理2. 设R是n元集A上的二元关系，则\[R^\infty = \bigcup_{i=1}^n R^i\]

关系的性质
(1) 自反性 \(aRa\), \(I_A\subset R\)
(2) 反自反性 \(\lnot aR a\), \(I_A\cap R=\emptyset\)
(3) 对称性 \(aRb\Rightarrow bRa\), \(R=R^{-1}\), \(M(R)\)是对称矩阵
(4) 反对称性 \(aRb\land bRa\Rightarrow a=b\), \(R\cap R^{-1}\subseteq I_a\).
(5) 斜对称性 \(aRb\Rightarrow \lnot bRa\)
(6) 传递性 \(aRb, bRc\Rightarrow aRc\), \(R\circ R\subseteq R\).

关系的闭包
对于A上的二元关系R，用\(r(R), s(R), t(R)\)分别表示包含R的最小自反、对称、传递的二元关系。
显式表达：
\(r(R) = R\cup I_A\);
\(s(R) = R\cup R^{-1}\);
\(t(R) = \bigcup_{i=1}^\infty R^i\).

闭包的运算性质
(1) \(r(R_1\cup R_2 ) = r(R_1)\cup r(R_2)\)
(2) \(s(R_1\cup R_2 ) = s(R_1)\cup s(R_2)\)
(3) \(t(R_1\cup R_2 ) \supseteq t(R_1)\cup t(R_2)\)

R的传递闭包也记作\(R^+\)，自反传递闭包\(R^*\).

等价关系
满足自反、对称和传递的二元关系称为等价关系。
设R是A上的等价关系，记\([a]_R\)为元素a关于R的等价类。R的所有等价类组成的集合称为A关于R的商集，记作\(A/R\)。

序关系
偏序关系：自反，反对称和传递的二元关系。常记为\(\le\) .
具有偏序关系的集合A称为偏序集\((A,\le)\)。
一些定义：
(1) 若两元素x, y满足\(x\le y\)或\(y\le x\), 称x和y是可比的。
(2) 若\(x\le y, x\ne y\), 记为\(x < y\).
(3) 若\(x < y, \not\exists z. x< z < y\). 称y覆盖x。

拟序关系：反自反，传递的二元关系。拟序关系一定是反对称的。
拟序关系与偏序关系相差一个\(I_A\).

全序关系：偏序关系中，任两元素可比大小。

定义. 设P是偏序集, \(B\subseteq P\).
(1) 若\(b\in B, \forall b'\in B, b'\le b\). 称b为最大元。
(2) 若\(b\in B, \not\exists b' \in B, b\le b'\). 称b为极大元。
(3) 若\(a\in P, \forall b\in B, b\le a\). 称a是B的一个上界。
(4) 若a是B的一个上界，且\(\forall a'\)也是上界，均满足\(a'\le a\). 称a是B的上确界。

偏序集的子集也是偏序集。链和反链是两种特殊的子偏序集。
定义. 设P是偏序集, \(B\subseteq P\).
(1) 若B中任两元素可比大小，称B是P中一条链。
(2) 若B中任两元素不可比大小，称B是P中一条反链。

Mirsky定理. 设P是偏序集。若P中最长链的长度为h，则
(1) P中存在极大元。
(2) P可划分为h块，每块都是反链。
推论. 设P是偏序集，\(|P|=n, m_1m_2< n.\) 则P存在长度为\(m_1+1\)的链，或存在长度为\(m_2+1\)的反链。

Dilworth定理. 设P是偏序集，P中最长反链的长度为w，则P可划分为w块，每块都是链。

Zorn引理. 若偏序集P的每个链都有上界，则P存在极大元。
选择公理. 若非空集A的子集族\(\{A_\alpha\}_{\alpha\in S}\)中的任意元素都非空，则存在函数\(f:S\to A, f(\alpha)\in A_\alpha.\)

良序关系：全序集P中，P的任何非空子集B都有最小元。
超限归纳原理. 设W为良序集，\(p(a)(a\in W)\)是关于a的一个命题，若
(1) 对于W中最小元e， \(p(e)\)成立；
(2) \(\forall a\in W(a > e)\), 若命题p对\(\forall a' < a\)成立，可以推出\(p(a)\)成立。
则命题对\(\forall a\in W\)成立。

保序与同构
设P，Q是两个偏序集。
(1) 称函数\(f:P\to Q\)是保序的，若\(x < y \Rightarrow f(x) \le f(y)\); 若P，Q都是全序集，称保序函数为单调递增的。
(2) 若\(f:P\to Q\)是双射，且\(f,f^{-1}\)都是保序的，称f是P到Q的同构，此时称P同构于Q。

引理1. W良序，f严格单调递增。则\(f(x) \ge x, \forall x\in W\).
推论2. 良序集上的自同构必是恒等函数。
推论3. 若良序集同构，则同构函数唯一。

定义. W良序，\(u\in W.\) 称\[W(u)=\{x|x < u\}\]为W的一个初始片段。

推论4. 良序集不可能同构于它自己的初始片段。
定理5. 设\(W_1, W_2\)良序。则以下之一成立：
(1) \(W_1, W_2\)同构；
(2) \(W_1\)同构于\(W_2\)的某初始片段；
(3) \(W_2\)同构于\(W_1\)的某初始片段。

定理6. 任何非空集合都可以良序化。

    所属分类：离散数学     发表于2022-03-24