順序的構造

ウィキペディア

順序集合

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/15 07:39 UTC 版)

「順序」はこの項目へ転送されています。その他の用法については「wikt:順序」をご覧ください。

この記事には複数の問題があります。改善やノートページでの議論にご協力ください。 出典は脚注などを用いて記述と関連付けてください。（2019年6月） 独自研究が含まれているおそれがあります。（2019年6月）

順序集合（じゅんじょしゅうごう、英: ordered set）は集合の要素の間に順序が定義された集合。順序とは二項関係であって後述する反射律・推移律などを満たすものであり、数の大小関係などを一般化したものである。

全ての2要素が比較可能（順序が定義されている）ものを特に全順序集合（totally ordered set; toset）という。例えば実数における大小関係は全順序集合である。

また、全順序ではない順序集合の例としては、正の整数全体の集合に整除関係で順序を定めたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序と見なしたものがある。

後述するように、順序が満たすべき公理の種類により、前順序集合、半順序集合（partially ordered set; poset）、全順序集合がある。多く場合、半順序集合を指して「順序集合」と呼ぶことが多いが、分野によっては前順序集合や全順序集合を指す場合がある。

定義

まず、二項関係について以下の用語を定める。

ここで P は集合であり、「≤」を P 上で定義された二項関係とする。

• 反射律：P の任意の元 a に対し、a ≤ a が成り立つ。
• 推移律：P の任意の元 a, b, c に対し、a ≤ b かつ b ≤ c ならば a ≤ c が成り立つ。
• 反対称律：P の任意の元 a, b に対し、a ≤ b かつ b ≤ a ならば a = b が成り立つ。
• 全順序律：P の任意の元 a, b に対し、a ≤ b または b ≤ a が成り立つ。

また、「≤」が全順序律を満たさない場合（すなわちa ≤ bでもb ≤ aないとき、 a と b は比較不能 (incomparable) であると言う。

前順序・半順序・全順序

P を集合とし、≤ を P 上で定義された二項関係とする。

• ≤ が反射律と推移律を満たすとき、≤ を P 上の前順序（英語版） (preorder) または擬順序 (quasiorder) という。
• ≤ が前順序でありさらに反対称律を満たすとき、≤ を P 上の半順序 (partial order) という。
• ≤ が半順序でありさらに全順序律を満たすとき、≤ を P 上の全順序 (total order) という。

≤ が前順序であるとき (P, ≤) を前順序集合という。同様に ≤ が半順序なら (P, ≤) は半順序集合、全順序なら (P, ≤) は全順序集合であるという。また集合 P は (P, ≤) の台集合 (underlying set) あるいは台 (support) と呼ばれる。紛らわしくなければ ≤ を省略し、P を（いずれかの意味で）順序集合という。

順序集合 (P, ≤) に対し、≤ を台 P 上の順序関係ともいう。

上では順序を記号 ≤ で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 ≤ と区別するため、順序の記号として ${\displaystyle \prec }$

三元集合 {x, y, z} の部分集合の全体を包含関係を順序とする順序集合と見たときのハッセ図

P を有限集合とし、「<」を P 上の狭義の半順序とするとき、以下のようにして P を自然に単純有向グラフと見なせる：

頂点：P の元

a ∈ P から b ∈ P への辺がある ⇔ a < b であり、しかも a < c < b を満たす c ∈ P が存在しない

（すなわち b は a を被覆している）

この有向グラフを図示したものをハッセ図という。

ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。例えばこの図で {x} と {x, y, z} は比較可能だが、{x} と {y} は比較不能である。また単集合の族 {{x}, {y}, {z}} は反鎖である。さらに {x} は {x, z} によって被覆されるが、{x, y, z} には被覆されない。

なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に (V, E) を閉路を持たない有限な単純有向グラフとすると、V 上に以下の順序を入れることで V を半順序集合と見なせる：

a < b ⇔ a から b への道がある

したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。

上界、最大、極大、上限、上方集合

P を半順序集合とし、A をその部分集合とし、x を P の元とする。このとき上界、上限、最大、極大の概念、およびこれらの双対概念である下界（かかい）、下限、最小、極小は以下のように定義される^[1]：

• x が A の上界 (upper bound) であるとは、A の任意の元 y に対して y ≤ x となること。
• x が A の上限 (supremum) あるいは最小上界 (least upper bound) であるとは、x が A の上界全体の集合の最小元となること。これは存在すれば一意的に決まり、sup A あるいは lub A と表される。
• x が A の最大元 (maximum element) であるとは、x は A の元であり、かつ x は A の上界であること。これは存在すれば一意的に決まり、max A で表される。
• x が A の極大元 (maximal element) であるとは、x は A の元であり、かつ y > x を満たす y ∈ A が存在しないこと。

• x が A の下界 (lower bound) であるとは、A の任意の元 y に対して y ≥ x となること。
• x が A の下限 (infimum) あるいは最大下界 (greatest lower bound) であるとは、x が A の下界全体の集合の最大元となること。これは存在すれば一意的に決まり、inf A あるいは glb A と表される。
• x が A の最小元 (minimum element) であるとは、x は A の元であり、かつ x は A の下界であること。これは存在すれば一意的に決まり、min A で表される。
• x が A の極小元 (minimal element) であるとは、x は A の元であり、かつ y < x を満たす y ∈ A が存在しないこと。

上界および上限の定義において、 x が必ずしも A の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間 ${\displaystyle [a,b)}$

三元集合の冪集合のハッセ図から最大元と最小元を取り除いたもの。この図の一番上の行にある各元がこの半順序の極大元であり、一番下の行の各元は極小元である。最大元と最小元はない。集合 {x, y} は元の族 {{x}, {y}} に対する上界を与える。

整除性によって順序付けられた非負整数のハッセ図

正整数全体の成す集合を整除関係で順序付けるとき、1 は任意の正整数を割り切るという意味において 1 は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としての 0 を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元 g はそれとは異なる。例えば 2g を割り切るから g は極大ではありえない。この半順序集合から最小元である 1 を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して 60 は部分集合 {2, 3, 5, 10} の上界（上限ではない）を与えるが、1 は除かれているので下界は持たない。他方、2 の冪全体の成す部分集合に対して 2 はその下界（これは下限でもある）を与えるが、上界は存在しない。

写像と順序

順序に関する写像の概念に以下のものがある：

定義

S, T を順序集合とし、f: S → T を写像とする。このとき

• f: S → T が順序を保つ（英語版）(order-preserving)（同調 (isotone) とも）とは、

任意の x, y ∈ S に対して x ≤ y ⇒ f(x) ≤ f (y)

• f: S → T が順序を逆にする（order-reversing（英語版））とは、

任意の x, y ∈ S に対して x ≤ y ⇒ f (x) ≥ f (y)

• 上の2つを合わせて単調 (monotone) 写像という。
• f が順序を反映する (order-reflecting) とは、

任意の x, y ∈ S に対して f (x) ≤ f (y) ⇒ x ≤ y

• f が順序埋め込み（英語版）であるとは、

任意の x, y ∈ S に対して x ≤ y ⇔ f (x) ≤ f (y)

• f が順序同型写像（英語版）であるとは、f が順序埋め込みな全単射であることをいう。

f: S → T が順序埋め込みであるとき、S は f によって T に（順序集合として）埋め込まれるという。 また順序同型 f: S → T が存在するとき、S と T は順序同型あるいは単に同型であるという。

性質

上で述べた概念は以下の性質を満たす：

• 順序を反映する写像は単射である。実際 f(x) = f(y) ⇒f(x) ≤ f(y) かつ f(x) ≥ f(y) ⇒ x ≤ y かつ x ≥ y ⇒ x = y である。
• f が順序埋め込みである必要十分条件は f が順序を保存し、しかも順序を反映することである。また全単射 f: S → T とその逆関数 f⁻¹: T → S が順序同型なら f, f⁻¹ は順序同型である。
• 順序を保つ写像と順序を保つ写像の合成は順序を保つ。順序を反映する写像と順序を反映する写像の合成も順序を反映する。

具体例

順序を保つが順序を反映しない写像 (f(u) ≤ f(v) だが u ≤ v でない)

120 の約数全体の成す半順序集合（整除関係で順序を入れる）と {2, 3, 4, 5, 8} の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型

自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 f: N → P(N) を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、x が y を割るならば x の各素因数は y の素因数にもなる）が単射ではない（例えば 12 も 6 もこの写像で {2, 3} に写る）し、順序を反映もしない（例えば 12 は 6 を割らない）。少し設定を変えて、各自然数にその素冪因子の集合を対応させる写像 g: N → P(N) を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば単集合 {4} に移る数は無い）が終域を g の値域 g(N) に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な分配束（英語版）と呼ばれる半順序集合のクラスに対して一般化することができる（バーコフの表現定理（英語版）の項を参照）。

区間

P を順序集合とし、a, b を P の元とするとき、閉区間 [a, b] と開区間 (a, b) を以下のように定義する：

${\displaystyle [a,b]:=\{x\in P\mid a\leq x\leq b\}}$

この節には、過剰に詳細な記述が含まれているおそれがあります。百科事典に相応しくない内容の増大は歓迎されません。内容の整理をノートで検討しています。（2016年1月）

全順序集合の位相

順序位相

全順序集合 A に対し、無限半開区間

${\displaystyle (-\infty ,b)=\{x\in A\mid x<b\}}$

N × N 上の直積狭義順序の反射閉包

N × N 上の積順序

N × N 上の辞書式順序

圏としての順序集合

任意の半順序集合（および前順序集合）は、任意の射集合が高々一つの元からなる圏と見なすことができる。具体的には、射の集合を x ≤ y ならば hom(x, y) = {(x, y)}（それ以外の場合は空集合）とし、(y, z)∘(x, y) = (x, z) と定義する。2つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏は同型射について閉じて（英語版）いる。

半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。

その他

• （半順序関係の総数）n 個の元からなる集合上の半順序の総数（狭義半順序の総数も同じ）は 1, 1, 3, 19, 219, 4231, … （オンライン整数列大辞典の数列 A001035）。同型を除いた総数は 1, 1, 2, 5, 16, 63, 318, … （オンライン整数列大辞典の数列 A000112）。
• （線型順序拡大）半順序集合 P の全順序集合への埋め込みを線型順序拡大（英語版） (linear extension) という。任意の半順序は全順序に拡張することができる（順序拡大原理（英語版）^[3]）。計算機科学において（有向非循環グラフの到達可能性（英語版）順序として表現される）半順序の線型拡張を求めるアルゴリズムは位相ソート (topological sorting) と呼ばれる。

関連項目

• 反マトロイド（英語版）: 半順序集合よりも一般の順序付けの族を許すような、集合上の順序付けの一般化
• 因果集合
• 比較可能グラフ（英語版）
• 有向集合
• 次数付き順序集合（英語版）
• 半束
• 束 (束論)
• 順序群
• 準順序（英語版） (semiorder)
• 直並列半順序（英語版）
• 狭義弱順序（英語版）: "a < b または b < a の何れかが成り立つ" という関係が推移的となるような狭義半順序 "<"
• 完備半順序 (cpo)
• ツォルンの補題
• コンパクト要素

脚注

[脚注の使い方]

注釈

1. ^ 原理的には半順序集合であっても同様の概念を定義できるが、本稿の英語版をはじめ、筆者^[誰?]が調べた範囲^{[要文献特定詳細情報]}では全順序集合に対してのみ order topology を定義しているため、ここでは全順序のみに話を限定した。
2. ^ 実数体でなくとも上極限位相と下極限位相を考えることができるが、これも実数体以外に対してこれらの位相を定義した文献が見つけられなかったので、ここでは実数体のみを対象にした。

出典

1. ^ 花木 章秀 (2021年1月22日). “集合論 信州大学理学部数学科 講義ノート 2020 年度後期 (2021/01/22)”. 2022年3月17日閲覧。
2. ^ Ward, L. E. Jr (1954). “Partially Ordered Topological Spaces”. Proceedings of the American Mathematical Society 5 (1): 144-161. doi:10.1090/S0002-9939-1954-0063016-5. 
3. ^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8 

参考文献

この節には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。脚注を導入して、記事の信頼性向上にご協力ください。（2016年1月）

• 松坂和夫『集合・位相入門』岩波書店、1968年6月10日。ISBN 4-00-005424-4。 
• 斎藤正彦『数学の基礎　集合・数・位相』東京大学出版会〈基礎数学14〉、2002年8月1日。ISBN 978-4-13-062909-6。 
• Deshpande, Jayant V. (1968). “On Continuity of a Partial Order”. Proceedings of the American Mathematical Society 19 (2): 383-386. doi:10.1090/S0002-9939-1968-0236071-7. 
• Schröder, Bernd S. W. (2003). Ordered Sets: An Introduction. Birkhäuser, Boston 
• Stanley, Richard P.. Enumerative Combinatorics 1. Cambridge Studies in Advanced Mathematics. 49. Cambridge University Press. ISBN 0-521-66351-2 

外部リンク

ウィキメディア・コモンズには、Hasse diagramに関連するメディアがあります。

• オンライン整数列大辞典の数列 A001035: Number of posets with n labeled elements in the OEIS
• オンライン整数列大辞典の数列 A000112: Number of posets with n unlabeled elements in the OEIS