二元关系

  • 两个对象之间的联系的数学模型，罗列所有有联系的对象，表示为二元组。
  • 集合XX和YY
  • XX到YY的二元关系： X×YX×Y的子集
  • XX上的二元关系： XX到XX的二元关系
  • x,yx,y满足关系R(xRy)R(xRy)：(x,y)∈R(x,y)∈R,xx是yy的前件，yy是xx的后件

定义域，值域

  • RR是XX到YY的二元关系
  • 定义域：dom(R)={x∣x∈X∧∃y∈Y,s.t.(x,y)∈R}⊆Xdom(R) = \{x|x\in X \wedge \exists y \in Y ,s.t. (x,y)\in R\} \subseteq X
  • 值域：ran(R)={y∣y∈Y∧∃x∈X,s.t.(x,y)∈R}⊆Yran(R) = \{y|y\in Y \wedge \exists x \in X ,s.t. (x,y)\in R\} \subseteq Y

特殊关系

  • 空关系：ϕ\phi
  • 全关系：X×YX\times Y
  • 恒等关系：Ix={(x,x)∣x∈X}I_x = \{(x,x)|x\in X\}

二元关系的表示

关系图

  • 有向图，顶点表示XX和YY中的元素，左边一列顶点表示XX中的元素，右边一列顶点表示YY中的元素，顶点xx到yy的有向边(箭头)存在 ⇔(x,y)∈R⇔ (x,y)∈R
  • 如果X=YX=Y，则XX中的元素不重复画两次

关系矩阵

X={x1,x2,...,xm},Y={y1,y2,...yn}X = \{x_1,x_2,...,x_m\},Y = \{y_1,y_2,...y_n\}

MR=(rij)m×n=[r11r12...r1nr21r22⋯r2n⋮⋮⋮rm1rm2⋯rmn]M_R=(r_{ij})_{m\times n}=\begin{bmatrix}r_{11}&r_{12}&...&r_{1n}\\r_{21}&r_{22}&\cdots&r_{2n}\\\vdots&\vdots&&\vdots\\r_{m1}&r_{m2}&\cdots&r_{mn}\end{bmatrix}

rij={1(xi,yj)∈R0(xi,yj)∉R\mathrm{r_{ij}=}\begin{cases}1&(x_i,y_j)\in R\\0&(x_i,y_j)\notin R\end{cases}

一些性质

  • 关系矩阵的元素之和=关系的基数
  • 关系矩阵的元素之和=关系图中的箭头的个数
  • 集合上的关系的关系矩阵必定是方阵
  • 关系成为函数 ⇔ 关系图中，左边每个顶点的出度均为1 ⇔ 关系矩阵中，每行有且仅有一个1

n元关系

  • 集合X1,X2,...XnX_1,X_2,...X_n上的nn元关系是X1×X2×...×XnX_1\times X_2 \times ... \times X_n的子集

关系的运算

  • 实际上就是集合的运算：交，并，差，补。(此时全集为X×YX\times Y)
  • RR在YY上的限制：YY上的关系RR是XX上的关系，Y⊆XY⊆X，{(x,y)∣x,y∈Y，且(x,y)∈R}\{(x,y)|x,y∈Y，且(x,y)∈R\}

关系的逆

  • RR是XX到YY的关系
  • RR的逆关系R−1R^{-1}：YY到XX的二元关系，{(y,x)∣(x,y)∈R}\{(y,x)|(x,y)∈R\}

关系的复合

  • 关系RR和SS的复合R∘SR∘S：XX到ZZ的关系，RR是XX到YY的关系，SS是YY到ZZ的关系
  • R∘SR∘S={(x,z)∣x∈X∧z∈Z∧∃y,s.t.y∈Y∧(x,y)∈R∧(y,z)∈S}\{(x,z)|x∈X∧z∈Z∧∃y,s.t.y∈Y∧(x,y)∈R∧(y,z)∈S\}
  • 注意
    • ∘∘的交换律不成立
    • 并非任意两个关系都可以进行复合

关系的幂

  • RR是XX上的关系，n∈Nn\in \mathbb N

Rn={IXn=0Rn−1∘Rn∈Z+R^n=\begin{cases}I_X&n=0\\R^{n-1}\circ R&n\in Z\end{cases}+

关系运算的性质

  • (R−1)−1=R(R^{-1})^{-1} = R
  • (R∩S)−1=R−1∪S−1(R \cap S)^{-1} = R^{-1} \cup S^{-1}
  • (R∪S)−1=R−1∩S−1(R \cup S)^{-1} = R^{-1} \cap S^{-1}
  • (R∘S)−1=S−1∘R−1(R \circ S)^{-1} = S^{-1} \circ R^{-1}
  • (R∘S)∘T=R∘(S∘T)(R\circ S) \circ T = R\circ (S \circ T)
  • XX上的关系RR，∀m,n∈N,Rm+n=Rm∘Rn∀m,n∈N,R^{m+n}=R^m∘R^n
  • ∀(x,y)，(x,y)∈Rn∀(x,y)，(x,y)∈R^n ⇔⇔ ∃n+1∃ n+1元组 (x0,x1,x2,…,xn)∈Xn+1(x_0,x_1,x_2,…,x_n)∈X^{n+1}，(xi,xi+1)∈R，(i=0,1,…,n−1)，x0=x，xn=y(x_i,x_{i+1})∈R，(i=0,1, …,n-1)，x_0=x，x_n=y
  • XX：有限集， ∣X∣=n，n∈Z+|X|=n，n∈Z^+ ， RR：XX上的关系，x,y∈Xx,y∈X，m∈Nm∈N，(x,y)∈Rm,∃k∈N，k≤n(x,y)∈R^m , ∃k∈N，k≤n，使(x,y)∈Rk(x,y)∈R^k
  • XX：有限集， ∣X∣=n，n∈Z+|X|=n，n∈Z^+，RR：XX上的关系,⋃m∈Z+Rm=⋃m=1nRm\bigcup_{m\in\mathbb{Z}^+}{R}^m=\bigcup_{m=1}^n{R}^m

关系的特殊性质

  • 自反关系(reflexive)：∀x∈X，(x,x)∈R∀x∈X，(x,x)∈R

  • 反自反关系(anti-reflexive)： ∀x∈X，(x,x)∉R∀x∈X，(x,x)\not \in R

  • 对称关系(symmetric)： ∀x,y∈X，(x,y)∈R∧(y,x)∈R∀x,y∈X，(x,y)∈R \wedge (y,x)∈R

  • 反对称关系(anti-symmetric)：∀x,y∈X，(x,y)∈R∧(y,x)∈R，则x=y∀x,y∈X，(x,y)∈R ∧ (y,x)∈R ，则x=y

  • 传递关系(transitive)：∀x,y,z∈X，(x,y)∈R∧(y,z)∈R，则(x,z)∈R∀x,y,z∈X，(x,y)∈R ∧ (y,z)∈R ，则 (x,z)∈R

  • RR自反 ⇔⇔ IX⊆RI_X⊆R

  • RR反自反 ⇔⇔ R∩IX=∅R∩I_X=∅

  • RR对称 ⇔⇔ R−1=RR^{-1}=R

  • RR反对称 ⇔⇔ R∩R−1⊆IXR∩R^{-1}⊆I_X

  • RR传递 ⇔⇔ R2⊆RR^2⊆R

  • RR传递 ⇔⇔ ∀n∈Z+，Rn⊆R∀n∈Z^+，R^n⊆R

关系的性质与关系矩阵的性质

  • 关系自反 ⇔ 其矩阵对角线全1
  • 关系反自反 ⇔ 其矩阵对角线全0
  • 关系对称 ⇔ 其矩阵对称
  • 关系反对称 ⇔ 其矩阵任意两不同对称位置上至少有一个0

关系的性质与关系图的性质

  • 关系自反 ⇔ 其关系图每个顶点都有环
  • 关系反自反 ⇔ 其关系图每个顶点均无环
  • 关系对称 ⇔ 其关系图每对顶点之间若有边则必有两条方向相反的边
  • 关系反对称 ⇔ 其关系图每对顶点之间至多只有一条边

关系的闭包

  • P闭包：包含RR、具有性质PP、最小的XX上的关系，RR：XX上的关系，PP：一种关系的性质

  • RR的PP闭包RPR^P是XX上的关系，满足：

    • P(RP)P(R^P)，即该关系是闭包的,RpR^p具有性质PP
    • R⊆RPR⊆R^P，即该关系包括了RR
    • ∀X∀X上的关系R′R'，若P(R′)P(R')且R⊆R′R ⊆R'，则RP⊆R′R^P⊆R' ，即该关系最小

  • 自反闭包r(R)r(R)：XX上包含RR的最小的自反关系

  • 对称闭包s(R)s(R)：XX上包含RR的最小的对称关系

  • 传递闭包t(R)t(R)：XX上包含RR的最小的传递关系

  • r(R)=R∪IXr(R)=R∪I_X

  • s(R)=R∪R−1s(R)=R∪R^{-1}

  • t(R)=⋃n=1∞Rnt(R)= \bigcup_{n=1}^{\infty} R^n

等价关系与等价类

  • 集合XX上的等价关系： XX上自反、对称、传递的关系

  • xx关于RR的等价类[x]R[x]_R：{y∣y∈X∧yRx}⊆X\{y | y∈X\wedge yRx\}⊆X,RR：XX上的等价关系，x∈Xx∈X,等价类[x]R[x]_R的代表元：xx

  • 若RR是XX上的等价关系，那么对于任意x,y∈Xx,y \in X

    • 若(x,y)∈R(x,y)\in R，[x]R=[y]R[x]_R = [y]_R，等价类中的任意元素都可以作为该等价类的代表元，
    • 若(x,y)∉R(x,y)\not \in R，[x]R∩[y]R=ϕ[x]_R \cap [y]_R = \phi，任意两个等价类要么是同一类要么没有公共元素
    • ⋃z∈X [z]R=X\bigcup_{z\in X}\space[z]_R = X，

商集

  • XX关于RR的商集X/RX/R：XX关于RR的所有等价类所组成的集合 X/R={[x]R∣x∈X}X/R=\{[x]_R|x∈X\},RR：XX上的等价关系

划分

  • 集合XX的划分π\pi，π\pi是XX的子集构成的集合族，π⊆P(X)\pi \subseteq P(X),满足：

    • ϕ∉π\phi \not \in \pi
    • ∀A,B∈π,A=B∨A∩B=ϕ\forall A,B\in \pi,A=B\vee A\cap B = \phi
    • ⋃A∈π A=X\bigcup_{A\in \pi} \space A =X

  • 若RR是XX上的等价关系，那么商集X/RX/R是XX的划分πR\pi_R。

  • 设π\pi是集合XX的划分，那么R:{(x,y)∣x,y属于π的同一个划分块}R:\{(x,y)|x,y属于\pi的同一个划分块\}是XX上的等价关系RπR_{\pi}

  • 等价关系和划分是集合元素分类的两种描述方法，二者本质上是同一事物的两个不同方面

偏序关系

  • XX上的偏序关系：XX上自反、反对称和传递的关系

  • xx和yy关于偏序≤≤是可比较的 ⇔ x≤y∨y≤xx≤y\vee y≤x

  • xx在yy的前面，yy在xx的后面：x≺yx\prec y，y≻xy \succ x

  • xx不在yy的后面，yy不在xx的前面：x⪯yx\preceq y，y⪰xy\succeq x

  • 这里的关系元素之间存在某种次序。

  • 全序(关系)：XX上的偏序≺\prec,∀x,y∈X∀x,y∈X，x⪯y∨y⪯xx\preceq y \vee y\preceq x，偏序是全序 ⇔ 任一元素对都可比较

  • 偏序集：二元组(X,≤)(X,≤)， ≤≤是集合XX上的偏序

  • 全序集：偏序集 (X,≤)(X,≤)，≤≤是集合XX上的全序

哈斯图

  • 偏序集(X,≤)(X,≤)，x,y∈Xx,y∈X，yy覆盖(cover)xx：(x<y)∧(¬∃z∈X，使x<z<y)(x<y )∧( ¬∃z∈X，使x<z<y), yy是xx的直接后继.
  • 哈斯图是有限偏序集的简化关系图，
    • 顶点xx到顶点yy有边 ⇔ yy覆盖xx，且y位于x上方
    • 省略所有的箭头：箭头总是从下方指向上方

偏序集的性质

  • 最大(小)元：比所有其他元素都大(小)的元素，∀x∈X，x≤a(a≤x)∀x∈X，x≤a(a≤x)

  • 极大(小)元：不存在比它更大(小)的元素，但允许存在与它不可比较的元素,¬∃x∈X，a<x(x<a)¬∃x∈X，a<x(x<a)

  • 最大(小)元至多只有一个，也可以没有

  • 极大(小)元可以有多个，也可以没有

  • 极大(小)元不一定是最大(小)元，最大(小)元一定是极大(小)元

  • 当最大(小)元存在时，极大(小)元也只有一个

  • 全序集的极大(小)元一定是也最大(小)元，全序集的“最大(小)”和“极大(小)”没有区别

  • 非空有限偏序集必有极大元和极小元

拓扑序列

  • 算法：从小到大，每次找出一个极小元，删除，再重复。
  • 设(X,≤)(X,≤)是有限偏序集,∣X∣=n|X|=n，则∃(x1,x2,…, xn)∈Xn∃(x_1, x_2,…,  x_n)∈ X^n  ,使得对任意i,j∈Z+i,j∈Z^+ ，若xi≤xjx_i≤x_j,则必有i≤j(1≤i,j≤n)i ≤ j(1≤ i, j ≤ n)，这个序列称为XX关于≤≤的拓扑序列。

格

确界

设(X,≤)(X,≤)是偏序集，Y⊆XY⊆X，a∈Xa∈X

  • 若对∀y∈Y∀y∈Y,∃a∃a, y≤ay≤a, 称aa为YY在(X,≤)(X,≤)中的上界(upper bound)。
  • 若∃Y∃Y的上界bb，∀Y∀Y的上界aa，有b≤ab≤a，则称bb为YY在(X,≤)(X,≤)中的最小上界(least upper bound)或上确界(supremum)，记为sup(X,≤)Ysup_{(X,≤)} Y。
  • 若对∀y∈Y∀y∈Y, ∃a∃a, a≤ya≤y, 称aa为YY在(X,≤)(X,≤)中的下界(lower bound) 。
  • 若∃Y∃Y的下界b，∀Y∀Y的下界aa，有a≤ba≤b，则称bb为YY在(X,≤)(X,≤)中的最大下界(greatest lower bound)或下确界(infimum)，记为inf(X,≤)Yinf_{(X,≤) } Y。
  • 对于任意偏序集的任意子集，其上确界至多只有一个，因为其最小性；同理，其下确界也至多只有一个。

格

  • 如果一个偏序集的每对元素都有上确界和下确界，则称该偏序集为格。
  • (P(S),⊆)(P(S), ⊆)是格，其中SS是集合
  • 任意全序集都是格