順序集合

順序集合の最新ニュースをまとめて検索！

自然数同士は「こちらのほうが大きい」「小さい」という比較が可能である。あるいは、ものの大きさや重さについても比較が可能である。順序集合（じゅんじょしゅうごう、ordered set）とは、このような「大きさの比較ができる対象」の一般化・抽象化であり、順序的構造の定まっている（つまり順序の入っている）集合のことである。

いわゆる大小関係は全順序の一例であり、自然数の全体は順序集合（特に、整列集合）の一例である。

この項目では、順序（順序関係）、（半）順序集合、全順序（全体的順序, 線形順序）、全順序集合、順序同型、辞書式順序、上界・下界、極大元・極小元、最大元・最小元、上限・下限、整列集合、整列可能定理、順序位相を順に説明している。

目次

[編集] 定義

[編集] 順序集合

集合 A に、次のような条件（順序の公理と呼ばれる）を満たす二項関係 ≤ が定まっている時、対 (A, ≤) のことを順序集合 (ordered set) という。

  1. 反射律 (reflexivity): 任意の元 a について a ≤ a が成立。
  2. 推移律 (transitivity): a ≤ b かつ b ≤ c ならば a ≤ c が成立。
  3. 反対称律 (antisymmetry): a ≤ b かつ b ≤ a ならば a = b が成立。

この二項関係のことを順序関係（または順序）という。文脈によっては 1 や 3 を条件に入れないこともある。

a ≤ b を「a は b と等しいかまたは小さい」または「b は a と等しいかまたは大きい」などと読む。これは b ≥ a とも書く。a ≤ b かつ a ≠ b である時、単に a < b（または b > a）と書き、「a は b より小さい」または「b は a より大きい」と読む。

1 の反射律はあまり説明を要さない。2 の推移律はいわゆる三すくみが起こることはない、ということをいっている。3 の反対称律は等号と不等号を関係付けるものである。

[編集] 全順序集合

順序集合 (A, ≤) が更に次の条件を満たすとき、(A, ≤) のことを全順序集合 (totally ordered set) という。この順序（関係）のことを全順序（関係）あるいは全体的順序 (total order) もしくは線形順序 (linear order) という。

  • 完全律 (totalness): A の任意の元 a, b について a ≤ b か b ≤ a のどちらかが成り立つ。

これは、A の任意の元が、順序関係 ≤ によって必ず「比べられる」ということを示している。

必ずしも全順序ではない場合、特にそのことを強調して順序を半順序関係 (partial order relation)、集合を半順序集合 (partially ordered set) と呼ぶこともある。

[編集] 例

  • 都道府県を人口順に並べたものは順序集合になる。これは特に全順序集合になる。
  • 自然数全体の集合 N、整数全体の集合Z、有理数全体の集合 Q、実数全体の集合 R は普通の大小関係によって全順序集合になる。
  • 複素数は大小関係を持ってはいない。しかし次のようにして複素数全体の集合 C に全順序を定めることはできる（この順序そのものにはあまり数学的な意味はない）。
二つの複素数の実部を実数の大小関係によって比較し、実部の大きなものをより大きいと定義する。
実部が等しい場合、虚部を比較して虚部の大きなものをより大きいと定義する。
  • 同じようにして、全順序集合の直積には全順序を定義することができる。このような順序を辞書式順序という。
  • ある集合についてのそのべき集合の元の包含関係は順序関係である。これは一般には全順序ではない。
例えば {1, 2, 3} のべき集合
{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
を考えると、 {1, 2} ≤ {2, 3} も {2, 3} ≤ {1, 2} もどちらも成り立たない。

[編集] 写像と順序

写像 f: A → B は A の任意の元 a, b について

a ≤ b ならば f(a) ≤ f(b) を満たすとき順序を保つ写像といわれる。
a ≤ b ならば f(a) ≥ f(b) を満たすとき順序を逆にする写像といわれる。

実変数実数値の関数で単調増大なものは順序を保つ写像、単調減少なものは順序を逆にする写像となっていることから、順序を保つ写像と順序を逆にする写像を総称して単調写像ということがある。

順序を保つ写像 f: A → B が全単射であっても、逆写像 f -1 は順序を保つとは限らないが（ただし、A,B が全順序集合のときは f-1 は順序を保つ）、逆写像 f-1 も順序を保つとき、f は 順序同型写像あるいは単に順序同型と呼ばれる。また、A と B は順序同型であるという。

互いに順序同型な 2 つの順序集合は、見かけは異なっても順序集合としては同じものであると考えることができる。順序集合として同じであるということを、同じ順序型を持つという。すなわち、順序集合が互いに順序同型であるという関係は順序集合の全体における "同値関係" であり、これによる類別の各成分を順序型という。また、整列集合が持つ順序型を特に順序数という。

[編集] 関連する概念とその間の関係

順序集合の空でない部分集合 A について、A の任意の元 a に対して a ≤ b が成り立つような b を A の上界（じょうかい、upper bound）という。上界が存在するとき、集合 A は上に有界であるという。また、A の任意の元 a に対して b ≤ a が成り立つような b を A の下界（かかい、lower bound）という。下界が存在するとき、集合 A は下に有界であるという。上下に有界であるとき、単に有界である (bounded) という。

A のある元 s に対して、s ≤ a となる A の元 a は常に s = a となるとき、s を極大元（きょくだいげん、 maximal element）という。 また、A のある元 s に対して、a ≤ s となる A の元 a は常に s = a となるとき、s を極小元（きょくしょうげん、minimal element）という。

A のある元 m が任意の A の元 a に対して a ≤ m を満たすとき、m を A の最大元（さいだいげん、maximum element）といい、max A と書く。また、A のある元 m が任意の A の元 a に対して m ≤ a を満たすとき、m を A の最小元（さいしょうげん、minimum element）といい、min A と書く。

最大元や最小元は高々一つしかないことが、順序の公理の 3 番目（反対称律）から分かる。最大元は極大元になるが、この逆は正しくない。A はいくつもの異なる極大元を持つかもしれない。

上界の集合の最小元（つまり、最小の上界）のことを、上限（じょうげん、least upper bound, supremum）といい、sup(A) と書く。また、下界の集合の最大元（つまり、最大の下界）のことを、下限（かげん、greatest lower bound, infimum）といい、inf(A) と書く。

A が最大元 M を持てば、M は A の上限になる。また、A が最小元 m を持てば、m は A の下限になる。

[編集] 関連記事

[編集] 例

  • 自然数の間に順序 a ≤ b を a | b（a は b の約数）で定義する。集合 {a, b} の上界、下界はそれぞれ a と b の公倍数、公約数であり、上限、下限はそれぞれ最小公倍数、最大公約数である。{1, 2, ..., 10} の極大元は 6, 7, 8, 9, 10 であり、最大元は存在しない。最小元は 1 である。
  • 集合 S を S = {m | ある自然数 n が存在して m = 2n} で定義して上と同じ順序を考えると、これは全順序集合になる。写像 f: S → N を f(2n) = n で与えると、これは順序同型になる。ただし、値域の自然数の順序には普通の大小関係を考える。
  • S をある集合とし、そのべき集合 2S の間に包含関係による順序を考える。A, B を S のある部分集合とすると、{A, B} の上限、下限はそれぞれ A ∪ B、A ∩ B である。
  • ある環の自明でないイデアル全体の集合に包含関係による順序を考える。極大イデアルはこの集合の極大元である。

[編集] 整列集合と整列可能定理

順序集合は、その任意の空でない部分集合が最小元を持つとき整列集合 (well-ordered set) であるという。また、その順序を整列順序 (well-order) という。定義からすぐに「整列集合は全順序集合である」ということが分かる。実際、任意の二つの元 a, b をとってきたとき、その二つの元のなす集合 {a, b} にも最小元があるから、a ≤ b か b ≤ a のどちらかが成り立つ。これは全順序であるということに他ならない。

[編集] 整列集合の例・整列集合でない例

  • 自然数全体の集合 N は大小関係によって整列集合になる。
  • 普通の大小関係において整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R はそうではない。
  • Z は 0 < -1 < 1 < -2 < 2 < -3 < 3 < … と順序を定めると整列集合になる。
  • Q や R では（特に R では）、このような簡単な修正ではうまく行かない。

しかし、選択公理を仮定すると、次の整列可能定理 (well-ordering theorem、単に整列定理、ツェルメロの整列定理ともいう）が証明できる。

任意の集合は整列集合となるように順序を定めることができる。

逆に、整列可能定理を仮定して選択公理を証明することもできるので、整列可能定理は選択公理と同値であり、さらにはツォルンの補題などとも同値である。

[編集] 順序位相

全順序集合には次のようにして自然に位相構造が定められる。これを順序位相 (order topology) という。例えば、通常の大小関係 ≤ によって実数全体の集合 R を全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。

( A, ≤ ) を一般の全順序集合とする。A における開区間とは、{ y ∈ A | y < a } (a ∈ A) の形の集合、{ y ∈ A | y > a } (a ∈ A) の形の集合、{ y ∈ A | a < y < b } (a, b ∈ A) の形の集合、および A 自身のことをいう。x ∈ A に対して、N(x) を「x ∈ I ⊂ U を満たす開区間 I が存在するような A の部分集合 U 全体の集合」と定義する。N(x) は基本近傍系の条件を満たしているため、A に位相が定まる。これを A の順序位相という。

[編集] 関連項目

"http://wkp.fresheye.com/wikipedia/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88" より作成
フリー百科事典『ウィキペディア（Wikipedia）』 Text is available under GNU Free Documentation License.

最終更新 2009年10月19日 (月) 12:06 （日時は個人設定で未設定ならばUTC）。
【順序集合】変更履歴

ご利用上の注意

もっと調べる！

順序集合　まとめて検索