二元关系

                     

贡献者: hfb25; JierPeter; Giacomo; addis; xiaokuc

预备知识 笛卡尔积

1. 关系

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

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

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

2. 二元关系

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

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

(1)爸爸孩子 ,妈妈孩子 ,孩子爸爸 ,孩子妈妈 .
爸爸和妈妈之间,在没有进一步信息的情况下,无法判断是否满足这个关系,但这个关系是存在的。也就是说,元素间的关系一共有两种状态:满足和不满足。

   在数学上,二元关系的严格定义是:

定义 1 二元关系

   设 A×A 的子集 R,如果集合 A 中的两个元素 a,b 满足 (a,b)R ,那么就称 a,b 满足关系 R。也称 a,bR 相关的,并且记作 aRb.

   下面是一个简单的例子:

例 1 

   设集合 A={1,2} 上的关系 Ra<b, (a,b)A2.

   集合 A 的笛卡尔积为:

(2)A2={(1,1),(1,2),(2,1),(2,2)} .
那么就有:
(3)R={(1,2)}A2 .

   我们注意到在 R 上,装备着小于关系和大于关系,它们间有一种对偶的联系,因此我们引入对偶关系来描述这种联系。

3. 对偶关系

定义 2 对偶关系

   设 R 是非空集合 A 上的一个二元关系. 我们定义 A 上的另一个关系 Rd 如下:

   (x,y)Rd(y,x)R .

   我们称 RdR 的对偶关系

   对偶关系描述的是二元关系的对称性,同时容易验证,存在着一些二元关系,它们的对偶关系是自身。

4. 等价关系

   最基础的一类关系,是等价关系(equivalence),它也是一类满足对偶关系是自己的关系(即对称性)

定义 3 等价关系

   在集合 A 上定义的关系 是一个等价关系,要求满足条件:

  1. 自反性xA,xx
  2. 对称性x,yA,xyyx
  3. 传递性x,y,zA,xy,yzxz

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

   注:等价关系定义中的自反性不可去除,虽然很多时候对称性和传递性可以推出自反性;如果每一个等价类都不止一个元素,那么自反性是可以推导出来的,如果不满足,比如说集合中只有一个元素,就不可以。

定义 4 集合的划分

   在集合 A 上,一个集族 SP(A),(P(A)A 的幂集合)被称为 A划分,如果它满足

  • U1,U2SU1U2=
  • USU=A

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

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

   每个等价关系都可以得到一个划分,反过来也是成立的,

定理 1 

   集合 A 上的每一个划分定义了一个等价关系。更进一步我们有,集合上的等价关系和划分一一对应。

  

未完成:证明它

  

未完成:以下为回收内容

5. 序关系

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

  1. 自反性xA,xx
  2. 反对称性x,yA, xy, yxx=y
  3. 传递性x,y,zA, xy, yzxz

   序关系是比较基础的一类关系,它在数学各个学科中广泛运用。

   序关系也是序论的中心课题。接下来,我们将主要探讨序关系。

                     

© 小时科技 保留一切权利