「全順序」の版間の差分
削除された内容 追加された内容
m ロボットによる: 二重リダイレクト修正 → 順序集合 |
Quickbaster (会話 | 投稿記録) en:Total order 06:47, 20 January 2014 タグ: サイズの大幅な増減 |
||
1行目:
[[数学]]における'''線型順序'''（せんけいじゅんじょ、{{lang-en-short|''linear order''}}）、'''全順序'''（ぜんじゅんじょ、{{lang-en-short|''total order''}}）または'''単純順序'''（たんじゅんじゅんじょ、{{lang-en-short|''simple order''}}）は、[[推移的関係|推移的]]、[[反対称関係|反対称]]かつ[[完全関係|完全]]な[[二項関係]]を言う。集合と全順序を組にしたものは、'''全順序集合''' (''totally ordered set''), '''線型順序集合''' (''linearly ordered set''), '''単純順序集合''' (''simply ordered set'') あるいは'''鎖''' (''chain'') と呼ばれる。
即ち、[[集合]] ''X'' が関係 ≤ によって全順序付けられるとき、''X'' の任意の元 ''a'', ''b'', ''c'' に対して、以下の条件
: 反対称律: ''a'' ≤ ''b'' かつ ''b'' ≤ ''a'' ならば ''a'' = ''b'';
: 推移律: ''a'' ≤ ''b'' かつ ''b'' ≤ ''c'' ならば ''a'' ≤ ''c'';
: 完全律 (比較可能): ''a'' ≤ ''b'' または ''b'' ≤ ''a'' の何れかが必ず成り立つ;
が満足される。
反対称性によって ''a'' < ''b'' でも ''b'' < ''a'' でもあるような不確定な状態は排除される<ref>{{cite book |last=Nederpelt |first=Rob |title=Logical Reasoning: A First Course |publisher=King's College Publications|year=2004| series=Texts in Computing|volume=3|edition=3rd, Revised |page=325 |chapter=Chapter 20.2: Ordered Sets. Orderings|isbn=0-9543006-7-X}}</ref>。完全性を持つ関係は、その集合の任意の二元がその関係で{{仮リンク|比較可能性|en|Comparability|label=比較可能}}であることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である<ref>{{cite book |last=Nederpelt |first=Rob |title=Logical Reasoning: A First Course |publisher=King's College Publications|year=2004| series=Texts in Computing|volume=3|edition=3rd, Revisied |page=330 |chapter=Chapter 20.3: Ordered Sets. Linear orderings|isbn=0-9543006-7-X}}</ref>。また完全性から'''反射性''' (''a'' ≤ ''a'') が出るから、全順序は[[半順序]]の公理を満たす。半順序は（完全性の代わりに反射性のみが課されるという意味で）全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序の{{仮リンク|線型拡張|en|linear extension}}と呼ばれる。
== 狭義全順序 ==
任意の（広義）全順序関係 ≤ に対し、それに付随する[[非対称関係|非対称]]（従って非反射的）な'''狭義全順序''' (''strict total order'') と呼ばれる関係 {{math|<}} が存在する。これは次の互いに同値な二種類の仕方で定義することができる。
* ''a'' < ''b'' [[必要十分条件|⇔]] ''a'' ≤ ''b'' かつ ''a'' ≠ ''b''
* ''a'' < ''b'' ⇔ ''b'' ≤ ''a'' でない
後者は、関係 {{math|<}} が ≤ の{{仮リンク|補関係|en|Binary_relation#Complement}}の[[逆関係]]であることを意味するものである。
; 性質:
:* 推移律: ''a'' < ''b'' かつ ''b'' < ''c'' ならば ''a'' < ''c''.
:* {{仮リンク|三分法 (数学)|label=三分律|en|Trichotomy (mathematics)}}: ''a'' < ''b'' または ''b'' < ''a'' または ''a'' = ''b'' の何れか一つのみが成立する。
:* 恒等性を付随する同値関係とする{{仮リンク|狭義弱順序|en|strict weak order}}である。
推移的かつ三分的な二項関係 < が最初に与えられたとき、そこから（広義の）全順序 ≤ を定めることも、次の同値な二種類の方法
* ''a'' ≤ ''b'' ⇔ ''a'' < ''b'' または ''a'' = ''b''
* ''a'' ≤ ''b'' ⇔ ''b'' < ''a'' でない
でできる。
他にも二つ、これらの補関係 ≥ と > を考えることができ、[[タプル|四つ組]] {<, >, ≤, ≥} はどれからでも他の三種類を導出することができるから、集合が全順序付けられることをいうのにいずれの関係を用いて定義・記述してもよい（特に広義か狭義かは記号で区別できる）。
== 例 ==
* 通常の[[アルファベット順]]（たとえば ''A'' < ''B'' < ''C'' など）は文字列全体の成す集合を全順序付ける。
* 全順序集合の任意の部分集合は、もとの全体集合の順序をその部分集合に制限することで、全順序付けられる。
* [[順序数]]からなる任意の集合、あるいは[[基数]]からなる任意の集合。これらは単に全順序集合であるばかりでなく、さらに強く[[整列集合]]になる。
* 任意の集合 ''X'' と ''X'' から全順序集合への[[単射]] ''f'' に対し、{{math|''x''<sub>1</sub> < ''x''<sub>2</sub> ⇔ ''f''(''x''<sub>1</sub>) < ''f''(''x''<sub>2</sub>)}} と置くことにより、''f'' は ''X'' 上の全順序を誘導する。
* 適当な順序数で添字付けられた全順序集合族の[[直積集合|デカルト積]]は、その上に[[自書式順序]]を入れることにより、それ自身全順序集合になる。例えば、アルファベット順に並べた任意の語の集合が全順序付けられることは、（スペースの記号をどの文字よりも小さいものとして加えた）アルファベットの集合の可算個のコピーからなる集合族のデカルト積に自書式順序を入れることで理解できる。
* [[実数]]全体の成す集合 '''R''' は通常の大小関係 ({{math|"<"}} あるいは {{math|">"}}) によって全順序付けられる。従ってその部分集合としての、[[自然数]]全体の成す集合 '''N''', [[整数]]全体の成す集合 '''Z''', [[有理数]]全体の成す集合 '''Q''' なども全順序集合になる。これらは何れも、ある性質に関して最小の全順序集合として（[[同型]]を[[違いを除いて|除いて]]）唯一の例を与えることが示せる（ここで、全順序集合 ''A'' がある性質に関して「最小」とは、同じ性質を持つ任意の ''B'' に対して ''A'' に順序同型な ''B'' の部分集合が存在することをいう）。
** '''N''' は[[上界]]を持たない最小の全順序集合である。
** '''Z''' は上界も[[下界]]も持たない最小の全順序集合である。
** '''Q''' は '''R''' の中で[[稠密順序関係|稠密]]となる最小の全順序集合である。ここでいう稠密性は {{math|''a'' < ''b''}} なる任意の実数 ''a'', ''b'' に対し、{{math|''a'' < ''q'' < ''b''}} となる有理数 ''q'' が必ず存在することを言う。
** '''R''' は順序位相（後述）に関して[[連結空間|連結]]となる最小の非有界全順序集合である。
* [[順序体]]は定義により全順序である。これは有理数体 '''Q''' や実数体 '''R''' を包括する概念である。
== 関連する概念 ==
=== 鎖 ===
全順序の同義語としても用いられる'''鎖'''（さ、{{lang-en-short|''chain''}}）は、また適当な[[半順序集合]]の全順序部分集合に対しても用いられる。後者の意味での鎖は[[ツォルンの補題]]で極めて重要な役割を果たす。
例えば[[整数]]全体の成す集合 '''Z''' に[[包含関係]]で半順序を入れた半順序集合を考えると、[[自然数]] ''n'' に対し、''n'' 以下の自然数全体の成す部分集合 ''I''<sub>''n''</sub> からなる集合族 {{math|{ ''I''<sub>''n''</sub> : ''n'' は自然数}}} はこの順序に関する鎖、すなわち包含関係に関する全順序部分集合になる。実際、''n''≤''k'' ならば ''I''<sub>''n''</sub> は ''I''<sub>''k''</sub> の部分集合である。
=== 束 ===
全順序集合を特定の種類の[[束 (順序集合論)|束]]として定義することもできる。つまり、任意の ''a'', ''b'' に対して
: <math>\{a\vee b, a\wedge b\} = \{a, b\}</math>
が成り立つものとして、''a'' ≤ ''b'' [[必要十分条件|⇔]] <math>a = a\wedge b</math> と定義するのである。これにより、全順序集合は[[分配束]]になる。
=== 有限全順序 ===
単に{{仮リンク|計数|lanel=数え上げ|en|counting}}<!--not [[数え上げ]]: enumeration (付番)-->を考えることにより、任意の空でない有限全順序集合が（従ってその任意の空でない部分集合が）最小元を持つことが確定する。すなわち、任意の有限全順序は[[整列順序]]である。任意の有限全順序が、通常の大小関係 {{math|<}} で順序付けられた自然数全体の成す集合 '''N''' の何れかの{{仮リンク|始片|en|initial segment|label=始切片}}に[[順序同型]]なることは、直接証明することもできるし、任意の整列順序が何れかの[[順序数]]に順序同型なることを見てもわかる。言い換えれば、[[有限集合|''k''-元集合]]上の全順序は、自然数の最初の ''k'' 個からなる全順序から誘導される。従て、有限全順序または[[順序型]] ω を持つ整列順序は、順序の観点からは自然数（0 から始まるか 1 から始まるかは問わず）で付番するのが普通である。
=== 圏論的記述 ===
順序を保つ写像 ''f''（{{math|''a'' ≤ ''b'' ならば ''f''(''a'') ≤ ''f''(''b'')}}）を[[射 (圏論)|射]]として、全順序集合の全体は[[半順序集合]]の[[圏 (数学)|圏]]の[[充満部分圏]]になる。
このとき、二つの全順序集合の間の[[全単射]]な射はこの圏における[[同型射]]になる。
=== 順序位相 ===
任意の全順序集合 ''X'' に対して、[[区間 (数学)|開区間]]は
: (''a'', ''b'') = {''x'' : ''a'' < ''x'' かつ ''x'' < ''b''},
: (−∞, ''b'') = {''x'' : ''x'' < ''b''},
: (''a'', ∞) = {''x'' : ''a'' < ''x''},
: (−∞, ∞) = ''X''
などと定義することができる。これらの開区間を用いて任意の順序集合上に[[位相空間|位相]]を定義することができる（{{仮リンク|順序位相|en|order topology}}の項を参照）。
一つの集合上に複数の順序が定義されているとき、そのそれぞれから誘導される順序位相について考えることができる。例えば、自然数の集合 '''N''' に小なり {{math|<}} と大なり {{math|>}} の二つの全順序を考えると、{{math|<}} の誘導する '''N''' の順序位相も {{math|>}} の誘導する '''N''' の順序位相も考えられる（今の場合は両者は一致するが、一般には必ずしも一致しない）。
全順序の誘導する順序位相は、遺伝的[[正規空間|正規]]であることが示せる。
=== 完備性 ===
全順序集合が'''完備''' (''complete'') であるとは、その空でない任意の部分集合が[[上界]]を持つこと、従って[[上限]]を持つことをいう。例えば[[実数]]全体の成す集合 '''R''' は完備だが、[[有理数]]全体の成す集合 '''Q''' はそうでない。
集合 ''X'' が完備となるような順序位相の性質についての結果はいくつもある。
* ''X'' 上の順序位相が連結ならば ''X'' は完備である。
* ''X'' が順序位相に関して連結となる必要十分条件は、それが完備かつ ''X'' に「ギャップ」がないことである（ここで「ギャップ」は ''X'' の適当な二点 ''a'', ''b'' ({{math|''a'' < ''b''}}) に対して {{math|''a'' < ''c'' < ''b''}} を満たす点 ''c'' が存在しないことをいう）。
* ''X'' が完備となる必要十分条件は、その順序位相に関する任意の閉有界集合がコンパクトとなることである。
[[完備束]]を成す全順序集合はその順序位相に関して[[コンパクト空間|コンパクト]]である。実数からなる閉区間（例えば単位閉区間 {{math|[0,1]}} ）や、[[拡大実数直線]]はそういった例である。この二つの例の間には順序を保つ[[同相]]がある。
=== 順序の和 ===
二つの順序 <math>(A_1,\le_1)</math> と <math>(A_2,\le_2)</math> の非交和と呼ばれる自然な順序 <math>\le_+</math> が和集合 <math>A_1\cup A_2</math> 上に定義される。しばしばこれを順序集合の和と呼び、単に <math>A_1+A_2</math> で表す。
: <math>x,y\in A_1\cup A_2</math> に対し <math>x\le_+ y</math> は以下の何れかひとつを満足することと定められる:
:# <math>x,y\in A_1</math> かつ <math>x\le_1 y</math>
:# <math>x,y\in A_2</math> かつ <math>x\le_2 y</math>
:# <math>x\in A_1</math> かつ <math>y\in A_2</math>
直観的にはこれは二番目の集合の各元を一番目の集合の最大元の後ろに並べることを意味する。
より一般に、全順序付けられた添字集合 <math>(I,\le)</math> の各元 <math>i\in I</math> に対して全順序集合 <math>(A_i,\le_i)</math> が対応して、各集合は対ごとに交わらないものとするとき、<math>\bigcup_i A_i</math> 上の自然な全順序が
: <math>x,y\in \bigcup_{i\in I} A_i</math> に対して <math>x\le y</math> であるとは、
:# 適当な <math>i\in I</math> について <math> x\le_i y </math> となるか
:# <math>I</math> 上で <math>i<j</math> なる添字について <math> x\in A_i</math> かつ <math> y\in A_j</math> となること
と置くことにより定義される。
== 全順序集合の直積上の順序 ==
二つの全順序集合の[[直積集合]]上に三つの順序を入れることができる。強い順に並べると
* [[辞書式順序]]: (''a'',''b'') ≤ (''c'',''d'') ⇔ ''a'' < ''c'' または (''a'' = ''c'' かつ ''b'' ≤ ''d''). (これはまた全順序を与える)
* {{仮リンク|積順序|en|product order}}: (''a'',''b'') ≤ (''c'',''d'') ⇔ ''a'' ≤ ''c'' かつ ''b'' ≤ ''d'' (これは半順序になる)..
* 対応する狭義全順序の直積関係: (''a'',''b'') ≤ (''c'',''d'') ⇔ (''a'' < ''c'' かつ ''b'' < ''d'') または (''a'' = ''c'' かつ ''b'' = ''d'') (これも半順序).
これら三種の順序は二つより多くの直積の場合にも同様に定義することができる。
[[数ベクトル空間]] '''R'''<sup>''n''</sup> にこれらのそれぞれを適用して、{{仮リンク|順序線型空間|en|ordered vector space}}にすることができる。
'''R'''<sup>''n''</sup> の部分集合上定義される実 ''n''-変数の実函数は、その部分集合上に{{仮リンク|狭義弱順序|label=狭義弱順序と対応する全前順序|en|Strict_weak_ordering#Function}}を定める。
== 関連する構造 ==
反対称、推移的かつ反射的（だが必ずしも完全でない）二項関係は[[半順序]]と言う。
両立する全順序を持つ[[群 (数学)|群]]は{{仮リンク|全順序群|en|totally ordered group}}と呼ぶ。
全順序を緩めて得られる全順序性と相互に読み替えられる非自明な構造はそれほどない。向きを忘れれば{{仮リンク|媒介関係|en|betweenness relation}}が得られ、端点の位置を忘れれば{{仮リンク|巡回順序|en|cyclic order}}が、それらの両方を忘れれば{{仮リンク|分離関係|en|separation relation}}が出る<ref>{{Citation |last=Macpherson |first=H. Dugald |year=2011 |title=A survey of homogeneous structures |journal=Discrete Mathematics |doi=10.1016/j.disc.2011.01.024 |url=http://www.amsta.leeds.ac.uk/pure/staff/macpherson/homog_final2.pdf |accessdate=28 April 2011}}</ref>。
== 関連項目 ==
* {{仮リンク|順序論|en|Order theory}}
* [[整列順序]]
* [[ススリンの問題]]
* {{仮リンク|カントリーマン直線|en|Countryman line}}
== 注釈 ==
{{Reflist|2}}
== 参考文献 ==
* George Grätzer (1971). ''Lattice theory: first concepts and distributive lattices.'' W. H. Freeman and Co. ISBN 0-7167-0442-0
* John G. Hocking and Gail S. Young (1961). ''Topology.'' Corrected reprint, Dover, 1988. ISBN 0-486-65676-4
{{DEFAULTSORT:せんしゆんしよ}}
[[Category:関係 (数学)]]
[[Category:順序構造]]
[[Category:集合論]]
| |||