离散数学：特殊关系

发表于 更新于 分类于 Waline： 阅读次数：

特殊关系

等价关系

Definition

设R是非空集合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系(equivalent relation).

以n为模的同余关系

在Z上以n为模的同余关系R中，一般记xRy为\(x\equiv y(mod n)\)(即同余式)或\(Res_n(x)=Rex_n(y)\).其中\(Res_n(x)\)表示x除以n的余数；

等价类

Definition

设R是非空集合A上的等价关系，对任意\(x\in A\)，称集合\([x]_R=\{y|y\in A,<x,y>\in R\}\)为x过R的等价类(equivalence class),或叫做由x生成的一个R等价类，其中x称为\([X]_R\)的生成元（代表元或典型元）（generator）.

Theorem

设R是非空集合A上的等价关系，则

  1. 对任意\(x\in A,[x]_R\neq \varnothing\)
  2. 对任意\(x,y\in A\)，如果\(y\in[x]_R\),则有\([x]_R=[y]_R\),否则\([x]_R\cap[x]_R=\varnothing\);
  3. \(\bigcup_{x\in A}[x]_R=A\)

商集

Definition

设R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集(quotient set),记为A/R,即\(A/R=\{[x]_R|x\in A\}\).

集合的划分

Definition

给定一个非空集合A，设有集合\(\pi =\{S_1, S_2 ,\cdots,S_m\}\)。如果满足： \[ S_i\subset A,S_i\neq \varnothing,i=1,2,\cdots,m;\\ S_i\cap S_j=\varnothing,i\neq j,i,j=1,2,\cdots,m;\\ \bigcup_{i=1}^m S_i=A. \] 则集合π称作集合A的一个划分(partition),而\(S_1,S_2,\cdots,S_m\)叫做这个划分的块(block)或类(class).

等价关系->集合划分

Theorem

设R是非空集合A上的等价关系，则A对R的商集A/R是A的一个划分，称为由R所导出的等价划分。

Theorem

给定集合A的一个划分\(\pi =\{S_1,S_2,\cdots,S_m\}\),则由该划分确定的关系\(R=(S_1\times S_1)\cup(S_2\times S_2)\cup\cdots\cup(S_m\times S_m)\)是A上的等价关系。我们称该关系R为由划分π所导出的等价关系。

偏序关系的定义

Definition

设R是非空集合A上的关系，如果R是自反的、反对称的、传递的，则称R是A上的偏序关系(partial order relation),记为\("\leq"\),读作“小于等于”，并将\(<a,b>\in \le\)记为\(a\le b\),序偶\(<A,\le >\)成为偏序集(partial order set).

可比与覆盖

设R是非空集合A上的偏序关系，\(\forall x,y\in A\),

  • 如果\(x\le y\)或\(y\le x\),则称x与y可比；
  • 如果\(x\le y\)且不存在\(z\in A\)使得\(x\le z\le y\),则称y覆盖x。

哈斯图和特殊元素

哈斯图

Definition

设R是非空集合A上的偏序关系，使用一下方法对R的关系图进行简化：

  • 取消每个结点的自环；（因自反性）
  • 取消所有由于传递性出现的边。（因传递性）
  • 重新排列每一条边，使得边的箭头方向全部向上，然后去掉这些箭头.（因反对称性）

以上步骤可以得到一个包含足够偏序信息的图，这个图为偏序关系R的哈斯图(Hasse diagram).

最大元和最小元

Definition

设\(<A,\le>\)是偏序集，B是A的任何一个子集，若存在元素\(b\in B\),使得

  • 对任意\(x\in B\),都有\(x\le b\)，则称b是B的最大元；
  • 对任意\(x\in B\),都有\(b\le x\)，则称b是B的最小元。

极大元和极小元

Definition

设\(<A,\le >\)是偏序集，B是A的任何一个子集，若存在元素\(b\in B\),使得

  • 对任意\(x\in B\),满足\(b\le x\Rightarrow x=b\),则称b为B的极大元
  • 对任意\(x\in B\),满足\(x\le b\Rightarrow x=b\),则称b为B的极小元

上界与上确界

Definition

设\(<A,\le>\)是偏序集，B是A的任何一个子集，若存在元素\(a\in A\),使得

  • 对任意\(x\in B\),满足\(x\le a\)，则称a是B的上界
  • 若元素\(a'\in A\)是B的上界，元素\(a\in A\)是B的任何一个上界，若均有\(a'\le a\),则称a'为B的最小上界或上确界

下界与下确界

Definition

设\(<A,\le>\)是偏序集，B是A的任何一个子集，若存在元素\(a\in A\),使得 - 对任意\(x\in B\),满足\(a\le x\)，则称a是B的下界 - 若元素\(a'\in A\)是B的下界，元素\(a\in A\)是B的任何一个下界，若均有\(a\le a'\),则称a'为B的最大下界或下确界

其他次序关系

拟序关系

Definition

设R是非空集合A上的关系，如果R是反自反的和传递的，则称R为A上的拟序关系(quasi-order relation),记为"<",读作“小于”，并将\(<a,b>\in <\)记为a<b.序偶\(<A,<>\)称为拟序集(quasi-order set).

eg:

  • 实数集上的小于关系是拟序关系；
  • 幂集上的真包含是拟序关系.
  • 设R是集合A上的拟序关系，则R是反对称的.

逆序关系VS偏序关系

  • R是集合A上的偏序关系，则\(R-I_A\)是A上的拟序关系；
  • S是集合A上的拟序关系，则\(S\cup I_A\)是A上的偏序关系.

全序关系

Definition

设\(<A,\le>\)是一个偏序关系，若对任意\(x,y\in A\),x与y都是可比的，则称关系\(\le\)为全序关系(total order relation)或线序关系。称\(<a,\le>\)为全序集(total order set),或线序集，或链。

全序关系的哈斯图将集合中的元素排成一条直线，像一条链子，这充分体现了全序集可以成为线序集或链的原因

良序关系

Definition

设\(<A,\le>\)是全序集，若A在任何一个非空子集都有最小元素，则称\(\le\)为良序关系(well order relation),此时\(<A,\le>\)成为良序集(well order set).

良序关系一定是全序关系，而有限全序集一定是良序集