順序集合

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
検索に移動

数学において順序集合(じゅんじょしゅうごう、: ordered set)とは「順序」の概念が定義された集合のことで、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。ただし、ここでいう順序とは、集合の任意の2つの元に定まる(「比較可能」)とは限らず、両者が「比較不能」であることもありうる。

比較不能の場合を許容する順序集合を半順序集合(はんじゅんじょしゅうごう、: partially ordered set, poset)という。特に、半順序集合で全ての2元が比較可能であるものを全順序集合 (totally ordered set) という。

全順序の最も簡単な例は、実数における大小関係である。

一方、全順序ではない半順序集合の例としては、正の整数全体の集合に整除関係で順序を入れたものや、(2つ以上元を含む)集合の冪集合において、包含関係を順序と見なしたものがある。例えば2元集合 S = {a, b} において {a}{b} はいずれも他方を包含していないので S の冪集合は全順序ではない。

日常の例では、「AさんはBさんの子孫である」ことを「A < B」と定義することで、人間全体の集合は半順序集合になる。AさんとBさんはどちらも他方の子孫でないこともありうる(兄弟同士、叔父と甥、赤の他人等)ので、この順序集合は全順序ではない。

定義[編集]

前順序、半順序、全順序を順に定義するために、まず以下の性質を考える。ここで P は集合であり、「」を P 上で定義された二項関係とする。

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

」が全順序律を満たさない場合、「ab」でも「ba」でもないときがある。このとき ab比較不能 (incomparable) であるという。

前順序・半順序・全順序[編集]

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

  • が反射律と推移律を満たすとき、P 上の前順序という。
  • が前順序でありさらに反対称律を満たすとき、P 上の半順序という。
  • が半順序でありさらに全順序律を満たすとき、P 上の全順序という。

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

順序集合 (P, ≤) に対し、 を台 P 上の順序関係ともいう。なお多くの数学の分野では半順序集合を主に扱うので、単に順序あるいは順序集合といった場合はそれぞれ半順序、半順序集合を意味する場合が多いが、分野によっては、主な対象が半順序集合でなく前順序集合や全順序集合である場合があり、そのような分野では前順序集合や全順序集合の意味で「順序集合」という言葉が用いられることがあるので注意が必要である。

上では順序を記号 で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 と区別するため、順序の記号として を使うこともある。

全順序を線型順序ともいい、全順序集合をと呼ぶこともある。また半順序集合の部分集合 AA の任意の異なる2元が比較不能であるものを反鎖英語版という。半順序集合のことを部分順序集合と呼ぶこともある[要出典]が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。

半順序集合の元 a が他の元 b によって被覆される英語版 (a <: b) とは、ab よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう。つまり とは次の3つがすべて成り立つことである:

順序集合の例[編集]

  • 実数全体の集合 R およびその部分集合(例えば、自然数全体の集合 N, 整数全体の集合 Z, 有理数全体の集合 Q)は、通常の大小関係により全順序集合となる。しかし、複素数全体の集合 C には複素数の乗法と"両立"する全順序は存在しない(順序体でない)。単に全順序を入れるだけであれば、直積集合 R × R辞書式順序を定めることができる。
  • 自然数全体の成す集合は整除関係を順序として半順序集合である。
  • 集合の冪集合に対して、包含関係による順序を入れると半順序集合となる。これはもとの集合の元の個数が2個以上であれば全順序でない。例えば {1, 2, 3} の冪集合
について、例えば {1, 2}{2, 3} を考えれば、これらは比較不能であり({1, 2} ≤ {2, 3} でも {2, 3} ≤ {1, 2} でもない)、全順序ではない。
  • 線形空間の部分空間全体は包含関係で順序付けられた半順序集合である。
  • 半順序集合 P に対し、P の元の(自然数で添え字付けられた)列全体の成す集合は、列 a = (an)nN, b = (bn)nN に対し、
    と定めると半順序集合となる。
  • 集合 X と半順序集合 P に対し、X から P への写像全体の成す写像空間英語版は、2つの写像 f, g に対して、fgX の任意の元 x に対して f(x) ≤ g(x) となることとして定義すると、半順序集合になる。
  • 非循環有向グラフの頂点集合は、到達不可能性によって順序付けられる。
  • 半順序集合における順序関係の向きが a < b > c < d というように交互に入れ替わる列をフェンス英語版と呼ぶ。

逆順序、狭義の順序、双対順序[編集]

上で述べた順序関係「」は直観的には左辺が右辺「よりも小さい、もしくは等しい」ことを意味しているが、逆に左辺が右辺「よりも大きい、もしくは等しい」順序関係や等しいことを許容しない順序関係を考えることもできる。

逆順序[編集]

「大きい、もしくは等しい」ことを意味する順序関係は「」の逆順序と呼ばれ、

により定義される。

狭義の順序[編集]

一方、等しいことを許容しない順序は狭義の(半)順序と呼ばれ、以下のように定義される:

…(1)

狭義の逆順序「>」も同様に定義される。

狭義の順序「<」の対義語として、等しいことも許容する順序「」のことを広義の(半)順序(もしくは弱い意味 (weak) の(半)順序、反射的 (reflexive) な(半)順序)という。

(1) 式で定義された「<」を「」の反射的簡約 (reflexive reduction) という。

」が半順序であるとき、その反射的簡約「<」は任意の a, b, cP に対して以下を満たす:

  • 非反射性:¬(a < a);
  • 非対称性:a < b ならば ¬(b < a); (非反射性と推移性から従う)
  • 推移性:a < b かつ b < c ならば a < c

以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質(非対称性は非反射性と推移性より得られるので条件としては不要)を満たすものを狭義の順序として定義し、広義の順序を

…(2)

により定義することもできる。この場合、(2) 式で定義された「」を「<」の反射閉包英語版という。「<」が前述の3条件を満たせば反射閉包「」が半順序であることを簡単に示すことができる。

双対順序集合[編集]

(P, ≤) を順序集合とするとき、P 上の二項関係「」を

と定義する(すなわち「」は「」の逆順序を順序と見なしたものである)。すると、「」も P 上の順序になっていることが容易に分かる。(P, ≤)双対順序集合という。

双対順序集合はその定義 よりもとの順序集合 (P, ≤) とは"大小が逆転"している。したがって (P, ≤) における上限、極大元、最大元(定義は後述)は ではそれぞれ下限、極小元、最小元に対応している。

ハッセ図[編集]

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

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

頂点:P の元
aP から bP への辺がある a < b であり、しかも a < c < b を満たす cP が存在しない
(すなわち ba を被覆している)

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

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

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

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

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

上界、最大、極大、上限、上方集合[編集]

P半順序集合とし、A をその部分集合とし、xPとする。このとき上界、上限、最大、極大の概念、およびこれらの双対概念である下界(かかい)、下限、最小、極小は以下のように定義される:

定義[編集]

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

上界および上限の定義において、 x が必ずしも A の元であるとは限らない、ことには注意が必要である。

極大元の概念と最大元の概念は以下の点で異なる。まず xA の極大元であるとは、A の元は「x 以下である」か、もしくは「x とは大小が比較不能である」かのいずれかである事を意味する。一方 xA の最大元であるとは A の元は常に x 以下である事を意味する(このとき xA の任意の元と比較が可能である)。したがって最大元は必ず極大元であるが、極大元は必ずしも最大元であるとは限らない。

さらに AP上方集合英語版(resp. 下方集合)であるとは、任意の aA x > a (resp. x < a) を満たす任意の P の元に対しxA となることをいう。

具体例[編集]

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

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

写像と順序[編集]

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

定義[編集]

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

  • f: ST順序を保つ英語版(order-preserving)(同調 (isotone) とも)とは、
任意の x, yS に対して xyf(x) ≤ f (y)
  • f: ST順序を逆にするorder-reversing英語版)とは、
任意の x, yS に対して xyf (x) ≥ f (y)
  • 上の2つを合わせて単調 (monotone) 写像という。
  • f順序を反映する (order-reflecting) とは、
任意の x, yS に対して f (x) ≤ f (y) ⇒ xy
  • f順序埋め込み英語版であるとは、
任意の x, yS に対して xyf (x) ≤ f (y)
  • f順序同型写像英語版であるとは、f が順序埋め込みな全単射であることをいう。

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

性質[編集]

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

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

具体例[編集]

順序を保つが順序を反映しない写像
(f(u) ≤ f(v) だが uv でない)
120約数全体の成す半順序集合(整除関係で順序を入れる)と {2, 3, 4, 5, 8} の整除関係で閉じた部分集合族(包含関係で順序を入れる)との間の順序同型

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

区間[編集]

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

さらに [a, b) および (a, b] を以下のように定義し、半開区間と呼ぶ:

文献によっては (a, b), [a, b), (a, b] のことを ]a, b[, [a, b[, ]a, b] と表す場合もある。

半順序集合が局所有限英語版であるとは、全ての区間が有限集合であることをいう。例えば、整数全体の成す集合は通常の大小関係による半順序に関して局所有限である(端点の無い無限区間のようなものは今考えていない)。

順序集合における区間の概念と、区間順序英語版として知られる特定の半順序の類いとを混同してはならない。

順序構造と位相構造[編集]

全順序集合の位相[編集]

順序位相[編集]

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

全体の集合を準開基とする位相を順序位相 (order topology) という[注 1]。例えば、実数全体の集合 を通常の大小関係 ≤ による全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。

全順序集合 A の部分集合 B には、B を全順序集合と見なした時の順序位相と A の順序位相から誘導される位相との2つの位相が入る。しかしこの2つの位相は一致するとは限らない。(B の順序位相における開集合は誘導位相でも開集合であるが逆は一般には成り立たない)。

例えば A を実数全体の集合とし、A の部分集合

を考えると、A からB に誘導される位相では一元集合 {2} は明らかに開集合であるが、B は順序集合としてみたときはそうではない。実際 B は(2を1に移す写像により) と順序同型だが、C の順序位相で {1} は開集合ではないので B の順序位相で{2} は開集合ではない。

上極限位相、下極限位相[編集]

単に「実数体上の位相」といった場合、前述の順序位相を指すがその他の位相を考えることも(主に反例として用いるために)できる。

実数体 上の上極限位相とは

全体の集合を開基とする位相のことであり、同様に 上の下極限位相英語版とは逆向きの半開区間

全体の集合を開基とする位相のことである[注 2]

実数体に下限位相を入れた空間はしばし と書かれ、ゾルゲンフライ直線と呼ばれる。またゾルゲンフライ直線2つの直積 ゾルゲンフライ平面英語版と呼ばれる。

overlapping interval topology[編集]

区間 [-1,1] 上の overlapping interval topology とは

for
for

を準開基とする位相である。

半順序集合の位相[編集]

半順序空間[編集]

位相構造を持つ半順序集合P で以下の性質を満たすものを半順序空間英語版という:

a < b を満たす任意のa, bP に対し、a の開近傍Uで上方集合であるものと b の開近傍V で下方集合であるものが存在することである。

P の位相構造でこの性質を満たすものは1つとは限らないが、それらを全て半順序空間という。) なお、半順序空間と名前の似たposet topology英語版は別概念であるので注意が必要である。

定義より明らかに半順序空間は常にハウスドルフ性を満たす。

半順序空間では以下が成立する:

aia, bib かつ任意の i に対して aibi ならば ab である[1]

位相構造を持つ半順序集合P が半順序空間である必要十分条件は以下を満たすことである:

半順序集合P 上の位相構造として、{(a, b) ∈ P × P | ab } が直積位相に関する閉部分集合になる。

2つ半順序空間の間の順序を保つ連続写像のことをdimapという。

上方位相、下方位相[編集]

順序集合 P 上の以下の2つの位相は同一である事が簡単に示せる。以下のいずれか一方(したがって両方)の条件を満たす位相を上方位相英語版という。

  1. {xP | x ≥ a} for aP を全て閉集合とする最弱の位相
  2. 任意のaP に対し、一点集合{a} の閉包が{xP | x ≥ a} と一致する最弱の位相

下方位相も同様にして定義できる。

アレクサンドロフ空間[編集]

位相空間 Pアレクサンドロフ空間英語版であるとは、P 上の(有限または無限個の)任意の開集合の共通部分が必ず開集合になることである。

アレクサンドロフ空間は前順序集合と自然に1対1対応していることが知られている。 実際任意の前順序集合 P に対し、

UP の開集合 ⇔ UP の上方集合

により P に位相を入れたものはアレクサンドロフ空間になる。(この位相を Pアレクサンドロフ位相という。)

逆に任意のアレクサンドロフ空間 P に対し P 上の「specialization preorder英語版」を前順序とすることで P を前順序集合と見なすことができる。

ここで位相空間 Pspecialization preorderとは

で定義される前順序のことである。上式では一元集合{x}閉包である。(なお、PT0空間であればspecialization preorder は半順序であることが知られている。)

以上の対応関係により、集合P におけるアレクサンドロフ空間としての構造とP 上の前順序は1対1対応する。

specialization preorderはアレクサンドロフ空間でなくとも定義可能であるが、アレクサンドロフ空間でない位相空間上ではspecialization preorderに対して上方集合でない開集合も存在する。(なおこの場合でも開集合は常に上方集合である)。したがって前述したような、上方集合を開集合とする位相を考えても元の位相は復元できない。

実数体における例[編集]

実数体(に通常の順序をいれたもの)を前順序集合と見なすことで実数体にアレクサンドロフ位相を入れることができる。アレクサンドロフ位相における実数体上の開集合(すなわち上方集合)は以下のもののいずれかになる:

  • for some a
  • for some a
  • 空集合、全体集合

スコット位相[編集]

上で述べたようにアレクサンドロフ位相は のような「下に閉じた」集合すらも開集合と見なしてしまう。アレクサンドロフ位相からこのような不自然さを取り除いたのがスコット位相である。順序集合 P 上のスコット位相 (Scott topology) とは、以下の2条件を満たす P の部分集合 O 全体の集合を開集合族とする位相である:

  1. OP は上方集合である
  2. P有向部分集合 A で(A を自然に有向点族と見なしたときの)A の極限がO に入っていれば、A の点でO に含まれるものが存在する

後者の条件は内点概念の点列による特徴づけ(O の内点x に収束する点列はO と共通部分を持つ)に類似しているおり、この条件が「下に閉じた」集合を排除する。

よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる:

  • for some a
  • 空集合 、全体集合

スコット位相を入れた順序集合をスコット空間といい、スコット空間からスコット空間への連続写像をスコット連続 (Scott continuity) という。順序集合 P から順序集合Q への写像 f がスコット連続である必要十分条件は以下の性質が成り立つことであることが知られている:

  • P の任意の有向部分集合A に対し、AP 内の上限を持てばf (A )もQ 内の上限を持ち、sup f (A) = f (sup A ) が成立する。

スコット連続な関数は順序を保つ。実際、xy ⇒ sup{x , y } = x であるので、上述した条件よりsup{f (x ), f (y )}が存在し、しかも sup{f (x ), f (y )} = f (sup{x , y }) = f (x ) となる。これはf (x ) ≥ f (y ) を意味する。

なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものをローソン位相英語版という。

ストーン双対性[編集]

位相空間の開集合全体の集合は包含関係により順序集合と見なせる。位相空間が「sober性」という弱い性質を満たす時はこの順序構造のみで位相空間の構造が特徴づけられることが知られている(ストーンの双対性定理)。したがってsober性を満たす空間に話を限定すれば、点集合論に頼らなくても順序構造のみで位相空間論を展開できる(ポイントレス位相空間論)。

直積集合上の順序[編集]

2つの半順序集合(の台集合)の直積集合上の半順序としては次の三種類がある。

  • 辞書式順序
  • 積順序

最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の半順序は、いずれも3個以上の半順序集合の直積に対しても同様に定義される。

上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれも再び順序線型空間となる。

圏としての順序集合[編集]

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

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

その他[編集]

関連項目[編集]

脚注[編集]

[脚注の使い方]

注釈[編集]

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

出典[編集]

  1. ^ 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. 
  2. ^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8 

参考文献[編集]

  • 松坂和夫『集合・位相入門』岩波書店、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