辞書式順序

テンプレート:Otheruseslist テンプレート:Expand English 数学における辞書式順序（じしょしきじゅんじょ、テンプレート:Lang-en-short）とはいくつかの順序集合の直積集合上に順序を定める方法の一つである。順序集合 テンプレート:Mvar と テンプレート:Mvar が与えられた際の直積集合 テンプレート:Math 上の辞書式順序は

$\{(a,b)\le (a^{\prime },b^{\prime })\mid (a<a^{\prime })\cup (a=a^{\prime }\cap b\le b^{\prime })\}$

として定められる。辞書式順序という名前は、この順序の定め方が辞書における項目の並べ方を一般化したものと見なせることに由来する。つまり、単語（文字の並び）テンプレート:Math が別の単語 テンプレート:Math の前に現れるのは テンプレート:Math が テンプレート:Math と異なるような最初の テンプレート:Mvar について、文字の順番の中で テンプレート:Math が テンプレート:Math より前に現れる場合である。このとき2つの単語は同じ長さ（文字数）であるものと仮定されているが、実際の辞書では普通短い単語の方を後ろにどんな文字よりも先の順番にある空白を付け加えることで単語の長さが揃っているものとして考える、という操作が行われる。

概要

整列順序の入った添字集合 テンプレート:Mvar で添字づけられた全順序集合の族 テンプレート:Math が与えられたとする。このとき、直積集合 テンプレート:Math 上に以下のようにして定められる順序は テンプレート:Math 上の辞書式順序と呼ばれる：

$(a_i{)}_i<(b_i{)}_i⟺a_j<b_j(j=\min \{i\in I\mid a_i\ne b_i\}).$

上の定義は テンプレート:Mvar が特に有限集合 テンプレート:Math の場合にも適用できる。その場合には次のように言いかえることができる。すなわち テンプレート:Math を全順序集合とするとき、直積集合 テンプレート:Math 上の辞書式順序とは次のようになる： テンプレート:Math と テンプレート:Math を テンプレート:Math の元とする。

1. 「先頭の文字」テンプレート:Math と テンプレート:Math が異なり、テンプレート:Math ならば テンプレート:Math、
2. 反対に テンプレート:Math ならば テンプレート:Math とし、
3. テンプレート:Math だったならば テンプレート:Math と テンプレート:Math を同様に比べる、

という操作を繰り返して テンプレート:Mvar と テンプレート:Mvar の間の大小関係が決定される。

辞書式順序の重要な性質に整列性を保つというものがある。つまり、順序集合 テンプレート:Mvar と テンプレート:Mvar が整列順序集合ならば辞書式順序をいれた直積集合も整列順序集合になる。

辞書式順序の応用

単項式に対する順序

テンプレート:Main 多変数の多項式の集合の中での単項式の集合は各変数に関する単項式集合たちの直積集合と見なすことができる。したがってこの単項式の集合上にそれぞれの変数の単項式に関する順序をもとにした辞書式順序を考えることができる。

社会での応用

辞書式順序の実社会における応用として日付の書式に関するISO 8601規格が挙げられる。この規格では日付は YYYYMMDD（Yは年、Mは月、Dは日を表す）という書式によって表され、単純に文字の並びとして並べ替えるだけの整列アルゴリズムで時系列順の並べ替えが得られる。ここで、このアルゴリズムが機能するためには年は4つの数字で表され、月や日は2つの数字で表されていなければならないので、たとえば数字1つの日付には0を付け足して '01' などと表すことになる。