出典(authority):フリー百科事典『ウィキペディア(Wikipedia)』「2015/09/16 12:00:32」(JST)
数学において順序集合(じゅんじょしゅうごう、英: ordered set)とは 「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。
ただし順序集合内の2つの元a、b に順序関係が定まっている必要はなく、両者が「比較不能」であってもよい。よってa、b の関係は「a はb 以上である」、「b はa 以上である」、「a とb は比較不能である」の3通りのいずれかとなる。
比較不能のケースを許容している強調して順序集合の事を半順序集合(はんじゅんじょしゅうごう、英: partially ordered set, poset)ともいう。一方、半順序集合の中で比較不能のケースがないものを特に全順序集合(totally ordered set)という。(「半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も半順序集合の一種である)。
全順序集合の簡単な例は整数の集合や実数の集合で、通常の大小比較を順序とみなしたものがある。
一方、全順序ではない半順序集合の例としては(2つ以上元を含む)集合の冪集合で、包含関係を順序とみなしたものがある。例えば3元集合P ={a,b,c}において{a,b}と{b,c}はいずれも他方を包含していないのでP の冪集合は全順序ではない。実生活に近い例では、「AさんはBさんの子孫である」という事を「A<B」という大小関係とみなす事で人間全体の集合を半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる(兄弟同士、叔父と甥、赤の他人等)ので、この順序集合は全順序ではない。
全順序集合、半順序集合、およびこれらよりさらに弱い概念である前順序集合の定義を述べる為にまず以下の性質を考える。ここでP は集合であり、「≤」をP 上で定義された二項関係 である。
「≤」が全順序律を満たさない場合、「a ≤ b」でも「b ≤ a」でもないケースがある。このような第三のケースにあるときa とbは比較不能であるという。
P を集合とし、≤ を P 上で定義された二項関係 とする。
≤ が前順序である (P, ≤) を前順序集合という。同様に ≤ が半順序なら (P, ≤) は半順序集合、全順序なら (P, ≤) は全順序集合である。また集合 P は (P, ≤) の台 (support) と呼ばれる。紛れがなければ ≤ を省略し、P の事を(いずれかの意味で)順序集合という。
順序集合 (P, ≤) に対し、≤ を台 P 上の順序関係ともいう。 なお多くの数学の分野では半順序集合を主に扱うので、単に順序あるいは順序集合といった場合はそれぞれ半順序、半順序集合を意味する場合が多いが、分野によっては、主な対象が半順序集合でなく前順序集合や全順序集合である場合があり、そのような分野では前順序集合や全順序集合の意味で「順序集合」という言葉が用いられることがあるので注意が必要である。
上では順序を記号 ≤ で表したが、必ずしもこの記号で表現する必要はない。 実数の大小を表す記号 ≤ と区別する為、順序の記号として や を使うこともある。
全順序の事を線型順序ともいい、全順序集合のことを鎖と呼ぶこともある。また半順序集合の部分集合 A で A の任意の相異なる二元が比較不能であるものを反鎖(英語版)という。
半順序集合の元 a が他の元 b によって被覆される(英語版) a <: b とは、a は b よりも真に小さく、かつそれらの間に別の元が入ることはないこと(後述する狭義の記号を使って書けば a < b かつ任意の c に対して a < c < b が偽となること)をいう。
上で述べた順序関係「≤」は直観的には左辺が右辺よりも「小さい、もしくは等しい」事を意味しているが、逆に左辺が右辺よりも「大きい、もしくは等しい」順序関係や等しい事を許容しない順序関係を考える事もできる。
「大きい、もしくは等しい」事を意味する順序関係は「≤」の逆順序と呼ばれ、
により定義される。
一方、等しい事を許容しない順序は狭義の(半)順序と呼ばれ、以下のように定義される:
狭義の逆順序「>」も自然に定義される。
狭義の順序「<」の対義語として、等しい事も許容する順序「≤」の事を広義の(半)順序(もしくは弱い意味 (weak) の(半)順序、反射的 (reflexive) な(半)順序)という。
(1)式で定義された「<」を「≤」の反射的簡約 (reflexive reduction) という。
「≤」が半順序であるとき、その反射的簡約「<」は任意のa, b, c ∈ P に対して以下を満たす:
以上では広義の順序からスタートして狭義の順序を定義したが、逆に上の三性質を満たすものを狭義の順序として定義し、広義の順序を
により定義する事もできる。 この場合、(2)式で定義された「≤」を「<」の反射閉包(英語版)という。 「<」が前述の3条件を満たせば反射閉包「≤」が半順序である事を簡単に示す事ができる。
(P , ≤)を順序集合とするとき、P 上の二項関係「」を
と定義する(すなわち「」は「≤」の逆順序を順序とみなしたものである)。すると、「」もP 上の順序になっている事が簡単に示せる。を(P , ≤)の双対順序集合という。
双対順序集合はその定義よりもとの順序集合(P , ≤)とは大小が逆転している。したがって(P , ≤)における上限、極大元、最大元はではそれぞれ下限、極小元、最小元になる。
P を有限集合とし、「<」をP 上の狭義の半順序とするとき、以下のようにしてP を自然に単純有向グラフとみなせる:
この有向グラフを図示したものをハッセ図という。
右に示した図がハッセ図の例である。この図では三元集合 {x, y, z}の 部分集合の全体を包含関係を順序とする順序集合とみなしたものをハッセ図として表している。
ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。 例えばこの図で {x} と {x,y,z} は比較可能だが、{x} と {y} は比較不能である。 また一元集合の族 {{x}, {y}, {z}}は反鎖である。 さらに{x} は {x,z} によって被覆されるが、{x,y,z} には被覆されない。
なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。 逆に(V , E )を閉路を持たない有限な単純有向グラフとすると、V 上に以下の順序を入れる事でV を半順序集合とみなせる:
したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。
P を半順序集合とし、A をその部分集合とし、x を P の元とする。 このとき上界、最大、極大、上限の概念、およびこれらの双対概念である下界、最小、極小、下限は以下のように定義される:
上界および上限の定義において x が A に必ずしも属さないことには注意が必要である。
極大元の概念と最大元の概念は以下の点で異なる。 まず x が A の極大元であるとは、A の元は「x 以下である」か、もしくは「x とは大小が比較不能である」かのいずれかである事を意味する。一方 x が A の最大元であるとは A の元は常に x 以下である事を意味する(このとき A の元は x と比較可能である)。したがって最大元は極大元であるが、極大元は必ずしも最大元であるとは限らない。
さらに A が P の上方集合(英語版)(resp. 下方集合)であるとは、任意の a ∈ A と x > a (resp. x < a) を満たす任意の P の元に対しx ∈ A となることをいう。
|
|
正整数全体の成す集合を整除関係で順序付ける時、1 は任意の正整数を割り切るという意味において 1 は最小元である。しかしこの半順序集合には最大元は存在しない(任意の正整数の倍数としての 0 を追加して考えたとするならば、それが最大元になる)。この半順序集合には極大元も存在しない。実際、任意の元 g はそれとは異なる例えば 2g を割り切るから g は極大ではありえない。この半順序集合から最小元である 1 を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して 60 は部分集合 {2,3,5,10} の上界(上限ではない)を与えるが、1 は除かれているので下界は持たない。他方、2 の冪全体の成す部分集合に対して 2 はその下界(これは下限でもある)を与えるが、上界は存在しない。
順序に関する写像の概念に以下のものがある:
S 、T を順序集合とし、f: S → T を写像とする。このとき
f: S → T が順序埋め込みであるとき、S はf によって T に(順序集合として)埋め込まれるという。 またf: S → T が順序同型なとき、S とT は順序同型あるいは単に同型であるという。
上で述べた概念は以下の性質を満たす:
|
|
自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 f: ℕ → ℙ(ℕ) を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である(すなわち、x が y を割るならば x の各素因数は y の素因数にもなる)が単射ではない(例えば 12 も 6 もこの写像で {2,3} に写る)し、順序を反映もしない(例えば 12 は 6 を割らない)。少し設定を変えて、各自然数にその素冪因子(英語版)の集合を対応させる写像 g: ℕ → ℙ(ℕ) を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない(実際、たとえば単元集合 {4} に写る数は無い)が終域を g の値域 g(ℕ) に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な分配束(英語版)と呼ばれる半順序集合のクラスに対して一般化することができる(バーコフの表現定理(英語版)の項を参照)。
P を順序集合とし、a、b をP の元とする時、閉区間 [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つの直積はゾルゲンフライ平面(英語版)と呼ばれる。
区間[-1,1]上のoverlapping interval topologyとは
を準開基とする位相である。
位相構造を持つ半順序集合P で以下の性質を満たすものを半順序空間(英語版)という:
(P の位相構造でこの性質を満たすものは1つとは限らないが、それらを全て半順序空間という。) なお、半順序空間と名前の似たposet topology(英語版)は別概念であるので注意が必要である。
定義より明らかに半順序空間は常にハウスドルフ性を満たす。
半順序空間では以下が成立する:
位相構造を持つ半順序集合P が半順序空間である必要十分条件は以下を満たす事である:
2つ半順序空間の間の順序を保つ連続写像の事をdimapという。
順序集合P 上の以下の2つの位相は同一である事が簡単に示せる。以下のいずれか一方(したがって両方)の条件を満たす位相を上方位相(英語版)という。
下方位相も同様にして定義できる。
位相空間P がアレクサンドロフ空間(英語版)であるとは、P上の(有限または無限個の)任意の開集合の共通部分が必ず開集合になる事を言う。
アレクサンドロフ空間は前順序集合と自然に1対1対応している事が知られている。 実際任意の前順序集合P に対し、
によりP に位相を入れたものはアレクサンドロフ空間になる。(この位相をP のアレクサンドロフ位相という。)
逆に任意のアレクサンドロフ空間P に対しP 上の「specialization preorder(英語版)」を前順序とする事でP を前順序集合とみなす事ができる。
ここで位相空間P のspecialization preorderとは
で定義される前順序の事である。上式では一元集合 {x } の閉包である。(なお、PがT0空間であればspecialization preorderは半順序である事が知られている。)
以上の対応関係により、集合P におけるアレクサンドロフ空間としての構造とP 上の前順序は1対1対応する。
specialization preorderはアレクサンドロフ空間でなくとも定義可能であるが、アレクサンドロフ空間でない位相空間上ではspecialization preorderに対して上方集合でない開集合も存在する。(なおこの場合でも開集合は常に上方集合である)。したがって前述したような、上方集合を開集合とする位相を考えても元の位相は復元できない。
実数体(に通常の順序をいれたもの)を前順序集合とみなす事で実数体にアレクサンドロフ位相を入れる事ができる。アレクサンドロフ位相における実数体上の開集合(すなわち上方集合)は以下のもののいずれかになる:
上で述べたようにアレクサンドロフ位相はのような「下に閉じた」集合すらも開集合とみなしてしまう。アレクサンドロフ位相からこのような不自然さを取り除いたのがスコット位相である。 順序集合P 上のスコット位相(Scott topology)とは、以下の2条件を満たすP の部分集合O 全体の集合を開集合族とする位相である:
後者の条件は内点概念の点列による特徴づけ(O の内点x に収束する点列はO と共通部分を持つ)に類似しているおり、この条件が「下に閉じた」集合を排除する。
よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる:
スコット位相を入れた順序集合をスコット空間といい、スコット空間からスコット空間への連続写像をスコット連続(Scott continuity)という。順序集合P から順序集合Q への写像f がスコット連続である必要十分条件は以下の性質が成り立つ事である事が知られている:
スコット連続な関数は順序を保つ。実際、x ≥ y ⇒ 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性を満たす空間に話を限定すれば、点集合論に頼らなくても順序構造のみで位相空間論を展開できる(ポイントレス位相空間論)。
ふたつの半順序集合(の台集合)の直積集合上の半順序としては次の三種類が考えられる。
最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの半順序集合の直積に対しても同様に定義される。
体上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。
ℕ×ℕ 上の直積狭義順序の反射閉包。
ℕ×ℕ 上の積順序
ℕ×ℕ 上の辞書式順序
任意の半順序集合(および前順序集合)は、任意の射集合が高々一つの元からなる圏と看做すことができる。具体的には、射の集合を x ≤ y ならば hom(x, y) = {(x, y)} (それ以外の場合は空集合) とし、(y, z)∘(x, y) = (x, z) と定義する。二つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏は同型射について閉じて(英語版)いる。
半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。
ウィキメディア・コモンズには、Hasse diagramに関連するメディアがあります。 |
全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.
リンク元 | 「配列」「連続」「結果」「sequence」「指令」 |
for ( $i = 0 ; $i < 5 ; $i++ ) { $a['w'][$i] = $i+100; $a['m'][$i] = 1; } for ( $i = 5 ; $i < 15 ; $i++ ) { $a['w'][$i] = $i+100; $a['m'][$i] = 2; } for ( $i = 15 ; $i < 20 ; $i++ ) { $a['w'][$i] = $i+100; $a['m'][$i] = 3; } $a['w'][5]=100; $a['w'][15]=100; var_dump($a); $b = array_unique($a['w']); #配列 重複キー 消去 var_dump($b); ----- array(2) { ["w"]=> array(20) { [0]=> int(100) [1]=> int(101) [2]=> int(102) [3]=> int(103) [4]=> int(104) [5]=> int(100) [6]=> int(106) [7]=> int(107) [8]=> int(108) [9]=> int(109) [10]=> int(110) [11]=> int(111) [12]=> int(112) [13]=> int(113) [14]=> int(114) [15]=> int(100) [16]=> int(116) [17]=> int(117) [18]=> int(118) [19]=> int(119) } ["m"]=> array(20) { [0]=> int(1) [1]=> int(1) [2]=> int(1) [3]=> int(1) [4]=> int(1) [5]=> int(2) [6]=> int(2) [7]=> int(2) [8]=> int(2) [9]=> int(2) [10]=> int(2) [11]=> int(2) [12]=> int(2) [13]=> int(2) [14]=> int(2) [15]=> int(3) [16]=> int(3) [17]=> int(3) [18]=> int(3) [19]=> int(3) } } array(18) { [0]=> int(100) [1]=> int(101) [2]=> int(102) [3]=> int(103) [4]=> int(104) [6]=> int(106) [7]=> int(107) [8]=> int(108) [9]=> int(109) [10]=> int(110) [11]=> int(111) [12]=> int(112) [13]=> int(113) [14]=> int(114) [16]=> int(116) [17]=> int(117) [18]=> int(118) [19]=> int(119) }
$str = implode('/',$array);
.