全順序とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 全順序の意味・解説 

全順序

(線型順序 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/07/01 08:59 UTC 版)

数学における全順序(ぜんじゅんじょ、: total order)とは、集合での二項関係で、推移律反対称律かつ完全律の全てを満たすもののことである。

単純順序(たんじゅんじゅんじょ、: simple order)、線型順序(せんけいじゅんじょ、: linear order)とも呼ばれる。

集合と全順序を組にしたものは、全順序集合 (totally ordered set), 線型順序集合 (linearly ordered set), 単純順序集合 (simply ordered set) あるいは (chain) と呼ばれる。

即ち、集合 X 上の関係 が全順序であるとは、が、X の任意の元 a, b, c に対して、次の4条件を満たすことである:

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

反対称性によって a < b かつ b < a であるという不確定な状態は排除される[2]。完全性を持つ関係は、その集合の任意の二元がその関係で比較可能英語版であることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である[3]。また完全性から反射性 (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 でない

でできる。

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

  • 通常のアルファベット順A < B < C)はアルファベット全体の成す集合を全順序付ける。
  • 全順序集合の任意の部分集合は、もとの全体集合の順序をその部分集合に制限することで、全順序付けられる。
  • 順序数からなる任意の集合、あるいは基数からなる任意の集合。これらは単に全順序集合であるばかりでなく、さらに強く整列集合になる。
  • 集合 X に対して、X から全順序集合への単射写像 f が存在するとき、x1 < x2f(x1) < f(x2)X での順序を定めると、X は全順序集合になる。
  • 適当な順序数で添字付けられた全順序集合族のデカルト積は、その上に辞書式順序を入れることにより、それ自身全順序集合になる。例えば、アルファベット順に並べた任意の語の集合が全順序付けられることは、(スペースの記号をどの文字よりも小さいものとして加えた)アルファベットの集合の可算個のコピーからなる集合族のデカルト積に辞書式順序を入れることで理解できる。
  • 実数全体の成す集合 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 に対して

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



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「全順序」の関連用語

全順序のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



全順序のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの全順序 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS