半順序集合(Posets)

半順序集合(Partially ordered set, posets, ポセット)

集合があったときに反射律、推移律、反対称律を満たすものは半順序集合、またはPoset(ポセット)と呼ばれる

反対称律がない(満たさない)と前順序集合

定義

集合$ P 上の半順序(partial order)とは、$ P 上の二項関係$ \preceq であって，以下を満たすもの

(反射律) $ x \preceq x

(反対称律) $ x \preceq y かつ$ y \preceq x なら$ x = y が成り立つ

(推移律) $ x \preceq y かつ$ y \preceq z ならば$ x \preceq z が成り立つ

半順序$ \preceq を備えた集合$ P のことを半順序集合(Partially ordered set, poset, ポセット)という。

集合$ P と半順序$ \preceq の組みの表記は$ (P, \preceq) 。

$ \preceq : \preceq、二項関係

参考