自反關係
自反關係是在邏輯學和數學中一種特殊的二元關係,這樣的二元關係被稱為自反的,也被稱為具有自反性。自反關係的一個例子是關於實數集合的「等於」關係,因為每個實數都等於它自己。對稱性、傳遞性以及自反性是定義等價關係的三個屬性。
定義
對於集合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」-元素集合上,自反關係的數目是2n2−n.[1]
n | 全部 | 遞移 | 自反 | 預序 | 偏序 | 全預序 | 全序 | 等價 |
---|---|---|---|---|---|---|---|---|
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 | 2n2−n | Σn k=0 k! S(n, k) |
n! | Σn k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |