自反关系

自反关系是在逻辑学数学中一种特殊的二元关系,这样的二元关系被称为自反的,也被称为具有自反性。自反关系的一个例子是关于实数集合的“等于”关系,因为每个实数都等于它自己。对称性传递性以及自反性是定义等价关系的三个属性。

定义

对于集合X上的二元关系R,若满足:取X里任一元素a,且满足对于所有a皆存在(a,a)在R集合中,则称二元关系R是自反的,或称R具有自反性,或称R为自反关系

相关概念

 ,a = a,在一些系统中称为相等公理

一个反自反(irreflexive, anti-reflexive)的关系,是在一个集合中没有元素与自身相关的二元关系。例如实数上的“大于”关系(x> y)。请注意,没有自反的各种关系,并不全都是反自反的;有些关系中,部分元素与自己相关,而部分不是。例如,“x和y的乘积是偶数”的二元关系在偶数集上是自反的,在奇数集上是反自反的,在自然数集上既不是自反,也不是反自反。

关于集合S上的一个关系,如果与某个元素相关的每个元素也与它自己有关,形式上就称为准自反:∀x,y∈S:x〜y⇒(x〜x∧y〜y)。一个例子是关于实数序列集合的“具有相同极限”的关系:并不是每个序列都有一个极限,因此这个关系不是自反的,但是如果一个序列与某个序列具有相同的极限,具有与其本身相同的限制。

S上二元关系的自反闭包是S上最小的自反关系,它是〜的超集。等价地,它是S与S上的同一性关系的联合,形式如下:(≃)=(¯)∪(=)。例如,x <y的自反闭包是x≤y。

在集合S上的二元关系的自反性约化或反自反核是最小的关系≆,使得≆共享与〜相同的自反闭包。它可以被看作是自反封闭的反面。 它相当于S上关于〜的形式关系的补充,形式上是:(≆)=(〜)\(=)。也就是说,除了x〜x是真的,它相当于〜。例如,x≤y的自反减少是x <y。

特殊的自反关系

满足传递性的自反关系称为预序关系。满足反对称性的预序关系称为偏序关系。满足对称性的预序关系称为等价关系

举例

自反关系举例:

  • 等于
  • 是……的子集(集合的包含)
  • 小于等于、大于等于
  • 整除

n元素集合之上的关系

一个“n”-元素集合上,自反关系的数目是2n2n.[1]

n元集上各种二元关系的数目
n 全部 递移 自反 预序 偏序 全预序英语Strict weak ordering 全序 等价
0 1 1 1 1 1 1 1 1
1 2 2 1 1 1 1 1 1
2 16 13 4 4 3 3 2 2
3 512 171 64 29 19 13 6 5
4 65536 3994 4096 355 219 75 24 15
n 2n2 2n2n Σn
k=0
 
k! S英语Stirling numbers of the second kind(n, k)
n! Σn
k=0
 
S英语Stirling numbers of the second kind(n, k)
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

参考文献

  1. ^ On-Line Encyclopedia of Integer Sequences A053763