2.3 关系的运算

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

关系是有序对的集合,所以关系的并、交、差等集合运算仍然适用。本节进一步定义从关系本身提取元素、反向关联、连续关联、限制输入范围和计算幂的运算。贯穿全部公式的复合约定是: 表示先经过 ,再经过 ,称为右复合。另一些文献采用相反约定;下面所有运算均按这一已声明的顺序进行。

定义2.3.1:关系的定义域、值域和域分别为

它们是实际出现在有序对中的第一元素、第二元素及两者的合集。若说 是从 到 的关系,只能断言 、,不必相等。本节的“域”是一个元素集合,和代数结构中可以进行加减乘除的“域”不是同一个概念。

【例2.3.1】设 ,求定义域、值域和域。

解:收集第一位置得到 ;收集第二位置得到 ;二者取并,。重复出现的元素只列一次。

定义2.3.2:交换 中每个有序对的两个位置,所得关系称为逆关系,记为

逆关系对任何关系都存在,不要求 是函数或双射。以后谈反函数时还需要额外的函数条件,不能把“逆关系存在”直接理解为“反函数存在”。

定义2.3.3:关系 的右复合为

中间元素 必须在第一步的终点和第二步的起点相同。中间元素不只一个时,结果仍只收录一次 ;没有可衔接的元素时,不能形成该对。这种定义也允许复合结果为空。

【例2.3.2】,,求 。

解:。先 后 时,只有路径 ,故 。先 后 时,有 ,故 。两个结果不同,说明关系复合通常不交换。

若采用左复合,符号相同的 可能被定义为先 后 。两种约定都可以建立一致的理论,但不能在同一推导中混用。这里以路径 固定右复合含义。

定义2.3.4: 在集合 上的限制为 ; 在 下的像为 。限制的结果仍是关系,像的结果是第二位置元素的集合。限制只筛选第一位置,不同时要求第二位置也属于 ;后者是另一个更强的筛选条件。

【例2.3.3】,求若干限制与像。

解:,,。相应有 ,,。最后一个像是单元素集,不是数2。

逆运算的优先级高于其他关系运算,关系运算高于集合运算。为免混淆,复合与并交混合的公式保留括号, 和 也明确写出作用范围。

定理2.3.1:,,。交换两次有序对的位置恢复原对;逆关系第一位置出现的元素,正是原关系第二位置出现的元素,因而三个等式直接来自定义。

定理2.3.2:关系复合满足结合律 ,并有 。第一个等式两侧都等价于存在 ,使 ;分组不改变同一条三步路径。第二个等式把 反向成为 ,所以逆运算不只对每一步取逆,还必须反转步骤顺序。

定理2.3.3:若 是 上的关系,则 。恒等步骤不改变元素;对 ,可分别在最后接上 或在最前接上 。这里必须使用包含全部相关元素的底集上的恒等关系。

定理2.3.4:复合对并分配,但对交一般只能保证包含:

并的等式只要求存在一条可走通的路径,所以可按路径落在 还是 分类。交的左侧需要同一个中间元素同时使 成立,而右侧的两条路径允许用不同中间元素,所以反向包含可能失败。例如 ,则 ,左侧为空,但两个复合都包含 。这些公式以归纳法可推广到任意有限个关系:并保持等号,交保持同方向包含。

定理2.3.5:限制对并、交均分配,像对并分配,像对交一般只保包含:

限制保留整个有序对,所以两个输入条件可以在同一个第一元素上比较。像只记录输出,同一个输出可能分别来自不同的输入。例如 ,则 ,却有 ,因此末式不能无条件改为等号。

定义2.3.5:对 上的关系 和自然数 ,规定 、。所以 ,不同关系的零次幂在同一底集上都等于同一个恒等关系。 表示逆关系,不是按此定义得到的负整数次幂,不能把两个记号混同。

矩阵法计算关系幂时,使用布尔矩阵乘法:,即某一条两步路径存在就取1。加法是逻辑或,特别 ;普通整数矩阵乘法会累计路径条数,结果不能直接作为0-1关系矩阵。在关系图中, 当且仅当存在从 到 、恰走 步的有向游走,允许重复顶点和边。它不是“至多走 步”的可达关系,也不要求是无重复顶点的简单路。

【例2.3.4】设 ,,求各次幂的矩阵和关系图。

解:按 排列,

逐次使用布尔乘法,有

由此所有正偶数且至少为2的幂都等于 ,所有奇数且至少为3的幂都等于 。 和 要单独保留,不能把上述周期公式错误地从0或1起套用。

abcd
:四个顶点均有自环。
abcd
:四个有序对对应四条箭头。
abcd
: 各有自环,另有 。
abcd
:。

定理2.3.6:若 ,则存在 使 。因为 上只有 个不同关系,考察 到 共 项,鸽巢原理保证有两项相同。它保证最终重复,并不保证每个关系都从零次幂开始周期重复,也不保证幂按包含关系单调增加。

定理2.3.7:对自然数 ,,。第一式固定 对 归纳: 时使用恒等关系;从 到 时使用结合律及幂的递推定义。第二式同样归纳,并在归纳步骤调用第一式。两个归纳都必须保留零次幂的初始情形。

定理2.3.8:若 且 ,令 ,则对任意自然数 ,有 ,,全部幂均出现在有限集合 中。第一式两边同时右复合 即得;第二式对 归纳。对任意指数 ,作除法 ,其中 ,就有 且 ,因此可以把大指数降到已知范围。

【例2.3.5】设 ,,求第一次重复的幂。

解: 构成长度2的循环, 构成长度3的循环。恢复整个关系作用需要同时恢复两组元素,因此指数差必须同时被2、3整除,最小正差为 。于是 ,最小起点为 ,相应最小终点为 。这里只因关系恰为两个置换循环,才从零次幂起呈周期;不能把这一特殊情形当作任意有限关系的结论。