半順序とは？

はんじゅんじょ

反射的・反対称的・推移的な二項関係のことで、すべての元が比較可能とは限らない順序構造です。

半順序（partial order）とは、集合 A 上の二項関係 ≤ が反射性（a ≤ a）・反対称性（a ≤ b かつ b ≤ a ならば a = b）・推移性（a ≤ b かつ b ≤ c ならば a ≤ c）の三条件を満たすものをいう。全ての元が比較可能（a ≤ b または b ≤ a）であれば全順序（線形順序）となる。整除関係・集合の包含関係・プログラムの依存関係などが半順序の例である。