自反關係

自反關係（reflexive relation）是在邏輯學和數學中一種特殊的二元關係，這樣的二元關係被稱作自反的，或具有自反性。一個集合$X$上的二元關係$R$，若滿足$(\forall x \in X)(xRx)$，則為自反關係。

## 定義

以下是與「自反」有關的定義。給定一個集合$X$上的二元關係$R$，稱其具有：

自反性（reflexivity）。

若任取$X$的一個元素$x$，滿足有序對$(x, x) \in R$，即$(\forall x \in X)(xRx)$。

非自反性（non-reflexivity）。

若存在$X$的一個元素$x$，滿足有序對$(x, x) \notin R$，即$\neg[(\forall x \in X)(xRx)] \iff (\exists x \in X)[\neg(xRx)]$。

反自反性（anti-reflexivity / irreflexivity）。

若任取$X$的一個元素$x$，滿足有序對$(x, x) \notin R$，即$(\forall x \in X)[\neg(xRx)]$。

左準自反性（left quasi-reflexivity）。

若任取$X$的兩個元素$x_L$和$x_R$，並滿足有序對$(x_L, x_R) \in R$，則$(x_L, x_L) \in R$。

換句話說，$(\forall x_L \in X)(\forall x_R \in X)(x_L R x_R \implies x_L R x_L)$。

右準自反性（right quasi-reflexivity）。

若任取$X$的兩個元素$x_L$和$x_R$，並滿足有序對$(x_L, x_R) \in R$，則$(x_R, x_R) \in R$。

換句話說，$(\forall x_L \in X)(\forall x_R \in X)(x_L R x_R \implies x_R R x_R)$。

準自反性（quasi-reflexivity）。

若$R$同時滿足「左準自反性」及「右準自反性」。

換句話說，$(\forall x_1 \in X)(\forall x_2 \in X)(x_1 R x_2 \implies x_1 R x_1 \land x_2 R x_2)$。

## 示例

### 基本 / 常見示例

以下為一些「自反」關係的例子：

- 定義在特定集合$X_r$上的相等（$=$）。
- 定義在特定集族$X_r$上的包含於（$\subseteq$）及包含（$\supseteq$）。
- 定義在實數集$\mathbb{R}$上的不大於（$\le$）及不小於（$\ge$）。
- 定義在正整數集$\mathbb{Z}^+$上的整除（$|$）。

接著是一些不具反自反性的「非自反」關係，例如：

- 定義在集合$\{-1, 0, 1\}$上的關係$R$，滿足$x R y \iff |x| = y$。
- 定義在集合$\{1, 2, 3\}$上的關係$R = \{(1, 1), (1, 2), (2, 2)\}$。
- 定義在整數集$\mathbb{Z}$上的關係$R$，滿足$x R y \iff (x \le y) \land (x \ge 0)$。

最後是一些「反自反」關係的例子：

- 定義在特定集合$X_i$上的不相等（$\ne$）。
- 定義在特定集合$X_i$上的真包含於（$\subset$）及真包含（$\supset$）。
- 定義在實數集$\mathbb{R}$上的小於（$<$）及大於（$>$）。

### 特殊 / 非典型示例

以下為一個「自反」關係的例子：

- 定義在自然數集$\omega$上的關係$R$，滿足$x R y \iff \operatorname{Card}(x) = y$。

接著是一個不具反自反性的「非自反」關係，例如：

- 定義在實數集$\mathbb{R}$上的關係$R_f$，滿足$x R_f y \iff x = f(y)$，其中函數$f:\mathbb{R} \to \mathbb{R}$，滿足圖形$y = f(x)$與直線$y = x$的交點個數為正整數。

再來是幾個「反自反」關係的例子：

- 定義在實數集$\mathbb{R}$上的關係$R$，滿足$x R y \iff (\exists \varepsilon \in \mathbb{R}^+)[x \notin (y - \varepsilon, y + \varepsilon)]$，其中$(y - \varepsilon,y + \varepsilon)$為一開區間。
- 定義在特定集合$X_i$上的關係$R$，滿足$x R y \iff x = y^+$，其中$y^+$表示$y$的後繼，並承認正則公理。

最後，值得一提的是，對於定義在空集合$\varnothing$上的二元關係$R$（此時只能有$R = \varnothing$），有：

- $(\forall x \in \varnothing)(xRx) \iff (\forall x)(x \in \varnothing \implies x R x)$為真，因為前件$x \in \varnothing$恆為假，故命題虛空真。
- $\neg[(\forall x)(x \in \varnothing \implies x R x)]$為假，因為$(\forall x)(x \in \varnothing \implies x R x)$為真，故其否定恆為假。
- $(\forall x)[x \in \varnothing \implies \neg(x R x)]$為真，因為前件$x \in \varnothing$恆為假，故命題虛空真。

因此，該關係$R$同時具備自反性及反自反性，卻不具非自反性。

## 相關概念

以下整理了一些分散的概念：

- $(\forall x \in X)(x = x)$在一些系統中被稱作相等公理。
- 預序關係：具有傳遞性的自反關係。

等價關係：具有對稱性的預序關係。

偏序關係：具有反對稱性的預序關係。

- 一個準自反關係的例子是關於實數序列集合的「具有相同極限」的關係：並不是每個序列都有一個極限，因此這個關係不是自反的，但是如果一個序列與某個序列具有相同的極限，具有與其本身相同的限制。
- 自反閉包：給定集合$X$上的二元關係$R$，其自反閉包是包含$R$的最小自反關係。

形式上，它等於$R$與$X$上的恆等關係$I_X$的聯集：

$R^= = R \cup I_X$。

例如，實數集上「小於」（$<$）的自反閉包即為「小於或等於」（$\le$）。

- 自反減少：給定集合$X$上的二元關係$R$，其自反減少是包含於$R$的最大反自反關係。

形式上，它等於$R$與$X$上的恆等關係$I_X$的差集：

$R^{\neq} = R \setminus I_X$。

例如，實數集上「小於或等於」（$\le$）的自反減少即為「小於」（$<$）。

## 各類關係個數

在一個$n$-元素集合上，自反關係的數目是$2^{n^2 - n}$個。其他的關係個數如下表：

$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$｜$2^{n^2}$｜$2^{n^2 - n}$｜$\sum_{k = 0}^n k!S(n, k)$｜$n!$｜$\sum_{k = 0}^n S(n, k)$

OEIS｜A002416｜A006905｜A053763｜A000798｜A001035｜A000670｜A000142｜A000110

其中上表的$S(n, k)$代表第二類史特靈數。