辞書式順序とは

辞書式順序（レキシコグラフィカル順序）は、複数の要素からなる組（タプル）を比較する際に用いられる順序の一種です。これは、国語辞典で単語が並んでいる順番と同様の考え方に基づいています。最初の要素から順に比較し、最初に異なる要素の大小関係で全体の順序を決定します。この方法は、文字列や数列、集合の直積など、さまざまな場面で利用されます。

有限個の要素からなる組の辞書式順序

まず、有限個の要素からなる組に対する辞書式順序の定義を紹介します。

集合 \( A_1, A_2, \ldots, A_n \) がそれぞれ順序関係 \( \le \) を持つとします。これらの直積集合 \( A = A_1 \times A_2 \times \cdots \times A_n \) 上で、要素 \( (a_1, a_2, \ldots, a_n) \) と \( (b_1, b_2, \ldots, b_n) \) の順序を以下のように定めます。

\[ (a_1, a_2, \ldots, a_n) < (b_1, b_2, \ldots, b_n) \] は、ある \( k \) が存在して、次の条件を満たすときに成り立ちます。

• \( a_i = b_i \) for all \( i < k \)
• \( a_k < b_k \)

この定義により、直積集合 \( A \) 上に順序が導入されます。

例1: 整数の5次元ベクトル

整数全体の集合 \( \mathbb{Z} \) に通常の大小関係を持たせ、5つの直積 \( \mathbb{Z}^5 \) 上で辞書式順序を考えます。以下の順序関係が成り立ちます。

\[ (0, 9, 9, 7, 0) < (1, 4, 1, 0, 5) < (1, 4, 1, 2, 0) \]

これは、各ベクトルの左から順に要素を比較し、最初に異なる要素の大小で順序を決定しているためです。

例2: 部分集合の直積

集合 \( X = \{x, y\} \) の部分集合全体の集合（べき集合） \( 2^X = \{\emptyset, \{x\}, \{y\}, \{x, y\}\} \) を考えます。包含関係 \( \subseteq \) による順序を用いて、直積 \( 2^X \times 2^X \) 上で辞書式順序を定めると、以下のような順序関係が得られます。

\[ (\{x\}, \{y\}) \le (\{x, y\}, \emptyset) \le (\{x, y\}, \{y\}) \]

ただし、\( (\{x\}, \{x\}) \) と \( (\{x\}, \{y\}) \) の間には順序が定まりません。これは、包含関係が半順序であり、全ての要素間で比較可能ではないためです。

無限個の要素からなる組の辞書式順序

次に、無限個の要素からなる組に対する辞書式順序の定義を紹介します。

整列集合 \( I \) を添え字集合とし、各 \( i \in I \) に対して順序集合 \( (A_i, \le) \) が定まっているとします。直積集合 \( A = \prod_{i \in I} A_i \) 上で、要素 \( (a_i) \) と \( (b_i) \) の順序を以下のように定めます。

\[ (a_i) < (b_i) \iff a_j < b_j \quad \text{where } j = \min \{ i \in I \mid a_i \ne b_i \} \]

すなわち、最初に異なる添え字 \( j \) において、\( a_j < b_j \) であれば、\( (a_i) < (b_i) \) と定めます。

例3: 2進数列の集合

集合 \( A = \{0, 1\}^\mathbb{N} \) を考えます。これは、無限列 \( (a_1, a_2, a_3, \ldots) \) で、各 \( a_i \in \{0, 1\} \) となるもの全体の集合です。この集合上で辞書式順序を定めます。

部分集合 \( B \subset A \) を、1が1つだけ現れる列全体とします。すなわち、

\[ B = \{ (a_i) \in A \mid \exists! i \in \mathbb{N}, a_i = 1 \} \]

このとき、\( B \) には最小元が存在しません。例えば、以下のような順序が成り立ちます。

\[ (1, 0, 0, \ldots) > (0, 1, 0, \ldots) > (0, 0, 1, \ldots) > \cdots \]

このように、無限個の要素からなる直積集合上の辞書式順序では、整列集合にならない場合があります。

整列集合と辞書式順序

整列集合とは、全順序集合であり、かつ任意の空でない部分集合が最小元を持つ集合のことです。有限個の整列集合の直積に辞書式順序を導入すると、その直積集合も整列集合になります。しかし、無限個の整列集合の直積では、辞書式順序を導入しても整列集合にならない場合があります。