自反关系是集合上的一种二元关系,其中每个元素都与自身具有该关系。形式上,关系 R⊆A×A 在 A 上是自反的,当且仅当
∀a∈A,(a,a)∈R.
自反性是定义等价关系和偏序的性质之一。它只对两个分量相同的有序对提出要求,不限制不同元素之间是否具有该关系。
定义与底集
用 aRb 表示 (a,b)∈R,则定义条件可写为
∀a∈A,aRa.
关系 R 是笛卡尔积 A×A 的一个子集。
A 上的恒等关系,也称对角关系,定义为
ΔA={(a,a):a∈A}.
因此,自反性也可以等价地表示为
ΔA⊆R.
恒等关系是 A 上最小的自反关系,而全关系 A×A 是最大的自反关系。
自反性取决于所指定的底集。例如,
R={(1,1),(2,2)}
在 {1,2} 上是自反的,但在 {1,2,3} 上不是自反的,因为 (3,3)∈/R。
在空集上,空关系是自反的,因为不存在使这一要求不成立的元素。这体现了全称量化命题在其论域为空时为真的情形。
例子与反例
常见的自反关系包括:
- **相等关系:**对于任意集合中的每个元素,都有 a=a。
- **数的非严格序关系:**对于每个实数 a,都有 a≤a。
- **集合的包含关系:**对于每个集合 B,都有 B⊆B,因此包含关系在任意指定的集合族上都是自反的。
- **整除关系:**每个正整数都能整除自身。
- 模正整数的同余关系:a≡a(modm),因为 m 整除 a−a=0。这一关系是模算术的核心。
相比之下,严格序 < 在非空数集上不是自反的,因为 a<a 永远不成立。不等关系 = 同样不会使任何元素与自身具有该关系。
自反性并不要求每个有序对都属于该关系。在 A={1,2} 上,关系
R={(1,1),(2,2),(1,2)}
是自反的,尽管 (2,1)∈/R。
与其他关系性质的区别
如果没有任何元素与自身具有某关系,那么该关系称为**非自反关系**:
∀a∈A,(a,a)∈/R.
不具有自反性与非自反并不相同。只要缺少一个对角有序对,自反性就不成立:
∃a∈A,(a,a)∈/R.
例如,{1,2} 上的关系 {(1,1)} 既不是自反的,也不是非自反的。在非空集合上,一个关系不可能既自反又非自反;但在空集上,空关系同时具有这两种性质。
自反性也不同于以下性质:
- **对称关系的对称性:**由 aRb 可推出 bRa。
- **反对称关系的反对称性:**由 aRb 和 bRa 可共同推出 a=b。
- **传递关系的传递性:**由 aRb 和 bRc 可共同推出 aRc。
仅凭自反性无法推出这三种性质中的任何一种。将这些性质组合起来,可以定义一些重要的关系类别:
| 类别 |
所需性质 |
| 等价关系 |
自反性、对称性、传递性 |
| [[preorder |
预序]] |
| 偏序 |
自反性、反对称性、传递性 |
例如,等价关系中的自反性保证每个元素都属于它自身的等价类。
图与矩阵表示
集合上的关系可以用有向图表示,其中从 a 到 b 存在一条边,当且仅当 aRb。在这种表示中,自反性意味着每个顶点都有一个自环。这种表示要求采用允许自环的图定义。
对于有限集合 A={a1,…,an},定义布尔邻接矩阵 M 如下:
Mij={1,0,aiRaj,otherwise.
关系是自反的,当且仅当每个对角元素都为 1:
Mii=1(1≤i≤n).
非对角元素不受限制。因此,在一个给定的、含 n 个元素的集合上,自反关系的数量为
因为 n 个对角元素已经固定,而其余 n2−n 个元素都可以独立选取。
自反闭包与自反性的保持
A 上的关系 R 的自反闭包为
Rref=R∪ΔA.
它是 A 上包含 R 的最小自反关系。它恰好补入所有缺失的元素与自身组成的有序对,而不改变任何由不同元素组成的有序对。用图来描述,就是补上缺失的自环;用矩阵来描述,就是将每个对角元素设为 1。
以下几种运算保持自反性:
- 同一集合上自反关系的交仍是自反关系。
- 同一集合上任意非空自反关系族的并仍是自反关系。
- 如果 R 是自反的,则逆关系 R−1={(b,a):(a,b)∈R} 也是自反的。
- 如果 B⊆A,且 R 在 A 上是自反的,则限制关系 R∩(B×B) 在 B 上也是自反的。
- 同一集合上两个自反关系的复合仍是自反关系,因为每个元素都可以充当自身的中间元素。
在图的可达性问题中,自反传递闭包允许长度为零的路径,因此每个顶点都可以从自身到达。若传递闭包仅用正长度路径来定义,则它未必是自反的:例如,孤立顶点就没有返回自身的正长度路径。