順序集合 - 曇りなき眼で見定めブログ

　当ブログは論理学とアニメを両輪とするはずが、気付けばアニメばかりになっている！アイデンティティの危機である。何故アニメばかりになったのかというと書きやすいからである。論理学記事は数式を打つのが面倒臭い。また私の専門(?)分野である証明論は証明図というのを書かねばならず、これがはてなブログだと難しい。

　そんで考えたのだが、最近は証明論に加えて代数的な意味論というのを勉強していて、これならちょっとずつでも書けそうな感じ。なのでこれをテーマにいろいろ書きたい所存。

　日本のネット上には論理学や数学基礎論の専門家はそこそこいるが、私のような非古典論理・部分構造論理の証明論・代数的意味論をやっている人間はめっちゃ少ない。まあそれはぶっちゃけブームが去っているからだが、しかし研究すべきことがなくなったというわけでもないと思う。

　とりあえず今回は最初なので基本中の基本である順序集合の定義と例でも書きまっせ。

　まず $X$ を集合とする。「関係」の定義の話までしだすとややこしいのでそこは曖昧にし、要するに $\sqsubseteq$ という記号が $X$ の任意の要素 $x, y, z$ について以下の二つを満たすとする。

反射律： $x \sqsubseteq x$
推移律： $x \sqsubseteq y$ かつ $y \sqsubseteq z$ ならば $x \sqsubseteq z$

このとき対 ${\bf X} = \langle X, \sqsubseteq \rangle$ は前順序集合であるという（このとき $\sqsubseteq$ は前順序であるという。以下でも同様に〇〇順序集合の $\sqsubseteq$ を〇〇順序という）。

　前順序集合がさらに次を満たすとする。

反対称律： $x \sqsubseteq y$ かつ $y \sqsubseteq x$ ならば $x = y$

このとき対 ${\bf X} = \langle X, \sqsubseteq \rangle$ は半順序集合または順序集合であるという。

　順序集合がさらにさらに次を満たすとする。

(有名な名前がない)： $x \sqsubseteq y$ または $y \sqsubseteq x$

このとき対 ${\bf X} = \langle X, \sqsubseteq \rangle$ は全順序集合または線形順序集合であるという。

　例を考えましょう。

　自然数をすべて集めた集合 ${\mathbb N} = \{0, 1, 2, 3, ...\}$ *1 に、普通の数の大小の関係 $\leq$ を合わせた $\langle {\mathbb N}, \leq \rangle$ は全順序集合になる（全順序集合は順序集合だし前順序集合でもある）。どの数も大小比較が可能なので四つめの法則を満たす。推移律と反対称律もよい。反射律なのだが、どの自然数も $n \leq n$ なのだが、順序を $\leq$ でなく <*2 にすると成り立たない。よって $\langle {\mathbb N},$ < $\rangle$ は全順序集合でも順序集合でも前順序集合でもない。

　順序集合の典型例はベキ集合と包含関係である。 $\langle {\mathcal P}({\mathbb N}), \subseteq \rangle$ は順序集合になる。 ${\mathcal P}({\mathbb N})$ というのはあらゆる自然数の集合を集めたものね。 $\{1, 2, 3\}$ と $\{4, 5, 6\}$ といった集合の間には包含関係がなく、全順序集合にならない。順序集合はもちろん前順序集合でもある。

　前順序集合の例として最適なのが論理的帰結関係である（唐突な例だが）。 ${\sf Form}$ をすべての論理式の集合とし、 $A \models B$ を「 $A$ が真ならば $B$ も真である」と定義すると、 $\langle {\sf Form}, \models \rangle$ は前順序集合となる。 $A \land B$ と $B \land A$ のように $A \land B \models B \land A$ 、 $B \land A \models A \land B$ と両方向に $\models$ が言える、すなわち論理的に同値だが、等しくない論理式がある。よって反対称律を満たさないのでこれは順序集合ではない。