辞書式順序のソースを表示

{{otheruseslist|数学|[[英英辞典]]・[[英和辞典]]など[[英語]]でひく[[辞典]]・[[事典]]|アルファベット順|[[国語辞典]]・[[和英辞典]]など[[日本語]]でひくもの|五十音順|[[漢和辞典]]|画数}}
{{Expand English|Lexicographic order|date=2024年5月}}
[[数学]]における'''辞書式順序'''（じしょしきじゅんじょ、{{lang-en-short|lexicographical order. lexicographic-, dictionary-}}）とはいくつかの[[順序集合]]の[[直積集合]]上に順序を定める方法の一つである。順序集合 {{mvar|A}} と {{mvar|B}} が与えられた際の直積集合 {{math|''A'' × ''B''}} 上の辞書式順序は

:<math>\{(a, b) \le (a', b') \mid (a < a') \cup (a = a' \cap b \le b') \}</math>

として定められる。辞書式順序という名前は、この順序の定め方が[[辞書]]における項目の並べ方を一般化したものと見なせることに由来する。つまり、単語（[[文字]]の並び）{{math|''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub>}} が別の単語 {{math|''b''<sub>1</sub>''b''<sub>2</sub>...''b''<sub>''k''</sub>}} の前に現れるのは {{math|''a''<sub>''i''</sub>}} が {{math|''b''<sub>''i''</sub>}} と異なるような最初の {{mvar|i}} について、文字の順番の中で {{math|''a''<sub>''i''</sub>}} が {{math|''b''<sub>''i''</sub>}} より前に現れる場合である。このとき2つの単語は同じ長さ（文字数）であるものと仮定されているが、実際の辞書では普通短い単語の方を後ろにどんな文字よりも先の順番にある空白を付け加えることで単語の長さが揃っているものとして考える、という操作が行われる。

== 概要 ==
[[順序集合|整列順序]]の入った[[添字記法|添字]]集合 {{mvar|I}} で添字づけられた[[順序集合#全順序集合|全順序集合]]<!-- to omit this totality assumption, modify below to j = min(i|ai < bi or ai > bi) -->の[[族 (数学)|族]] {{math|(''A''<sub>''i''</sub>)<sub>''i'' &isin; ''I''</sub>}} が与えられたとする。このとき、[[直積集合]] {{math|&prod;<sub>''i'' &isin; ''I''</sub> ''A''<sub>''i''</sub>}} 上に以下のようにして定められる順序は {{math|&prod;<sub>''i'' &isin; ''I''</sub> ''A''<sub>''i''</sub>}} 上の辞書式順序と呼ばれる：

:<math>(a_i)_i < (b_i)_i \iff a_j < b_j \quad (j = \min \left\{ i \in I \mid a_i \ne b_i \right\}).</math>

上の定義は {{mvar|I}} が特に[[有限集合]] {{math|{{mset|1, ... , ''n''}}}} の場合にも適用できる。その場合には次のように言いかえることができる。すなわち {{math|''A''<sub>1</sub>, ... , ''A''<sub>''n''</sub>}} を全順序集合とするとき、直積集合 {{math|''A''<sub>1</sub> × … × ''A''<sub>''n''</sub>}} 上の辞書式順序とは次のようになる：
{{math|1=''a'' = (''a''<sub>1</sub>, ... , ''a''<sub>''n''</sub>)}} と {{math|1=''b'' = (''b''<sub>1</sub>, ... , ''b''<sub>''n''</sub>)}} を {{math|''A''<sub>1</sub> × … × ''A''<sub>''n''</sub>}} の元とする。
#「先頭の文字」{{math|''a''<sub>1</sub>}} と {{math|''b''<sub>1</sub>}} が異なり、{{math|''a''<sub>1</sub> &lt; ''b''<sub>1</sub>}} ならば {{math|''a'' &lt; ''b''}}、
# 反対に {{math|''a''<sub>1</sub> &gt; ''b''<sub>1</sub>}} ならば {{math|''a'' &gt; ''b''}} とし、
# {{math|1=''a''<sub>1</sub> = ''b''<sub>1</sub>}} だったならば {{math|''a''<sub>2</sub>}} と {{math|''b''<sub>2</sub>}} を同様に比べる、
という操作を繰り返して {{mvar|a}} と {{mvar|b}} の間の大小関係が決定される。

辞書式順序の重要な性質に整列性を保つというものがある。つまり、順序集合 {{mvar|A}} と {{mvar|B}} が整列順序集合ならば辞書式順序をいれた直積集合も整列順序集合になる。<!-- rephrase this in the family (Ai) setting -->

== 辞書式順序の応用 ==
=== 単項式に対する順序 ===
{{main|単項式順序}}
多変数の[[多項式]]の集合の中での[[単項式]]の集合は各変数に関する単項式集合たちの直積集合と見なすことができる。したがってこの単項式の集合上にそれぞれの変数の単項式に関する順序をもとにした辞書式順序を考えることができる。

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

{{DEFAULTSORT:ししよしきしゆんしよ}}
[[Category:順序構造]]
[[Category:辞書学]]
[[Category:組合せ論]]
[[Category:数学に関する記事]]