自反关系

集合中每个元素都和自身相关的二元关系

自反关系是在逻辑学数学中一种特殊的二元关系,这样的二元关系被称为自反的,也被称为具有自反性。自反關係的一個例子是關於實數集合的“等於”關係,因為每個實數都等於它自己。对称性传递性以及自反性是定義等價關係的三個屬性。

定义

对于集合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