📂集合論

部分順序集合

定義 ¹

1. 集合 $A$ での関係 $\le$ が反射的であり、推移的であり、反対称的なら、部分順序^{partial order}と言い、$(A,\le)$ を部分順序集合と呼ぶ。$A$ が部分順序集合であるというのは、全ての要素 $a,b \in A$ に対して下記を満たすことである。 $$ a \le b \land b \le a \implies a = b $$
2. 部分順序集合 $(A, \le)$ が与えられた場合、全ての $a,b \in A$ に対して $a \le b$ か $b \le a$ なら、$\le$ を $A$ の全順序^{total order}とし、$(A,\le)$ を全順序集合^{totally ordered set}という。

説明

定義では、$\le$ は単なる記号であり、必ずしも大きさを比較する不等号である必要はない。もちろん、不等号や包含関係は部分順序になれるが、逆が成立するわけではない。例えば、アルファベットで a の次は b であり、単なる記号で $a \le b$ のように示しても構わない。実際には、コンピュータ科学では a はアスキーコード $0000001_{(2)}$ に対応し、b はアスキーコード $00000010_{(2)}$ に対応し、このような2進数の大小関係で文字間の順序も表せる。

実際、全順序集合は義務教育を受けた人なら容易に思い浮かべられるもので、そうでない集合がすぐに思い浮かばないかもしれない。全順序集合の良い例は自然数の集合 $\mathbb{N}$ であり、これは整数の集合 $\mathbb{Z}$、有理数の集合 $\mathbb{Q}$、実数の集合 $\mathbb{R}$ にも同じことが言える。しかし、複素数 $\mathbb{C}$ になると、自然な順序は特に定義されていない。

全順序を定義する前に部分順序を定義するのは、その方が数学的にはるかに自然だからである。以下の五つの集合を考えてみれば、これらは自然に部分順序を持つ。 $$ A = \left\{ 1 \right\} \\ B = \left\{ 1,2 \right\} \\ C = \left\{ 1,3 \right\} \\ D = \left\{ 1,2,3 \right\} \\ E = \left\{ 1,2,4 \right\} $$ 集合の包含関係を考えると、 $$ A \subset B \subset D \\ A \subset B \subset E \\ A \subset C \subset D $$ 図で見ると、この複雑な形を一目で確認できる。 こういった非線形の形は、私たちの日常生活でもよく見かけるほど自然な関係を表している。考え直してみれば、完全に線形に積み重なる関係が奇妙に思えるかもしれない。自然数の集合 $\mathbb{N}$ でさえ、フォン・ノイマンの構成法に従えば、「直感的」とはちょっと違う。だから、全順序は単に集合全体で線形に定義される関係と言った方が理解しやすいかもしれない。