こんにちは。　今回は、集合に「大小関係」のような構造を入れる順序関係というものについて話します。

　一般的に知られている大小関係としては、自然数同士の数の大小（２よりも３のほうがでかい！とか）がありますね。
数学の例ではありませんが、「〇〇さんは××さんよりも足が速い」みたいなのも、（速いことを大きいと表現すれば）大小関係に思えますね。

　こういうのを数学の中で一般化していろいろやりたいわけです。
そこで、集合Ｘを一つ固定したときに、二つの元$${a, b \in X}$$が
「$${b}$$が$${a}$$より大きい」といえるための条件を指定して、その条件によりXに順序の構造を入れる、ということを考えましょう。

　僕の前の記事を読んでくれてたら察しがつくかもしれませんが、上で言ったような「条件」はなんでもＯＫというわけにはいきません。順序を定めるための条件なんですから、それ相応の性質は満たしてくれないと困ります。

ということで満たすべき性質を下に書き並べていきます。

１.　自分は自分自身より「大きい」

　言葉の表現が悪いせいで意味不明なことを言っているように感じてしまうかもしれませんが、数字の世界で言うところの「$${\leq}$$」を一般化したいので、これが成り立っていてほしいんですね。　
「$${\leq}$$」みたいなものが作れれば、「＜」に対応するものも作れるのでご安心を。

２．「aがb以上」と「bがa以上」が同時に満たされるのはaとbが等しい時に限る。

自分よりおおきくて、　自分より小さいものなんて自分以外にいたらたまったもんじゃありませんよね

3.　aよりbのほうが大きくて、bよりcのほうが大きいならaよりcのほうが大きい

順序と呼ばれる関係の特徴的な性質ですね。これはさすがに成り立ってほしいです。

　この３つの性質が満たされる条件なら、順序という構造を入れる最低限の性質はあると言えそうですね。　これら３つの性質を満たすもののことを順序関係といいます。
ではちゃんとした定義を下に書いておきます。

前の記事と同じで、$${\preceq \subset X^2}$$とかは無視で、
$${a \preceq b }$$のことは単に「$${b}$$は$${a}$$以上」と読み替えて問題ありません。

これで、集合X上の順序関係というものが何者かがわかりましたね。
それでは、実際に順序関係としてどんなものがあるかを見ていきましょう。

$${\fbox{注意}}$$
集合Xとその上の順序関係を一つ自由にとって来た時、
現実で使われる順序関係の多くで成り立つ性質「任意の二つの元a, bに対し、「bはa以上」または「aはb以上」のどちらか一方は必ず成り立つ」
が満たされるとは限りません。

そこで、この性質を追加で要請し、これを満たす順序関係のことを
全順序（関係）と呼ぶことにします。また、全順序でない順序関係のことを、それを強調する場合半順序と呼ばれたりします。

順序関係、順序集合の例

・半順序集合の例

 $${\mathbb{N}}$$を自然数全体の集合とし、順序関係”｜”を、

$${n | m :\Leftrightarrow mはnの倍数　\hspace{3mm}(n, m \in \mathbb{N})}$$

としてみると、"|"は$${\mathbb{N}}$$上の順序関係になります。
（証明は素直にやれば簡単だからやってみてね）
また、この順序関係は半順序です。　実際、2, 3$${\in \mathbb{N}}$$ はお互いに他方の倍数ではありません。

他の例として、Sを2つ以上の要素をもつ集合として、
X:=P(S) = $${\{ J | J \subset S\}}$$とし, X上の順序関係を包含関係で定めましょう。つまり、$${I, J \in P(S)}$$に対し$${I \subset J :\Leftrightarrow  {}^\forall i \in I, \hspace{2mm}  i \in J}$$とすると、これも順序関係になります。（これも簡単だよ）
しかも、この順序はやはり半順序です。　　実際Sの互いに異なる元$${a, b}$$をとると、$${\{a\}, \{b\} \in P(S)}$$で、互いに包含関係はありません。

・全順序集合の例

上と同じ$${\mathbb{N}}$$に対し、数に関する通常の大小関係は順序関係になります。（証明をするのは面倒なので飛ばします。気が向いたら別の記事でやるかも）
また、直観的にはアタリマエですが、これは全順序になりますね。（同じく証明略）

これは写像の全単射の概念と同値関係を知っている人にしか伝わらない例ですが置いときます。（写像の話も同値関係の話も僕の記事にあるのでよかったらみてってね）

Sを集合とし、P(S)をべき集合（上で使ったP(S)と同じ意味）とします。
P(S)上の同値関係$${\sim}$$を次で定めます。

$${A \sim B :\Leftrightarrow  {}^\exists f : A \rightarrow B \hspace{2mm}s.t. \hspace{2mm} fは全単射   (A, B \in P(S))}$$

これが同値関係になってることの証明はそんなに難しくないので気になる人はやってみてください。

ここで、Xを上の同値関係による商集合$${P(S)/\sim}$$とします。
X上の順序関係"$${\preceq}$$"を、$${\mu, \nu \in P(S)/\sim}$$に対し

$${\mu \preceq \nu :\Leftrightarrow {}^\exists A \in \mu, {}^\exists B \in \nu , {}^\exists g: A \rightarrow B \hspace{1mm}s.t.\hspace{1mm}  gは単射}$$

と定義すると、これは順序関係となります。

証明

一つ目：
$${\mu \in X}$$を任意にとる。商集合の定義から、
$${{}^\exists A \in P(S) ,  \mu = [A]}$$が成り立つ。
もちろん$${A \in \mu }$$であり、恒等写像は単射だから結局
$${\mu \preceq \mu}$$が成り立つ。

２つ目：
$${\mu \in X, \nu \in X}$$を任意にとる。
$${\mu \preceq \nu \cdots (1)かつ \nu \preceq \mu \cdots(2)}$$が成り立つと仮定すると、
(1)より
$${{}^\exists A_1 \in \mu, {}^\exists B_1 \in \nu , {}^\exists g_1: A_1 \rightarrow B_1 \hspace{1mm}s.t.\hspace{1mm}  g_1は単射}$$
(2)より
$${{}^\exists B_2 \in \nu, {}^\exists A_2 \in \mu , {}^\exists g_2: B_2 \rightarrow A_2 \hspace{1mm}s.t.\hspace{1mm}  g_2は単射}$$
がともに成り立つ。

この時、$${A_1, A_2 \in \mu}$$より$${A_1 \sim A_2, つまり　全単射F:A_2 \rightarrow A_1}$$が存在する。
同様に$${B_1, B_2 \in \nu}$$より$${B_1 \sim B_2, つまり　全単射H:B_1 \rightarrow B_2}$$が存在する。
ここで、$${F \circ  g_2 \circ H : B_1 \rightarrow A_1}$$を考えると、これは単射である。（$${\because 単射の合成}$$）

よって、$${A_1とB_1}$$は、両方向から単射が存在する。
ベルンシュタインの定理より、$${A_1 \sim B_1}$$を得る。
よって、$${\mu = [A_1]= [B_1] = \nu}$$

3つ目：
$${\mu, \nu, \xi \in X}$$が、$${\mu \preceq \nu,   \nu \preceq \xi}$$を満たしているとする。
このとき、
$${{}^\exists A \in \mu, {}^\exists B_1 \in \nu \hspace{2mm} s.t. \hspace{2mm} {}^\exists g: A \rightarrow B_1; 単射}$$
$${{}^\exists B_2 \in \nu, {}^\exists C \in \xi \hspace{2mm} s.t. \hspace{2mm} {}^\exists h: B_2 \rightarrow C; 単射}$$
の２つが成り立つ。

さらに、$${B_1, B_2 \in \nu}$$より、$${{}^\exists F : B_1 \rightarrow B_2;全単射}$$が成り立つ。
このとき、$${h \circ F \circ g :A \rightarrow C}$$は単射。（$${\because 単射の合成}$$）
これで、$${A \in \mu}$$から$${C \in \xi}$$への単射が得られたので、
$${\mu \preceq \xi}$$が得られる。　

さらに、証明はしませんが、この順序集合は全順序です。
順序関係の話を進めて、整列可能定理と比較定理を認めれば、任意の二つの集合の濃度の大小は一意に定まり、それを用いて証明できます。

順序集合の例はもう十分出したと思うので、自然に定まる概念をいくつか定義していきましょう。

「等号なしの不等号」の定義

これは普段使ってる意味と同じように定義すればいいですね。

全順序がはいった順序集合に限っては、
$${x \prec y }$$　であることと　$${y \preceq x}$$でない　ことが必要十分になります。これも普段使ってる順序の感覚と合致しますね。
証明は対偶をとれば簡単です。やってみてね

最大元、最小元の定義

わざわざ順序を考えるんですから、やっぱり一番でかいやつとか、一番ちっこいやつも考えたいですよね。ということでこれも自然に定義しましょう。

すごく自然な定義ですね。
与えられた部分集合に対し、その中で一番大きいやつを最大元って呼ぶわけですね。（最小元も同じ感じ）
もちろん、その部分集合によっては最大元、最小元が存在するとは限りません。（整数の集合$${\mathbb{Z}}$$に数の大小を入れ、A=$${\mathbb{Z}}$$としたり）

しかし、もしAに最大元が存在すれば、簡単な証明により
Aの最大元となるものは一つしかないとわかります。

最大元を最小元に取り換えても同じことが言えます。

極大元、極小元の定義

上で言ったように、最大元、最小限は存在するとは限りません。
それに、一般に順序集合の部分集合が与えられたときに、それが最大元をもつ、または最小元を持つ、というのは割と強い（厳しい）条件だと僕は思うんですよね。
そこで、これらより少し条件を緩めた、極大元、極小元というものを考えましょう。
数学やるときは、最大元、最小元がなくても、極大元、極小元があれば十分なことも割とあるし、zornの補題とかいう便利な定理もあり（ただし選択公理ウェルカム派に限る）、極大元、極小元の存在はちょっとだけ示しやすいので、こういうやつを考えとくと便利なんですよね。

下に定義を書きます。

一応確認しておくと、Xの部分集合Aに最大元が存在したなら、それは極大元になります。順序関係に要請されている性質だけ使えば１、２行で証明できます。下の証明で一緒にやりますね。

また、極大元、極小元は最大元、最小元より弱い条件として紹介しましたが、全順序集合に限った話をすれば、これはそれぞれ同値な条件です。
では証明しましょう。最大元、極大元の同値性について示します。

$${\fbox{証明}}$$
$${(X, \preceq)}$$を全順序集合, $${A \subset X}$$とする。

・（最大元 $${\Rightarrow}$$極大元）

$$
\left ( \begin{array}{}注：こっちは全順序であるという仮定は使いません。\\
一般の順序集合でも全く同じ議論で証明できます。\end{array} \right)
$$

$${a \in A}$$が$${A}$$の最大元であると仮定する。
このとき、$${b \in A}$$が$${a \preceq b}$$を満たしているとすると、
仮定より$${b \preceq a}$$が成り立ち、$${a=b}$$を得る。

・(極大元$${\Rightarrow}$$最大元 )
$${a \in A}$$が極大元であると仮定する。
このとき、任意の$${x \in X}$$に対し、$${(X, \preceq)}$$の全順序性から
$${x \preceq a,  \hspace{2mm}a \preceq x }$$のいずれかが成り立つ。
$${x \preceq a}$$の時はOK.
$${a \preceq x}$$の時、$${a}$$が極大元であるから$${x=a}$$となる。
$${\therefore x \preceq a}$$

ということで、全順序集合については、極大、極小という（見かけ上）弱い条件が達成されれば、自動的に最大、最小の条件も達成されることがわかりました。
まあ、極大元とかを考えるのは学部レベルの勉強してる今のところでは半順序のやつばっかりで、全順序のやつに対してはあんまり考えてないんですけどね。

最後に、上のほうでちょろっと言ったzornの補題を紹介して終わります。
順序集合の概念を考えてうれしい事の内７割ぐらいはzornの補題が占めているといっても過言ではないと思いますね。

なんやこれって言われそうですね。まずは$${X}$$が空でない有限集合の場合について考えましょう。

今、やりたいことは、$${X}$$の中で、極大元、つまり「これ以上大きくできないような元」を見つけることです。
今回は、$${X}$$は有限集合なので、パソコンでも使って見つけることができそうです。どうすればいいでしょうか？

これはゴリ押し戦法で何とかなりそうですね。まず好きに$${X}$$の元$${a_0}$$をとりましょう。$${a_0}$$より大きいやつが取れたならそのおおきいやつを$${a_1}$$とし、$${a_1}$$がまだ大きくできるならその大きくしたやつを$${a_2}$$にして・・・
と繰り返せば、有限集合$${X}$$についてはいつかこの手続きは終了し、極大元が手に入りました。

では無限集合ではどうでしょうか？さっきと同じような方法でどんどん大きい元をとっていけば、いつか必ず極大元が手に入るでしょうか？
・・なんか無理そうですよね。
$${\mathbb{N} \cup \{+\infty\}}$$に自然に順序を入れたものとか、定理の仮定を満たすし、実際極大元（なんなら最大元）が存在するけど、これに対してさっきの手続きをしても、場合によっては有限回では極大元がいつまでたっても得られないことがありますよね。（例えば、$${a_0 = 0, a_1=1,  a_2=2 \cdots}$$とか）

そこで、zornの補題の主張を（語弊大歓迎で）述べると、
この手続きを有限回で止めなくていいよ、「可算無限」回繰り返してもいいし、「非可算」回（実数の濃度に対応するぐらいたくさん）でもいいし、
なんなら$${X}$$の濃度と同じぐらいたくさん手続きを繰り返してもいいよ。そしたら極大元が手に入るよ！
となります。

手続きのやり方をみると、回数を増やすごとに$${X}$$の元を「選ぶ」という操作が入っていますね。一回一回の操作において、元を一つ選ぶことは補題の仮定が満たされていれば可能になりますが、人間は本来有限個のものしか選びきれないはずですよね。　
だから「非可算」とか、人間感覚でバカみたいにでかい濃度と同じぐらい大量のものを選び取るためには、選択公理という名のチートを使わないといけないみたいです。

今回は、現実世界にもある概念である「順序」の数学バージョンを紹介しました。zornの補題は選択公理を使っているだけあってすごく強力な定理で、代数学でもベクトル空間の基底の存在を保証したり、代数閉包の同型を除く一意性を示したりするのに使われます。
また、実数体は、その順序もまとめて一緒に定義されるので、実数を作るときにも順序は関係してきます。
なんかグダグダ話してましたが、この辺で終わりにしときます。
ここまで読んでくれた方、ありがとうございました。