無限長の配列はソート可能か?

皆さんご存知の通り、有限サイズの任意の配列は、有限回の比較と交換でソートすることができます。 (挿入ソートやクイックソートなどの具体的なアルゴリズムが存在することが、その証明になっています)

では、配列が無限の長さを持っていた場合はどうなるでしょうか?

Twitter で考えたことをまとめます。

ソート可能性

ソートとは、配列の各要素が演算子  \leq 比較可能なときに、 各要素が「下から何番目か」という番号を振ることであると考えられます。

そこで、有限配列のソート可能性を次のように定義します。

定義: 有限集合のソート可能性

有限な順序集合 (X, \leq) について、 任意の全単射  \phi: X \rightarrow \{1, \cdots, | X | \} に対して 次の2つを満たす全単射 \psi: \{1, \cdots, | X | \} \rightarrow \{1, \cdots, | X | \}が存在するとき、 Xソート可能であるという。

  1.  x \leq y \Leftrightarrow \psi(\phi(x)) \leq \psi(\phi(y))
  2.  \psi は有限個の互換の合成で表される。

上の定義で、 \phi はソート前の配列を表し ( x \in X \phi(x)番目の要素)、  \psi がソートによって「n番目の要素が \psi(n) 番目に移動する」ことを表しています。

ここで、1つ目の条件は、 X\{1, \cdots, | X | \} が順序同型であるということを意味します。 要素数が等しい任意の有限集合は順序同型ですから、これは常に成り立ちます。

また、2つ目の条件についても、任意の有限置換は互換の積で表されますから、こちらも常に成り立ちます。

これらのことから、任意の有限集合はソート可能であることが確認できました。

(この定義のみからでは、有限回の比較回数で \psi を構成可能であるかどうかについては触れていないのでご注意ください。このあたりの精緻な議論は私の手に余ります。。。)

それでは、ソート可能性の概念を無限長の配列に拡張しましょう。

定義: 可算無限集合のソート可能性

可算な順序集合 (X, \leq) について、 任意の全単射  \phi: X \rightarrow \mathbb{N} に対して 次の2つを満たす全単射 \psi: \mathbb{N} \rightarrow \mathbb{N}が存在するとき、 Xソート可能であるという。

  1.  x \leq y \Leftrightarrow \psi(\phi(x)) \leq \psi(\phi(y))
  2.  \psi は可算個の互換の合成で表される。

はい、有限を可算無限にしただけですね。 しかし、一般に可算無限集合に対しては、ソート可能性は成り立ちません。

たとえば、可算無限個の要素からなる配列

 \displaystyle
X = \left( \frac{(-1)^{i}}{i} \right) = \left(-1, \frac{1}{2}, -\frac{1}{3}, \frac{1}{4}, \cdots \right)

を通常の意味の大小関係でソートする場合を考えましょう。

f:id:nunuki:20161120004037p:plain

もし、 X がソート可能であると仮定すると、  X の最小・最大の要素  -1, \frac{1}{2} のソート後の順番がそれぞれ m,n と求まります。

すると、  X の要素数 n-m+1 個となってしまいますが、 これは、 X が無限集合であることと矛盾します。 よって、 X はソート不可能であることがわかりました。

これは、 条件1の「可算無限集合 X自然数全体の集合 \mathbb{N} と順序同型である」 が一般には成立しないことを反映しています。

逆に言えば、 X がソート可能であるためには、 X \mathbb{N} と順序同型であることが必要です。

このための必要条件として、

  •  X は最小値を持つ
  •  X は最大値を持たない
  •  X の任意の2要素  a \leq b について、  Xの部分集合 \{ x\in X | a \leq x \leq b \} は有限集合である

などが挙げられますが、他にもいろいろと条件がありそうです。

この議論を進めていくと、整列順序など、数学の基礎的な概念の話になってくるようですが、こちらはまだまだ勉強不足です。