# 半順序 ## 定義 半順序(partial order)は、二項関係の一部の性質(反射性・非反射性・対称性・非対称性・反対称性・推移性)を組み合わせて定義される関係のクラスである。**強半順序(strict partial order)**は推移的かつ非反射的な関係であり、これは推移的かつ非対称的な関係と同値である。**弱半順序(weak partial order)**は推移的・反射的・反対称的な関係であり、強半順序 `S` を使って `a R b :⟺ a S b または a = b` と表せる。この2つは「自分自身との比較を認めるかどうか」だけが異なり、片方から他方を機械的に構成できる。強半順序は[[有向グラフ]]における DAG(有向非巡回グラフ)の正の歩道関係(positive walk relation)と一致し、弱半順序は DAG の歩道関係(walk relation、長さ0の歩道=自分自身を含む)と一致する。この対応により、任意の強半順序・弱半順序はある DAG の描像として視覚化できる。また、任意の弱半順序 `≼`(集合 `A` 上)は、各要素 `a` をその逆像 `{b ∈ A | b ≼ a}` という集合に対応させる写像により、集合の包含関係 `⊆` と同型(isomorphic、関係を保存する全単射が存在する)になる——半順序は常に「集合と包含関係」として表現し直せる。半順序のうち、任意の異なる2要素が比較可能(comparable、一方が他方から到達可能)であるものを**全順序(linear order)**と呼ぶ。2つの半順序の直積(積順序、product order)は各成分ごとの関係の連言として定義され、半順序であることは積で保存されるが、全順序であることは保存されない。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) ## 横断的知見 (この concept は本 ingest が初出のため、複数ソースの突き合わせによる横断的知見はまだない。半順序・全順序を扱う他ソースが ingest された際にここへ追記する。) ## 未解決の問い - 「全順序であることは、半順序が全域関係(total relation)であることより強い条件である」(§9.8脚注)という注意書きがある。全域な半順序でありながら全順序でない具体例(本章では明示されていない)を、後続の集合論・順序理論のソースで確認したい。 - Dilworthの補題(半順序の鎖・反鎖の存在定理)は、より一般的な Dilworth の定理(本章では扱わない)の特殊ケースとされている。一般形との関係を後続ソースで補いたい。 - 半順序の「集合による表現」(定理9.7.3)は、束論(lattice theory)のBirkhoffの表現定理とどう関係するか。本章では触れられていない。 ## 関連 - 概念: [[有向グラフ]] / [[トポロジカルソート]] / [[同値関係]] / [[二項関係]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 9.