順序の公理

順序集合(X,≦)を次のように定める。

∀x,y,z∈Xに対して

x≦x（反射律）

x≦y,y≦x→x=y（反対称律）

x≦y,y≦z→x≦z（推移律）

この定義は、我々が普段実数上で考えている≦の性質とあまり変わらない。

これらの性質はとても重要であり、多くの構造で順序を入れることができる。

順序集合の例として、自然数と集合Xの冪集合P(X)の順序について考える。

自然数の順序≦は加法の定義を前提として、次のように定められるのであった。

自然数l,mに対して

l≦mとは、l=mが成り立つか、l+k=mとなる自然数kが存在することを指す。

これが順序であることを示す。l≦lは定義より当たり前。

l≦mかつm≦lが成り立つとする。l+k=m、m+k'=lとなる自然数k,k'が存在する。

ここで次の補題を示そう。

自然数の簡約補題

自然数m,a,bに対して、m+a=m+b→a=b

[証明]

mに関する数学的帰納法により示す。m=0の時自明である。m=1の時、suc(a)=suc(b)とsucの単射性よりa=b。m=kの時成り立つとする。m=k+1の時、k+1+a=k+1+b。+は可換（これは長くなるのでいずれ）であるので、1+k+a=1+k+b。m=1の時を援用すると、k+a=k+bが成り立つ。m=kの仮定より、a=bが成り立った。よってすべての自然数mでm+a=m+b→a=bは成り立つ◽︎

この補題は自然数について知っている立場からすればほとんど当たり前なことである。

l+k=m、m+k'=lが成り立っているのでm+k'+k=mが成り立つ。簡約補題により、k+k'=0が成り立つ。よって、k=k'=0が成り立ち、l=m

最後に、l≦m,m≦n→l≦nを示そう。l+k=m、m+k'=nより、l+k+k'=n。k+k'は自然数より、l≦n。

つまり、自然数には上で構成したものが順序として入ることが示せた。

例えば、1≦3は、3=1+2となるため成り立つ。

P(X)は包含⊂を順序として持つ順序集合である。具体的に考えてみよう。X={1,2}とすると、P(X)={{},{1},{2},{1,2}}である。

P(X)は⊂により順序集合をなす。{1}⊂{1,2}、{2}⊂{1,2}、{}⊂{1}、{}⊂{2}、{1}⊂{1}、{2}⊂{2}、{}⊂{}。しかし、{1}と{2}には大小関係は定まらない。できる限り、大小関係はすべての元に定まっていて欲しいものである。そこで、次のような性質を定める。

順序集合(X,≦)が全順序集合であるとは、∀x,y∈Xに対して、

x≦yまたは、y≦xが成り立つこと

全順序集合と区別するために、我々の最初に定義した集合と二項関係の組を半順序集合と言ったりもする。

全順序集合には様々な良い性質が定まる。その性質は少し様々な概念を紹介した後で証明していこう。

性質の紹介の前に次のものを紹介する。

前順序集合

(X,≦)が前順序集合とは、二項関係≦が推移律と反射律を満たすことをいう。

(X,≦)が前順序でも、擬距離と同じように順序化することができる。

(X,≦)に次のような同値関係~を導入する。

x~y⇄x≦y∧y≦x

これによって作った同値類でXを割る。これをX/~と表す。この上に次のように二項関係⊑を定義する。

x,y∈X/~に対して、[x]⊑[y]であるとは、x≦yを満たすことをいう。

これがwell-definedであることを示そう。

次に狭義順序集合を定義する。

狭義順序の公理

(X,<)が狭義順序集合であるとは、<が次の性質を満たす二項関係であるときをいう。

∀x,y,z∈X

1.¬[x<x]（非反射律）

2.x<y→¬[y<x]（非対称律）

3.x<y,y<z→x<z（推移律）

普段の順序では、x≦yでx≠yが成り立つものをx<yと書く。この性質は我々の定義した≦、<で成り立つのだろうか。

それが成り立つというのが以下の定理だ。

反射簡約と反射閉包

1.(X,<)が狭義順序集合→x≦y⇄x<y∨x=yと定義した二項関係≦について(X,≦)は順序集合。またこの≦を<の反射閉包と呼ぶ。

2.(X,≦)が順序集合→x<y⇄x≦y∧x≠yと定義した二項関係<はX上で狭義順序となる。

また、この<を≦の反射簡約と呼ぶ。

[証明]

1から示す。≦が順序の公理を満たしていることを示そう。

x≦xはx=xより自明に成り立つ。

x≦y,y≦x→x=yを示す。x≠yであるとした時、x<yとy<xが成り立っていることが定義より確認できる。しかしこれは非対称律に矛盾。よってx=y。

最後にx≦y,y≦z→x≦zを示そう。面倒なので確認作業は省くがx=y,y<z、x<y,y=z、x<y,y<z、x=y,y=zいずれの場合も、推移律は成り立つ。

2を示す。<が狭義順序であることを示そう。

¬[x<x]を示す。x=xであるので、x≦xは成り立つが、x≠xは成り立たないので、x<xではないことが示せた。

x<y→¬[y<x]を示そう。x<yであるとする。y<xも同時に成り立つとすると、x≦y、y≦xも成り立ち、x=yであることが言えるが、x<yに矛盾する。

最後にx<y,y<z→x<zを示そう。これは、自明に成り立つ。

狭義順序の場合も全順序と同じように扱いやすくなるような性質を付け加えて、新しい定義を作ることができる。それが次の公理である。

∀x,y∈Xでx<y∨x≠y∨y<xのいずれか一方が成り立つ（三分律）

これを満たす狭義順序を狭義全順序と呼ぼう。

次の定理が成り立つ。

全順序と狭義全順序の遺伝性

1.狭義全順序<の反射閉包≦は全順序

2.全順序≦の反射簡約<は狭義全順序

[証明]

1を示そう。∀x,y∈Xに対して、x≦yもしくはy≦xが成り立てば良い。x<yもしくはx=yもしくはy<xが成り立つので、反射閉包の定義より、x≦yもしくはy<xが成り立つ。

よって、x≦yもしくはy≦xが成り立つ。

2を示そう。∀x,y∈Xに対して、x≦yもしくはy≦xが成り立つ。これを分解すると、x<yもしくはx=yもしくはy<xもしくはy=xであり、x=yとy=xの同値性より示せた。

証明の途中の式を用いて、次のようなことも言える。

全順序の否定

≦がX上の全順序であるとして、その反射簡約を<とする。∀x,y∈Xに対し、

x≦y⇄¬[y<x]

[証明]

→を示す。x≦yであるので、x<y∨x=yが成り立っている。さて、x<y∨x=y∨y<xのいずれかが成り立つので、x≦yは¬[y<x]と言える。

←を示す。x,yに対してx<y∨x=y∨y<xであるので、¬[y<x]であれば、x<y∨x=yが成り立ち、x≦yが成り立つ。

さて、順序集合には次のような概念が定まる。

A⊆Xとする。

∀a∈A、a≦MとなるようなM∈XをAの上界という。

また、上界全体の集合Uに最小値が存在した場合、それは一意に定まる。この時、その値をsupAと書き、Aの最小上界、Aの上限と呼ぶ。

∀a∈A、a≦MとなるM∈AをAの最大値といい、これは一意に定まる。maxAとかく。

[∃a∈Aが存在し、x<aが成り立つ]ことがないようなx∈AをAの極大元という。

不等号を逆向きにした定義の元も存在し、それはそれぞれ、下界、最大下界（下限、infAとかく）、最小値（minAとかく）、極小元と呼ばれる。

ここで気をつけたいのは極大元と最大元の定義の違いだ。我々の普段考えている順序では、極大元と最大元は感覚的に一致している。しかし、普通の順序ではそうもいかない。イメージとして、枝分かれしている図を思い浮かべればわかりやすい。枝分かれした先の最後尾が極大元になっているのである。

具体例を出そう。({{1},{2},{1,3}},⊆)は順序集合である。これの極大元は{1,3}、{2}であるが、最大元は存在しない。なぜなら、{2}と{1,3}は比較できないからである。

このイメージの通り、極大元はいくつでも存在しえる。しかし、最大元は一つしか存在しない。（だから、Aの最大元をmaxAとかける）これを示すのが次の定理だ。

最大元の一意性

Aに最大元が存在したとすれば、それはただ一つである。

[証明]

最大元が2つ以上あるとする。それらから、二つS、Tをとる。S、TはAの元である（最大元の定義より）ので、S≦T、T≦Sの両方が成り立つ。よって、

S=T。つまり、最大元は一意である。

また、枝分かれしていなかったら、最大元と極大元は同じように思える。次の定理が成り立つ。

全順序集合(X,≦)の部分集合Aの下、

MがAの極大元⇄MがAの最大元

[証明]

定理：全順序の否定 より明らか。

さて、順序集合にも集合としては違うが似ているものが存在する。

例えば、({{1},{1,2},{1,2,3}},⊆)と({1,2,3},≦)（≦は一般的に使われるものと同じ）は、

{1}⊆{1,2}⊆{1,2,3}、1≦2≦3が成り立つ。ここで、f(1)={1}、f(2)={1,2}、f(3)={1,2,3}というように写像を構成すると、a≦b→f(a)⊆f(b)が成り立ち、f(a)⊆f(b)→a≦bが成り立つ。また、この写像は全単射である。

このような写像fを順序同型写像と呼んで、f:X→Yとなる順序同型写像が存在すれば、X≅Yとかく。

順序同型写像の性質はいくつかの性質に分解することができる。

(X,≦)、(Y, ⊑)に対して、写像f:X→Yを考える。

x≦y→f(x)⊑f(y)（fは順序を保つ）

f(x)⊑f(y)→x≦y（fは順序を反映する）

fは順序を保ち、順序を反映する（fは順序埋め込み）

順序を反映すればfは単射である。

[証明]

f(x)=f(y)とすると、f(x)⊑f(y)、f(y)⊑f(x)が成り立ち、x≦y、y≦xも成り立つ。よって、x=y◽︎

順序集合に関する基礎は実数の構成をする上で非常に重要なので是非ともよく知りたい。