|
数学における辞書式順序（じしょしきじゅんじょ、lexicographical / lexicographic / dictionary order）とはいくつかの順序集合の直積集合上に順序を定める方法の一つである。順序集合 ''A'' と ''B'' が与えられた際の直積集合 ''A'' × ''B'' 上の辞書式順序は : として定められる。辞書式順序という名前は、この順序の定め方が辞書における項目の並べ方を一般化したものと見なせることからきている。つまり、単語（文字の並び）''a''1''a''2...''a''''k'' が別の単語 ''b''1''b''2...''b''''k'' の前に現れるのは ''a''''i'' が ''b''''i'' と異なるような最初の ''i'' について、文字の順番の中で ''a''''i'' が ''b''''i'' より前に現れるときである。このとき二つの単語は同じ長さ（文字数）であるものと仮定されているが、実際の辞書では普通短い単語の方を後ろにどんな文字よりも先の順番にある空白を付け加えることで単語の長さがそろっているものとして考える、という操作が行われる。 == 概要 == 整列順序の入った添字集合 ''I'' で添字づけられた全順序集合の族 (''A''''i'')''i'' ∈ ''I'' が与えられたとする。このとき、直積集合 ∏''i'' ∈ ''I'' ''A''''i'' 上に以下のようにして定められる順序は ∏''i'' ∈ ''I'' ''A''''i'' 上の辞書式順序とよばれる： : (''a''''i'')''i'' < (''b''''i'')''i'' ⇔ ''a''''j'' < ''b''''j'' ( ''j'' = min ) 上の定義は ''I'' が特に有限集合 の場合にも適用でき。その場合には次のように言いかえることができる。すなわち ''A''1, ... , ''A''''n'' を全順序集合とするとき、直積集合 ''A''1 × … × ''A''''n'' 上の辞書式順序とは次のようになる：''a'' = (''a''1, ... , ''a''''n'') と ''b'' = (''b''1, ... , ''b''''n'') を ''A''1 × … × ''A''''n'' の元とする。「先頭の文字」''a''1 と ''b''1 が異なり、''a''1 < ''b''1 ならば ''a'' < ''b''、反対に ''a''1 > ''b''1 ならば ''a'' > ''b'' とし、''a''1 = ''b''1 だったならば ''a''2 と ''b''2 を同様に比べるという操作を繰り返して ''a'' と ''b'' の間の大小関係が決定される。 辞書式順序の重要な性質に整列性を保つというものがある。つまり、順序集合 ''A'' と ''B'' が整列順序集合ならば辞書式順序をいれた直積集合も整列順序集合になる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「辞書式順序」の詳細全文を読む スポンサード リンク
|