順序の定義

定義 1 (順序の定義). 上の二項関係であって、推移的かつ反射的であるものを前順序といい、で表す。反対称的な前順序を半順序という。をそれぞれ前順序集合や半順序集合などという。

に定められた順序が文脈上明らかで誤解が生じない場合は,単に順序集合と言うこともある.

命題 2. 前順序集合に対して、によって同値関係を定め、この同値関係による商集合における順序をによって定めれば、は半順序集合となる。

証明. まずが同値関係であることを示す。 反射性は前順序の反射性より なので 。 対称性はの定義より従う。 推移性は、かつのとき および から かつ、よって 。

次にが well-defined であることを示す。 かつとし、を仮定する。 より 、より 。 したがって推移性より であり を得る。 ゆえに代表元の取り方によらず は定まる。

最後にが半順序であることを示す。 任意のについて より より反射的である。 かつならば かつなので 、よって となり推移的である。 かつならば かつ、すなわち 。よって であるのでより反対称的である。

以上より、は半順序集合である。 ◻

鎖・反鎖

定義 3 (比較可能). 前順序集合の2元に対し、

が真であるときとは比較可能であるといい、比較可能でないとき、すなわち

が真であるときとは比較不能であるという。

定義 4 (鎖・反鎖). 前順序集合の部分集合であって、任意の2元が比較可能であるとき、をの鎖という。また任意の2元が比較不能であるとき、をの反鎖という。

定義 5 (順序集合の長さ・幅). 前順序集合に対し、その鎖の濃度の上限をの長さという。また反鎖の濃度の上限をの幅という。

順序集合の大きさが有限の場合は鎖や反鎖の濃度には最大値が存在して、それらは上の定義と一致する。

全順序

定義 6 (全順序律). 任意の2元が比較可能であるという条件

を全順序律という。全順序律を満たす前順序を全前順序という。全順序律を満たす半順序を全順序あるいは線形順序という。

逆順序・狭義順序

定義 7 (逆順序). 順序の逆関係を逆順序や双対順序といい、で表す。を双対順序集合などという。

定義 8 (狭義順序). それぞれの順序から恒等関係を除いた関係 を狭義順序という。の性質に応じて狭義前順序や狭義半順序などという。狭義でない順序の逆順序の補関係とも言い換えられる。

これはすなわち狭義でない順序の定義における反射性を非反射性に取り替えたものである。

©2025 Atlasez