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