10.8 線形順序

実数の大小関係は、これまでに触れてこなかった重要な性質を持つ: 任意の異なる二つの実数が与えられると、一方がもう一方より必ず大きい。この性質を持つ半順序を線形順序 (linear order) と呼ぶ。線形順序は「全ての要素を順序通りに一列に並べられる」順序と考えることができる1。

定義 10.8.1

\(R\) を集合 \(A\) 上の二項関係とする。\(A\) の要素 \(a\), \(b\) が \(R\) において比較可能 (comparable) とは、\(a \mathrel{R} b\) または \(b \mathrel{R} a\) が成り立つことを言う。任意の二要素が比較可能な半順序を線形順序 (linear order) と呼ぶ。

例えば \(\mathbb{R}\) 上の \(<\) と \(\leq\) は線形順序である。一方で集合の包含関係は線形順序でない: 同じ個数の要素を持つ異なる二集合は \(\subseteq\) において比較可能でない。また、図 \(\text{10.6}\) に示した科目の依存関係では 8.01 と 6.042 がいずれも相手の必須科目でないので、これも線形順序でない。

  1. 線形順序は全順序 (total order) とも呼ばれる。しかし、この呼び方だと [英語では] 二項関係の性質である全域 (total) と単語が衝突する。これが原因で両者を混同している学生を定期的に見かける。

    線形順序であることは全域関係であることより強い条件である。例えば任意の弱半順序は全域関係であるものの、一般に線形順序とは限らない。 ↩︎

広告