aiwiki.page
中文
数学 / 离散数学与逻辑 / reflexive-relation

自反关系

自反关系是集合上的一种二元关系,其中每个元素都与自身具有该关系。

18 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
集合(数学)二元关系等价关系偏序笛卡尔积子集空集实数自反关系

自反关系是集合上的一种二元关系,其中每个元素都与自身具有该关系。形式上,关系 R⊆A×AR\subseteq A\times A 在 AA 上是自反的,当且仅当

∀a∈A,(a,a)∈R.\forall a\in A,\quad (a,a)\in R.

自反性是定义等价关系和偏序的性质之一。它只对两个分量相同的有序对提出要求,不限制不同元素之间是否具有该关系。

定义与底集

用 aRbaRb 表示 (a,b)∈R(a,b)\in R,则定义条件可写为

∀a∈A,aRa.\forall a\in A,\quad aRa.

关系 RR 是笛卡尔积 A×AA\times A 的一个子集。

AA 上的恒等关系,也称对角关系,定义为

ΔA={(a,a):a∈A}.\Delta_A=\{(a,a):a\in A\}.

因此,自反性也可以等价地表示为

ΔA⊆R.\Delta_A\subseteq R.

恒等关系是 AA 上最小的自反关系,而全关系 A×AA\times A 是最大的自反关系。

自反性取决于所指定的底集。例如,

R={(1,1),(2,2)}R=\{(1,1),(2,2)\}

在 {1,2}\{1,2\} 上是自反的,但在 {1,2,3}\{1,2,3\} 上不是自反的,因为 (3,3)∉R(3,3)\notin R。

在空集上,空关系是自反的,因为不存在使这一要求不成立的元素。这体现了全称量化命题在其论域为空时为真的情形。

例子与反例

常见的自反关系包括:

  • **相等关系:**对于任意集合中的每个元素,都有 a=aa=a。
  • **数的非严格序关系:**对于每个实数 aa,都有 a≤aa\leq a。
  • **集合的包含关系:**对于每个集合 BB,都有 B⊆BB\subseteq B,因此包含关系在任意指定的集合族上都是自反的。
  • **整除关系:**每个正整数都能整除自身。
  • 模正整数的同余关系:a≡a(modm)a\equiv a\pmod m,因为 mm 整除 a−a=0a-a=0。这一关系是模算术的核心。

相比之下,严格序 << 在非空数集上不是自反的,因为 a<aa<a 永远不成立。不等关系 ≠\neq 同样不会使任何元素与自身具有该关系。

自反性并不要求每个有序对都属于该关系。在 A={1,2}A=\{1,2\} 上,关系

R={(1,1),(2,2),(1,2)}R=\{(1,1),(2,2),(1,2)\}

是自反的,尽管 (2,1)∉R(2,1)\notin R。

与其他关系性质的区别

如果没有任何元素与自身具有某关系,那么该关系称为**非自反关系**:

∀a∈A,(a,a)∉R.\forall a\in A,\quad (a,a)\notin R.

不具有自反性与非自反并不相同。只要缺少一个对角有序对,自反性就不成立:

∃a∈A,(a,a)∉R.\exists a\in A,\quad (a,a)\notin R.

例如,{1,2}\{1,2\} 上的关系 {(1,1)}\{(1,1)\} 既不是自反的,也不是非自反的。在非空集合上,一个关系不可能既自反又非自反;但在空集上,空关系同时具有这两种性质。

自反性也不同于以下性质:

  • **对称关系的对称性:**由 aRbaRb 可推出 bRabRa。
  • **反对称关系的反对称性:**由 aRbaRb 和 bRabRa 可共同推出 a=ba=b。
  • **传递关系的传递性:**由 aRbaRb 和 bRcbRc 可共同推出 aRcaRc。

仅凭自反性无法推出这三种性质中的任何一种。将这些性质组合起来,可以定义一些重要的关系类别:

类别 所需性质
等价关系 自反性、对称性、传递性
[[preorder 预序]]
偏序 自反性、反对称性、传递性

例如,等价关系中的自反性保证每个元素都属于它自身的等价类。

图与矩阵表示

集合上的关系可以用有向图表示,其中从 aa 到 bb 存在一条边,当且仅当 aRbaRb。在这种表示中,自反性意味着每个顶点都有一个自环。这种表示要求采用允许自环的图定义。

对于有限集合 A={a1,…,an}A=\{a_1,\ldots,a_n\},定义布尔邻接矩阵 MM 如下:

Mij={1,aiRaj,0,otherwise.M_{ij}= \begin{cases} 1,&a_iRa_j,\\ 0,&\text{otherwise}. \end{cases}

关系是自反的,当且仅当每个对角元素都为 11:

Mii=1(1≤i≤n).M_{ii}=1\qquad (1\leq i\leq n).

非对角元素不受限制。因此,在一个给定的、含 nn 个元素的集合上,自反关系的数量为

2n2−n,2^{n^2-n},

因为 nn 个对角元素已经固定,而其余 n2−nn^2-n 个元素都可以独立选取。

自反闭包与自反性的保持

AA 上的关系 RR 的自反闭包为

Rref=R∪ΔA.R^{\mathrm{ref}}=R\cup\Delta_A.

它是 AA 上包含 RR 的最小自反关系。它恰好补入所有缺失的元素与自身组成的有序对,而不改变任何由不同元素组成的有序对。用图来描述,就是补上缺失的自环;用矩阵来描述,就是将每个对角元素设为 11。

以下几种运算保持自反性:

  • 同一集合上自反关系的交仍是自反关系。
  • 同一集合上任意非空自反关系族的并仍是自反关系。
  • 如果 RR 是自反的,则逆关系 R−1={(b,a):(a,b)∈R}R^{-1}=\{(b,a):(a,b)\in R\} 也是自反的。
  • 如果 B⊆AB\subseteq A,且 RR 在 AA 上是自反的,则限制关系 R∩(B×B)R\cap(B\times B) 在 BB 上也是自反的。
  • 同一集合上两个自反关系的复合仍是自反关系,因为每个元素都可以充当自身的中间元素。

在图的可达性问题中,自反传递闭包允许长度为零的路径,因此每个顶点都可以从自身到达。若传递闭包仅用正长度路径来定义,则它未必是自反的:例如,孤立顶点就没有返回自身的正长度路径。