二元关系

             

预备知识 集合

1. 关系

   在 “集合” 中我们只关心了集合的基数,即集合中元素的数目.在这种语境下,任何两个元素数量相同的集合都可以看作是同一个集合.但是仅仅讨论集合的基数未免太过单调,缺少了很多有意思的理论,于是我们希望在集合的元素之间建立一些结构,来进行更细致的划分和研究.

   关系(relation)是集合上最基础的一种结构.给定一个关系,我们就可以讨论一些元素之间是否满足这个关系.比如说,如果取一家三口构成一个集合,$\sim$ 代表的是 “年龄大于”,那么我们可以说 “爸爸对于孩子具有这个关系”,但是反过来 “孩子对于爸爸不具有这个关系”.从这个例子可以看出,关系的表达方式很灵活,而且可以是有方向性的.讨论关系时,我们唯一关心的是给定元素之间是否具有这样的关系.

   关系可以用在两个元素之间,也可以用在三个元素之间,甚至可以用在不特定的元素之间.

2. 二元关系

   在绝大多数数学和物理领域,我们只关心集合上的二元关系(binary relation).如果 $\sim$ 是在集合 $A$ 上定义的一个二元关系,那么任意给定两个元素,我们都可以讨论它们之间是否具有这种关系,但如果给定三个元素,讨论就没有意义了.比如,如果 $\sim$ 的定义是 “年龄大于”,那么把三个人的年龄都拿过来比较就没有意义;不过,如果 $\sim$ 的定义是 “比后面两个人的年龄都大”,那么 $\sim$ 就可以用在三个人身上.

   对于集合 $A$ 上的二元关系 $\sim$,如果 $x, y\in A$ 满足这个关系,我们可以把这句话表述为 $x\sim y$.如果不满足,则可以表述为 $x\not\sim y$.用这样简洁的表示方法,我们可以把以上 “年龄大于” 的关系表述如下:

\begin{equation} \text{爸爸}\sim\text{孩子} \qquad \text{妈妈}\sim\text{孩子} \qquad \text{孩子}\not\sim\text{爸爸} \qquad \text{孩子}\not\sim\text{妈妈} \qquad \end{equation}
爸爸和妈妈之间,在没有进一步信息的情况下,无法判断是否满足这个关系,但这个关系是存在的.也就是说,元素间的关系一共有两种状态:满足和不满足.

   在数学上,二元关系被定义为笛卡尔积 $A \times A$ 的子集,如果集合 $A$ 中的两个元素 $a,b$ 满足关系 $R$.则 $(a,b) \in R$,否则 $(a,b) \notin R$.

3. 等价关系

   最基础的一类关系,是等价关系(equivalence).在集合 $A$ 上定义的关系 $\sim$ 是一个等价关系,要求满足条件:

  1. 自反性:$\forall x\in A, x\sim x$;
  2. 对称性:$\forall x, y\in A, x\sim y \Rightarrow y\sim x$;
  3. 传递性:$\forall x, y, z\in A, x\sim y, y\sim z\Rightarrow x\sim z$.

   如果把 “具有关系 $\sim$” 看成是两个元素间相互连接(没有方向性,因为对称性),传递性保证了当多个元素相连时,这些元素也两两互联;自反性甚至保证了每个元素必然和自身相连.由此一来,我们可以根据等价关系把集合 $A$ 划分成等价类(equivalence class),每个等价类都是 $A$ 的一个子集,所包含的元素彼此相连.

   等价类的划分是数学中非常重要的思维方法,它可以将每一个等价类中的元素都看成是无差别的,大大简化一个集合的复杂程度.有了等价关系后,我们可以用相应的等价类来组成一个新的集合,这样的集合被称作商集(quotient set).和原来集合中的元素不一样,商集中的元素是原集合中的子集.

   作为例子,我们取全体非负整数的集合 $\mathbb{Z}$,并在上面定义关系 $\sim$ 为 “两数的差是 3 的倍数”,那么容易验证,$1\sim4, 7\sim304, 0\not\sim 77, 77\not\sim 1$.利用这个等价关系,我们可以把非负整数集合划分成三个等价类,分别是 $\{0, 3, 6, 9, 12\cdots \}$,$\{1, 4, 7, 10, 13\cdots\}$ 和 $\{2, 5, 8, 11, 14\cdots\}$.这样,我们可以得到一个含有三个元素的商集,用数学专业术语来说,叫做集合 $A$ 模去关系 $\sim$ 所得的商集.这里的模(mod)的意思来自于 “除法”,在群论中会看到为什么用除法来命名商集.

4. 序关系

   另一类比较基础的关系是序关系(ordering relation).在集合 $A$ 上定义的关系 $\prec$(一般也可以写成 $\leq$ 或 $\leqslant$)是一个序关系,要求满足条件:

  1. 自反性:$\forall x\in A,x\prec x$;
  2. 反对称性:$\forall x,y\in A,\ x\prec y,\ y\prec x \Rightarrow x = y $;
  3. 传递性:$\forall x,y,z\in A,\ x\prec y,\ y\prec z \Rightarrow x\prec z $.

定义 1 偏序集、半序集

   如果一个集合 $A$ 上定义了一个序关系 $\prec$,那么称这个集合是带有偏序 $\prec$ 的偏序集(partially ordered set)半序集

   带有偏序 $\prec$ 的偏序集 $A$ 通常记作 $(A,\prec)$.在不致混淆的情况下,可以简称为偏序集 $A$.偏序集上的序关系称为偏序关系(partially ordered relation)

   序关系实际上是给集合中的元素排序,因此 $a \prec b$ 又被称为$a$ 在 $b$ 前,反之 $b \prec a$ 称为$a$ 在 $b$ 后.这种排序方式并不唯一,而且任意两个元素间不一定可以排出前后.

例 1 

   各种数集(包括 $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}$)按通常的序关系构成偏序集.

   其中复数集 $\mathbb{C}$ 上的序关系比较特殊,复数 $a_1+b_1 \mathrm{i} \leq a_2+b_2 \mathrm{i} $ 当且仅当 $a_1\leq a_2$ 且 $b_1 \leq b_2$.复数的序关系通常不使用.

   这个例子说明序关系实际上是数与数大小关系的抽象.

例 2 字典序

   已知 $(A,\prec),(B,\leq)$ 是两个偏序集,那么笛卡尔积 $A\times B$ 按某个序关系 $\leqslant$ 构成偏序集.这个序关系 $\leqslant$ 满足:

  1. $\forall(a_1,b_1),(a_2,b_2) \in A\times B, a_1\prec a_2 \Rightarrow (a_1,b_1)\leqslant(a_2,b_2)$;
  2. $\forall(a_1,b_1),(a_2,b_2) \in A\times B, a_1=a_2, b_1\leq b_2 \Rightarrow (a_1,b_1) \leqslant (a_2, b_2)$.

   由于字典通常按照这样的顺序编排1,因此这种序关系称为字典序.

例 3 幂集

   一个集合 $A$ 的幂集2$2^X$ 与子集关系一起构成偏序集.

例 4 

   小时百科的知识树(目录树)可以看做一个偏序集,词条 A 在词条 B 前意味着词条 A 是词条 B 的预备知识,或预备知识的预备知识,或……

定义 2 全序集

   偏序集 $(A,\prec)$ 称为全序集(totally ordered set)有序集(ordered set),当且仅当对任意 $a,b \in A$,$a \prec b$ 或 $b \prec a$.

   全序集上的序关系称为全序关系(totally ordered relation)

例 5 

   数集 $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ 按通常的序关系构成全序集.

例 6 

   将例 2 中的偏序集 $A,B$ 换成全序集,则按同样的序关系,$A\times B$ 也构成全序集.

   一个显然但重要的事实是,任何偏序集的非空子集按原来的序仍是偏序集,任何全序集的非空子集按原来的序仍是全序集.

定义 3 极小元、极大元

   已知偏序集 $(A,\prec)$:

  1. 如果存在某个 $a \in A$,使得对任意 $x \in A, x\prec a$ 都有 $x = a$,那么称 $a$ 为偏序集 $A$ 的极小元(minimal element)
  2. 如果存在某个 $b \in A$,使得对任意 $x \in A, b\prec x$ 都有 $x = b$,那么称 $b$ 为偏序集 $A$ 的极大元(maximal element)

定义 4 最小元、最大元

   已知偏序集 $(A,\prec)$ 的某个非空子集 $B$:

  1. 如果存在某个 $a \in B$,使得 $\forall x \in B, a \prec x$.那么 $a$ 被称为 $B$ 的最小元(least element)
  2. 如果存在某个 $b \in B$,使得 $\forall x \in B, x \prec b$.那么 $b$ 被称为 $B$ 的最大元(greatest element)

   极大元、极小元与最大元、最小元极易混淆.偏序集的极大元、极小元不一定唯一,但最大元、最小元只要存在必然唯一.在全序集中两者统一.

例 7 

   集合 $A=\{0,1,2\}$,在上面定义偏序关系 $\prec$ 为 $0\prec 0$, $1\prec 1$, $1\prec 2$, $2\prec 2$.那么子集 $\{0,1\}$ 的极大元为 0 和 1,不存在最大元.

习题 1 

   证明:如果偏序集的某个子集存在最大元,那么它的极大元必然存在且唯一,并且两者相等.

习题 2 

   证明:对于全序集的任意非空子集,如果存在极大元,则最大元必然存在,且两者相等.

定义 5 良序集

   全序集 $(A,\prec)$ 称为良序集(well-ordered set),当且仅当它的任意非空子集都有极小元.

   良序集上的序关系称为良序关系(well-ordered relation)

   任何良序集的非空子集仍是良序集.


1. ^ 比如,字典中单词 in 在 a 后,在 it 前.
2. ^ 即集合 $A$ 所有子集的集合.

致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择会员制,大量广告,内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

         

© 小时科技 保留一切权利