順序集合

数学において順序集合（じゅんじょしゅうごう、英: ordered set）とは、大小関係や血縁関係のような順序が定義された集合のことである。順序は一般に二項関係として定義されるが、その順序集合の任意の2つの元に対して必ず定まるとは限らない。 比較不能の場合を許容する順序集合として典型的なのは後述する半順序集合（partially ordered set; poset）である。特に、半順序集合で全ての2元が比較可能であるものを全順序集合 (totally ordered set; toset) という。 全順序の最も簡単な例は、実数における大小関係である。 一方、全順序ではない半順序集合の例としては、正の整数全体の集合に整除関係で順序を入れたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序と見なしたものがある。例えば2元集合 S = {a, b} において {a} と {b} はいずれも他方を包含していないので S の冪集合は全順序ではない。