前順序集合

$X:$ 集合.

$X$ 上の二項関係 $\le$ について、以下が成り立つとき、 $(X,\le)$ を 前順序集合 という。

$\forall x \in X,\; x \le x$ （反射律）
$\forall x,y,z \in X,\; x \le y,\; y \le z \Longrightarrow x \le z$ （推移律）

Hint

半順序集合や順序集合との違いは、反対称律を要求しないこと。

順序集合では、 $x \le y$ かつ $y \le x$ なら $x = y$ でなければならない
前順序集合では、 $x \le y$ かつ $y \le x$ でも、 $x$ と $y$ が異なることを許す

つまり、前順序集合では「区別できるが、順序関係の上では同じように見える」要素がありうる。

Example

順序集合は前順序集合である
同値関係は、対称な前順序集合と見なせる
有向グラフにおける到達可能性は前順序集合になる