コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「全順序」の版間の差分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
AvicBot (会話 | 投稿記録)
m ロボットによる: 二重リダイレクト修正 → 順序集合
(同じ利用者による、間の1版が非表示)
1行目: 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'') と呼ばれる。
#REDIRECT [[順序集合]]

即ち、[[集合]] ''X'' が関係 ≤ によって全順序付けられるとき、''X'' の任意の元 ''a'', ''b'', ''c'' に対して、以下の条件
: 反対称律: ''a'' ≤ ''b'' かつ ''b'' ≤ ''a'' ならば ''a'' = ''b'';
: 推移律: ''a'' ≤ ''b'' かつ ''b'' ≤ ''c'' ならば ''a'' ≤ ''c'';
: 完全律 (比較可能): ''a'' ≤ ''b'' または ''b'' ≤ ''a'' の何れかが必ず成り立つ;
が満足される。

反対称性によって ''a'' &lt; ''b'' でも ''b'' &lt; ''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|&lt;}} が存在する。これは次の互いに同値な二種類の仕方で定義することができる。
* ''a'' < ''b'' [[必要十分条件|⇔]] ''a'' ≤ ''b'' かつ ''a'' ≠ ''b''
* ''a'' < ''b'' ⇔ ''b'' ≤ ''a'' でない
後者は、関係 {{math|&lt;}} が ≤ の{{仮リンク|補関係|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'' &lt; ''b''}} なる任意の実数 ''a'', ''b'' に対し、{{math|''a'' &lt; ''q'' &lt; ''b''}} となる有理数 ''q'' が必ず存在することを言う。
** '''R''' は順序位相(後述)に関して[[連結空間|連結]]となる最小の非有界全順序集合である。
* [[順序体]]は定義により全順序である。これは有理数体 '''Q''' や実数体 '''R''' を包括する概念である。

== 関連する概念 ==
=== 鎖 ===
全順序の同義語としても用いられる'''鎖'''(さ、{{lang-en-short|''chain''}})は、また適当な[[半順序集合]]の全順序部分集合に対しても用いられる。後者の意味での鎖は[[ツォルンの補題]]で極めて重要な役割を果たす。

例えば[[整数]]全体の成す集合 '''Z''' に[[包含関係]]で半順序を入れた半順序集合を考えると、[[自然数]] ''n'' に対し、''n'' 以下の自然数全体の成す部分集合 ''I''<sub>''n''</sub> からなる集合族 {{math|{ ''I''<sub>''n''</sub> : ''n'' は自然数}}} はこの順序に関する鎖、すなわち包含関係に関する全順序部分集合になる。実際、''n''&le;''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|&lt;}} で順序付けられた自然数全体の成す集合 '''N''' の何れかの{{仮リンク|始片|en|initial segment|label=始切片}}に[[順序同型]]なることは、直接証明することもできるし、任意の整列順序が何れかの[[順序数]]に順序同型なることを見てもわかる。言い換えれば、[[有限集合|''k''-元集合]]上の全順序は、自然数の最初の ''k'' 個からなる全順序から誘導される。従て、有限全順序または[[順序型]] &omega; を持つ整列順序は、順序の観点からは自然数(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:集合論]]
[[Category:数学に関する記事]]

2014年2月12日 (水) 17:13時点における版

数学における線型順序(せんけいじゅんじょ、: linear order)、全順序(ぜんじゅんじょ、: total order)または単純順序(たんじゅんじゅんじょ、: simple order)は、推移的反対称かつ完全二項関係を言う。集合と全順序を組にしたものは、全順序集合 (totally ordered set), 線型順序集合 (linearly ordered set), 単純順序集合 (simply ordered set) あるいは (chain) と呼ばれる。

即ち、集合 X が関係 ≤ によって全順序付けられるとき、X の任意の元 a, b, c に対して、以下の条件

反対称律: ab かつ ba ならば a = b;
推移律: ab かつ bc ならば ac;
完全律 (比較可能): ab または ba の何れかが必ず成り立つ;

が満足される。

反対称性によって a < b でも b < a でもあるような不確定な状態は排除される[1]。完全性を持つ関係は、その集合の任意の二元がその関係で比較可能英語版であることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である[2]。また完全性から反射性 (aa) が出るから、全順序は半順序の公理を満たす。半順序は(完全性の代わりに反射性のみが課されるという意味で)全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序の線型拡張英語版と呼ばれる。

狭義全順序

任意の(広義)全順序関係 ≤ に対し、それに付随する非対称(従って非反射的)な狭義全順序 (strict total order) と呼ばれる関係 < が存在する。これは次の互いに同値な二種類の仕方で定義することができる。

  • a < b ab かつ ab
  • a < bba でない

後者は、関係 < が ≤ の補関係英語版逆関係であることを意味するものである。

性質
  • 推移律: a < b かつ b < c ならば a < c.
  • 三分律英語版: a < b または b < a または a = b の何れか一つのみが成立する。
  • 恒等性を付随する同値関係とする狭義弱順序英語版である。

推移的かつ三分的な二項関係 < が最初に与えられたとき、そこから(広義の)全順序 ≤ を定めることも、次の同値な二種類の方法

  • aba < b または a = b
  • abb < a でない

でできる。

他にも二つ、これらの補関係 ≥ と > を考えることができ、四つ組 {<, >, ≤, ≥} はどれからでも他の三種類を導出することができるから、集合が全順序付けられることをいうのにいずれの関係を用いて定義・記述してもよい(特に広義か狭義かは記号で区別できる)。

  • 通常のアルファベット順(たとえば A < B < C など)は文字列全体の成す集合を全順序付ける。
  • 全順序集合の任意の部分集合は、もとの全体集合の順序をその部分集合に制限することで、全順序付けられる。
  • 順序数からなる任意の集合、あるいは基数からなる任意の集合。これらは単に全順序集合であるばかりでなく、さらに強く整列集合になる。
  • 任意の集合 XX から全順序集合への単射 f に対し、x1 < x2f(x1) < f(x2) と置くことにより、fX 上の全順序を誘導する。
  • 適当な順序数で添字付けられた全順序集合族のデカルト積は、その上に自書式順序を入れることにより、それ自身全順序集合になる。例えば、アルファベット順に並べた任意の語の集合が全順序付けられることは、(スペースの記号をどの文字よりも小さいものとして加えた)アルファベットの集合の可算個のコピーからなる集合族のデカルト積に自書式順序を入れることで理解できる。
  • 実数全体の成す集合 R は通常の大小関係 ("<" あるいは ">") によって全順序付けられる。従ってその部分集合としての、自然数全体の成す集合 N, 整数全体の成す集合 Z, 有理数全体の成す集合 Q なども全順序集合になる。これらは何れも、ある性質に関して最小の全順序集合として(同型除いて)唯一の例を与えることが示せる(ここで、全順序集合 A がある性質に関して「最小」とは、同じ性質を持つ任意の B に対して A に順序同型な B の部分集合が存在することをいう)。
    • N上界を持たない最小の全順序集合である。
    • Z は上界も下界も持たない最小の全順序集合である。
    • QR の中で稠密となる最小の全順序集合である。ここでいう稠密性は a < b なる任意の実数 a, b に対し、a < q < b となる有理数 q が必ず存在することを言う。
    • R は順序位相(後述)に関して連結となる最小の非有界全順序集合である。
  • 順序体は定義により全順序である。これは有理数体 Q や実数体 R を包括する概念である。

関連する概念

全順序の同義語としても用いられる(さ、: chain)は、また適当な半順序集合の全順序部分集合に対しても用いられる。後者の意味での鎖はツォルンの補題で極めて重要な役割を果たす。

例えば整数全体の成す集合 Z包含関係で半順序を入れた半順序集合を考えると、自然数 n に対し、n 以下の自然数全体の成す部分集合 In からなる集合族 { In : n は自然数} はこの順序に関する鎖、すなわち包含関係に関する全順序部分集合になる。実際、nk ならば InIk の部分集合である。

全順序集合を特定の種類のとして定義することもできる。つまり、任意の a, b に対して

が成り立つものとして、ab と定義するのである。これにより、全順序集合は分配束になる。

有限全順序

単に計数を考えることにより、任意の空でない有限全順序集合が(従ってその任意の空でない部分集合が)最小元を持つことが確定する。すなわち、任意の有限全順序は整列順序である。任意の有限全順序が、通常の大小関係 < で順序付けられた自然数全体の成す集合 N の何れかの始切片英語版順序同型なることは、直接証明することもできるし、任意の整列順序が何れかの順序数に順序同型なることを見てもわかる。言い換えれば、k-元集合上の全順序は、自然数の最初の k 個からなる全順序から誘導される。従て、有限全順序または順序型 ω を持つ整列順序は、順序の観点からは自然数(0 から始まるか 1 から始まるかは問わず)で付番するのが普通である。

圏論的記述

順序を保つ写像 fab ならば f(a) ≤ f(b))をとして、全順序集合の全体は半順序集合充満部分圏になる。

このとき、二つの全順序集合の間の全単射な射はこの圏における同型射になる。

順序位相

任意の全順序集合 X に対して、開区間

(a, b) = {x : a < x かつ x < b},
(−∞, b) = {x : x < b},
(a, ∞) = {x : a < x},
(−∞, ∞) = X

などと定義することができる。これらの開区間を用いて任意の順序集合上に位相を定義することができる(順序位相英語版の項を参照)。

一つの集合上に複数の順序が定義されているとき、そのそれぞれから誘導される順序位相について考えることができる。例えば、自然数の集合 N に小なり < と大なり > の二つの全順序を考えると、< の誘導する N の順序位相も > の誘導する N の順序位相も考えられる(今の場合は両者は一致するが、一般には必ずしも一致しない)。

全順序の誘導する順序位相は、遺伝的正規であることが示せる。

完備性

全順序集合が完備 (complete) であるとは、その空でない任意の部分集合が上界を持つこと、従って上限を持つことをいう。例えば実数全体の成す集合 R は完備だが、有理数全体の成す集合 Q はそうでない。

集合 X が完備となるような順序位相の性質についての結果はいくつもある。

  • X 上の順序位相が連結ならば X は完備である。
  • X が順序位相に関して連結となる必要十分条件は、それが完備かつ X に「ギャップ」がないことである(ここで「ギャップ」は X の適当な二点 a, b (a < b) に対して a < c < b を満たす点 c が存在しないことをいう)。
  • X が完備となる必要十分条件は、その順序位相に関する任意の閉有界集合がコンパクトとなることである。

完備束を成す全順序集合はその順序位相に関してコンパクトである。実数からなる閉区間(例えば単位閉区間 [0,1] )や、拡大実数直線はそういった例である。この二つの例の間には順序を保つ同相がある。

順序の和

二つの順序 の非交和と呼ばれる自然な順序 が和集合 上に定義される。しばしばこれを順序集合の和と呼び、単に で表す。

に対し は以下の何れかひとつを満足することと定められる:
  1. かつ
  2. かつ
  3. かつ

直観的にはこれは二番目の集合の各元を一番目の集合の最大元の後ろに並べることを意味する。

より一般に、全順序付けられた添字集合 の各元 に対して全順序集合 が対応して、各集合は対ごとに交わらないものとするとき、 上の自然な全順序が

に対して であるとは、
  1. 適当な について となるか
  2. 上で なる添字について かつ となること

と置くことにより定義される。

全順序集合の直積上の順序

二つの全順序集合の直積集合上に三つの順序を入れることができる。強い順に並べると

  • 辞書式順序: (a,b) ≤ (c,d) ⇔ a < c または (a = c かつ bd). (これはまた全順序を与える)
  • 積順序: (a,b) ≤ (c,d) ⇔ ac かつ bd (これは半順序になる)..
  • 対応する狭義全順序の直積関係: (a,b) ≤ (c,d) ⇔ (a < c かつ b < d) または (a = c かつ b = d) (これも半順序).

これら三種の順序は二つより多くの直積の場合にも同様に定義することができる。

数ベクトル空間 Rn にこれらのそれぞれを適用して、順序線型空間英語版にすることができる。

Rn の部分集合上定義される実 n-変数の実函数は、その部分集合上に狭義弱順序と対応する全前順序英語版を定める。

関連する構造

反対称、推移的かつ反射的(だが必ずしも完全でない)二項関係は半順序と言う。

両立する全順序を持つ全順序群と呼ぶ。

全順序を緩めて得られる全順序性と相互に読み替えられる非自明な構造はそれほどない。向きを忘れれば媒介関係英語版が得られ、端点の位置を忘れれば巡回順序英語版が、それらの両方を忘れれば分離関係英語版が出る[3]

関連項目

注釈

  1. ^ Nederpelt, Rob (2004). “Chapter 20.2: Ordered Sets. Orderings”. Logical Reasoning: A First Course. Texts in Computing. 3 (3rd, Revised ed.). King's College Publications. p. 325. ISBN 0-9543006-7-X 
  2. ^ Nederpelt, Rob (2004). “Chapter 20.3: Ordered Sets. Linear orderings”. Logical Reasoning: A First Course. Texts in Computing. 3 (3rd, Revisied ed.). King's College Publications. p. 330. ISBN 0-9543006-7-X 
  3. ^ Macpherson, H. Dugald (2011), “A survey of homogeneous structures”, Discrete Mathematics, doi:10.1016/j.disc.2011.01.024, http://www.amsta.leeds.ac.uk/pure/staff/macpherson/homog_final2.pdf 28 April 2011閲覧。 

参考文献

  • 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