半順序とは？

半順序（はんじゅんじょ、英: partial order）とは、集合の要素間に定義される二項関係のうち、次の3つの条件をすべて満たすものをいいます。

• 反射律：任意の要素 a について、a ≦ a が成り立つ
• 推移律：a ≦ b かつ b ≦ c ならば a ≦ c が成り立つ
• 反対称律：a ≦ b かつ b ≦ a ならば a = b が成り立つ

この3条件を満たす関係を「半順序関係」といい、その関係が定義された集合を「半順序集合（poset）」と呼びます。「半」とついているのは、必ずしもすべての要素の組が比較可能ではないためです。すべての要素が互いに比較できる場合は「全順序（線形順序）」と呼ばれ、半順序の特殊ケースにあたります。

典型的な例として、自然数の集合における「整除関係（aがbを割り切る）」があります。たとえば 2 は 4 を割り切りますが、2 と 3 はどちらもどちらを割り切るわけではないため、この二要素は比較不能です。また、集合族に包含関係（⊆）を入れた場合も半順序の例です。

半順序はコンピュータ科学でも重要で、タスクの依存関係（あるタスクが別のタスクより先に実行されなければならない）などを半順序としてモデル化できます。依存関係のないタスクは比較不能な要素に対応します。さらに、半順序集合のハッセ図は要素間の関係を視覚的に表現するために広く使われます。

半順序集合上では「最大元・最小元」「極大元・極小元」「上界・下界」「上限（最小上界）・下限（最大下界）」などの概念が定義され、束（lattice）理論へと発展します。