2.4 关系的性质
本章目录 · 1 节
本章导读
关系的五种主要性质是自反性、反自反性、对称性、反对称性和传递性。它们都要相对于指定底集 判断;改变底集可能改变结论。例如 在 上自反,在 上却不自反,因为缺少 。
定义2.4.1:若对每个 都有 ,称 在 上自反;若对每个 都有 ,称其反自反。前者要求全部对角项都有,后者要求全部对角项都没有。一个关系可能只含部分对角项,于是两者都不满足;“反自反”不是“不自反”的同义词。空底集上两个全称条件都成立。
全域关系 和恒等关系 均自反,实数子集上的小于等于关系、非零整数集上的整除关系,以及集族上的包含关系也自反。严格小于和真包含关系反自反。 和 同为自反关系,不表示两个关系相同。
【例2.4.1】在 上,,,,判断自反性和反自反性。
解: 只有部分自环,既不自反也不反自反; 含全部对角项,自反而不反自反; 没有对角项,反自反而不自反。判断自反时必须检查指定底集中的全部元素,不能只检查已经出现在关系中的元素。
定义2.4.2:若 总能推出 ,称 对称。若 且 时必须 ,称 反对称。反对称只禁止不同元素之间的双向关系,不禁止自环;对称则要求每条非自环边都有反向伙伴。
对称与反对称可以同时成立,例如恒等关系或空关系;也可以都不成立。全域关系一般对称但不反对称,不过当底集至多一个元素时,也满足反对称,不能忽略这个退化情形。
【例2.4.2】在 上,判断以下关系的对称性和反对称性:,,,。
解: 同时对称和反对称; 对称但不反对称; 反对称但不对称; 两者都不是。 中1与2双向关联,破坏反对称;1与3只有单向关联,破坏对称。这两个反例分别针对不同性质。
定义2.4.3:若 且 总能推出 ,称 传递。只要找到一条可衔接的两步关系却没有对应一步关系,就能否定传递性。若根本不存在这样的两步关系,传递条件反而成立,因为没有违反蕴含的情形。
全域关系、恒等关系、空关系均传递;通常的小于等于、整除、包含、小于及真包含关系也都传递。证明这些例子时可分别使用数的次序传递性、整除商的相乘和集合包含的传递性。
【例2.4.3】在 上,,,,判断传递性。
解: 传递,因为能衔接的两步都仍停在同一个元素; 不传递,缺少 ; 传递,因为第一步到达3后,没有从3出发的第二步。不能为让它“看起来传递”而擅自增添自环。
定理2.4.1:五种性质分别等价于以下集合条件:
自反和反自反的条件直接检查全部对角项。对称条件把“每个有序对都有反向对”写成与逆关系相等。反对称条件要求同时属于 与逆关系的有序对只能位于对角线上。传递条件中, 恰好收集所有能用两步连接的起终点,所以要求这些起终点已有一步关系。每个等价式的两个方向都由上述逐元素解释得到,并非只有充分性。
【例2.4.4】证明:(1)两个自反且对称的关系的并仍自反且对称;(2)两个传递关系的交仍传递。
解:(1)两个关系均包含 ,它们的并仍包含 ,所以自反。又 ,所以对称。(2)若 且 ,两条边分别同时属于两个关系;分别利用各自的传递性,得到 和 ,于是 。这个证明没有要求两个关系存在相同的图形画法。
五种性质在矩阵和关系图中都有对应特征。自反时矩阵主对角线全为1,图中每个顶点都有自环;反自反时主对角线全为0,图中没有自环。对称时 ,每条非自环有向边都配有反向边。反对称时 的 不能同时为1,图中不同顶点之间不出现双向边。传递时布尔平方矩阵 中为1的每个位置,在 中也必须为1;图中任意两步有向游走的起终点之间已有相应的有向边,起终点相同时这条边就是自环。
【例2.4.5】判断下列三幅关系图的五种性质。
解:(a)对称;既不自反也不反自反,因为只有一个顶点有自环;不反对称,因为存在不同顶点间的双向关系;不传递,例如 却没有3的自环。(b)反自反、反对称且传递;不自反、不对称。没有两步可接的边,所以传递性成立。(c)自反、反对称;不反自反、不对称、不传递。反对称允许自环;不传递的证据是 却没有 。
考察运算是否保持某种性质时,前提是参加运算的关系都具有该性质,“不能保证保持”不表示每次都必定破坏。逆运算保持全部五种性质;两个关系的交也保持全部五种性质。并运算保持自反、反自反和对称,一般不保持反对称和传递。差运算保持反自反、对称和反对称,一般不保持自反和传递。复合保持自反,一般不保证其余四种性质。
保持性的理由可以直接说明:交集中的两步路径同时位于两个传递关系中,因此终点边也在交集中;反对称关系的子关系仍反对称;两个对称关系作差时,某条边及其反向边会同时保留或同时删除。复合保持自反是因为每个 都能接续 。不能保持的情况需要另找反例,例如两个反自反关系分别含 和 ,它们复合会产生自环;两个传递关系分别只有 、,并集缺少 ,所以不传递。后续练习可用这些原则系统检查其他运算。
