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

反对称关系

反对称关系是一种二元关系,其中两个元素只有在相等时才可能双向关联。

15 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
二元关系偏序笛卡尔积有序对实数子集整数等价关系反对称关系

反对称关系是一种二元关系,其中任意两个不同的元素都不能双向关联。形式上,集合 AA 上的关系 RR 是反对称的,是指对所有 a,b∈Aa,b\in A,若 aRbaRb 和 bRabRa 同时成立,则 a=ba=b。反对称性与自反性、传递性一起构成了偏序的定义条件。尽管名称中有“反”字,反对称并不只是指“不对称”。

定义与等价表述

AA 上的关系是一个子集 R⊆A×AR\subseteq A\times A,其中 A×AA\times A 是 AA 与自身的笛卡尔积。记号 aRbaRb 表示有序对 (a,b)(a,b) 属于 RR。

反对称性的形式化定义为

∀a,b∈A,(aRb∧bRa)⟹a=b.\forall a,b\in A,\qquad (aRb\land bRa)\Longrightarrow a=b.

等价地,对于任意两个不同的元素,有

a≠b⟹¬(aRb∧bRa).a\ne b\Longrightarrow \neg(aRb\land bRa).

因此,对于每一对不同的元素 aa 和 bb,关系中可以包含 (a,b)(a,b),可以包含 (b,a)(b,a),也可以两者都不包含,但不能同时包含两者。

反对称性并不限制某个对角有序对 (a,a)(a,a) 是否属于 RR。反对称关系可以包含所有对角有序对,也可以只包含其中一部分,或者一个也不包含。

另一种表述使用逆关系

R−1={(b,a):(a,b)∈R}R^{-1}=\{(b,a):(a,b)\in R\}

以及对角关系

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

于是有

R is antisymmetric⟺R∩R−1⊆ΔA.R\text{ is antisymmetric} \quad\Longleftrightarrow\quad R\cap R^{-1}\subseteq\Delta_A.

若 RR 还具有自反性,则上述包含关系变为相等关系:

R∩R−1=ΔA.R\cap R^{-1}=\Delta_A.

例子与反例

数值的序关系

实数上的关系 ≤\leq 是反对称的,因为

a≤b and b≤a⟹a=b.a\leq b\ \text{and}\ b\leq a \quad\Longrightarrow\quad a=b.

严格关系 << 也是反对称的。在这种情况下,a<ba<b 和 b<ab<a 永远不可能同时成立,因此定义中的蕴含式总是成立。反对称性并不要求实际存在双向关联的元素对。

集合的包含关系

子集关系是反对称的:

X⊆Y and Y⊆X⟹X=Y.X\subseteq Y\ \text{and}\ Y\subseteq X \quad\Longrightarrow\quad X=Y.

这就是为什么证明两个集合互相包含,就能证明它们相等。

整除关系

正整数上的整除关系是反对称的。若 a∣ba\mid b 且 b∣ab\mid a,则 a=ba=b。

不过,所讨论的范围很重要。全体整数上的整除关系不是反对称的:2∣−22\mid -2 且 −2∣2-2\mid 2,但 2≠−22\ne -2。两个整数互相整除,只能确定它们相差一个单位因子;在整数中,这意味着它们可能相差一个符号。

相等关系与空关系

相等关系同时具有反对称性和对称性。更一般地,任何包含于 ΔA\Delta_A 的关系都同时具有这两种性质。

空关系也是反对称的,因为它不包含任何可能违反定义条件的有序对。

不满足反对称性的情形

在 A={1,2,3}A=\{1,2,3\} 上,关系

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

是反对称的。加入 (2,1)(2,1) 后,反对称性就不再成立,因为此时 1R21R2 和 2R12R1 同时成立,但 1≠21\ne2。

要证明一个关系不是反对称的,只需找到一对这样互相关联但彼此不同的元素。

与对称性、非对称性的区别

以下三种名称相近的性质有着不同的含义:

性质 定义条件
[[symmetric-relation 对称关系]]的对称性
反对称性 (aRb∧bRa)⟹a=b(aRb\land bRa)\Longrightarrow a=b
[[asymmetric-relation 非对称关系]]的非对称性

对称性要求每个属于关系的有序对,其逆序对也属于该关系。反对称性只禁止不同元素之间同时存在互为逆序的有序对。非对称性则完全禁止互为逆序的有序对同时存在,也不允许对角有序对。

因此:

  • 每个非对称关系都是反对称关系。
  • 反对称关系未必是非对称关系;≤\leq 就是一个例子。
  • 一个关系是非对称的,当且仅当它既是反对称的,又是反自反的;反自反是指 aRaaRa 永远不成立。
  • 一个关系同时具有对称性和反对称性,当且仅当它是对角关系的子集。

因此,反对称性并不是对称性在逻辑上的否定。一个关系可以同时具有这两种性质,也可以只具有其中一种,或者两种都不具有。

在序理论中的作用

偏序是满足自反性、反对称性和传递性的关系。反对称性保证:两个元素若各自都不大于对方,就不可能是不同的元素。

反对称性并不要求任意两个元素都可比较。例如,在集合包含关系下,{1}⊆{2}\{1\}\subseteq\{2\} 和 {2}⊆{1}\{2\}\subseteq\{1\} 都不成立。任意两个元素都可比较的偏序称为全序。

预序具有自反性和传递性,但不一定具有反对称性。对于预序 ⪯\preceq,定义

a∼b⟺a⪯b and b⪯a.a\sim b \quad\Longleftrightarrow\quad a\preceq b\ \text{and}\ b\preceq a.

这是一个等价关系。将元素替换为它们所属的等价类,就得到一个偏序:

[a]≤[b]⟺a⪯b.[a]\leq[b] \quad\Longleftrightarrow\quad a\preceq b.

传递性保证这个定义不依赖于代表元的选取。此时反对称性成立,因为两个类若在两个方向上都满足该关系,就必然是同一个类。这一构造恰好将那些因彼此不同而使原预序不满足反对称性的元素归为一类。

图与矩阵表示

一个关系可以用有向图表示:只要 aRbaRb,就有一条边 a→ba\to b。反对称性意味着任意两个不同顶点之间都不能同时存在两个方向的边。自环则是允许的。

反对称性不意味着无环。例如,三个不同元素上的关系

R={(a,b),(b,c),(c,a)}R=\{(a,b),(b,c),(c,a)\}

虽然包含一个有向环,却是反对称的。有向无环图不包含任何长度的有向环,而反对称性只排除不同顶点之间长度为二的环。如果关系还具有传递性,那么经过不同顶点的环就会迫使反向边存在,从而违反反对称性。

对于有限集 A={a1,…,an}A=\{a_1,\ldots,a_n\},设 MM 为该关系的邻接矩阵:当 aiRaja_iRa_j 时,Mij=1M_{ij}=1,否则为 00。反对称性等价于

MijMji=0for every i≠j.M_{ij}M_{ji}=0 \qquad\text{for every }i\ne j.

对角元素不受限制。不能将这一条件与斜对称矩阵的条件 MT=−MM^{\mathsf T}=-M 混淆:这两个概念描述的是不同的性质。

保持性与计数

反对称关系的每个子关系都是反对称的,因为删除有序对不会产生一对原本不存在的、方向相反的有序对。因此,将反对称关系限制在较小的底集上,仍能保持反对称性;取其逆关系也同样如此。

同一集合上的反对称关系的交仍是反对称的,但并集未必如此:对于不同的 aa 和 bb,一个关系可能包含 (a,b)(a,b),另一个关系则可能包含 (b,a)(b,a)。

取传递闭包也未必能保持反对称性。上面的三元环关系是反对称的,但它的传递闭包在每一对顶点之间都包含两个方向的边。

在一个固定的、含有 nn 个带标号元素的集合上,反对称关系的数量为

2n 3(n2).2^n\,3^{\binom n2}.

nn 个对角有序对中的每一个,都可以独立地选择包含或不包含。对于 (n2)\binom n2 个由不同元素组成的无序对中的每一个,恰好有三种选择:包含一个方向、包含另一个方向,或者两个方向都不包含。若要求自反性,所有对角有序对就都必须包含,因此自反且反对称的关系共有 3(n2)3^{\binom n2} 个;它们未必是偏序,因为尚未要求传递性。