辞書式順序

$x\neq y$ について、$x_i\neq y_i$ となる $i$ 全体は正の整数の空でない部分集合なので最小元をもち（数学的帰納法 の記事の定理「自然数の整列原理」）、それを $d(x,y)$ と書く。$d(x,y)=d(y,x)$ である。
反射律は定義から成り立つ。
反対称律：$x\leq_{\mathrm{lex}}y$ かつ $y\leq_{\mathrm{lex}}x$ で $x\neq y$ とすると、$k=d(x,y)$ で $x_k<_k y_k$ かつ $y_k<_k x_k$ となり、$\leq_k$ の反対称律に反する。よって $x=y$ である。
推移律：$x<_{\mathrm{lex}}y$ かつ $y<_{\mathrm{lex}}z$ とし、$k=d(x,y)$、$l=d(y,z)$ とおく。$j:=\min\{k,l\}$ とすると、$i< j$ では $x_i=y_i=z_i$ である。

• $k< l$ なら $j=k$ で、$x_k<_k y_k=z_k$。
• $l< k$ なら $j=l$ で、$x_l=y_l<_l z_l$。
• $k=l$ なら $x_k<_k y_k<_k z_k$ なので $x_k\leq_k z_k$ であり、$x_k=z_k$ なら $z_k<_k y_k$ と $y_k<_k z_k$ が同時に成り立って反対称律に反するので、$x_k<_k z_k$。
  いずれの場合も $x_j<_j z_j$ かつ $i< j$ で $x_i=z_i$ なので、$d(x,z)=j$ であり $x<_{\mathrm{lex}}z$ である。$x\leq_{\mathrm{lex}}y\leq_{\mathrm{lex}}z$ で等号が入る場合は明らかである。
  全順序律：$x\neq y$ なら $k=d(x,y)$ で $x_k\neq y_k$ であり、$\leq_k$ は全順序なので $x_k<_k y_k$ または $y_k<_k x_k$、すなわち $x<_{\mathrm{lex}}y$ または $y<_{\mathrm{lex}}x$ である。$\square$

$\Sigma$ に属さない新しい記号 $\bot$ を加えた $\Sigma_\bot:=\Sigma\cup\{\bot\}$ に、$\bot$ がどの文字よりも小さい全順序を入れる。語 $u=u_1\cdots u_m$ に、後ろに $\bot$ を無限に並べた列 $\iota(u):=(u_1,\dots,u_m,\bot,\bot,\dots)\in\Sigma_\bot^{\mathbb{N}}$ を対応させる。$\iota(u)$ の $\bot$ の最初の位置が $m+1$ なので、$\iota$ は単射である。
$u\neq v$ について、$u<_{\mathrm{lex}}v$ と $\iota(u)<_{\mathrm{lex}}\iota(v)$（def-lex-product の無限列の辞書式順序）が同値であることを示す。$u$ が $v$ の真の接頭辞なら、$\iota(u)$ と $\iota(v)$ が最初に違う位置は $|u|+1$ であり、そこで $\iota(u)$ は $\bot$、$\iota(v)$ は文字なので $\iota(u)<_{\mathrm{lex}}\iota(v)$ である。$v$ が $u$ の真の接頭辞なら、同様に $\iota(v)<_{\mathrm{lex}}\iota(u)$ である。どちらでもなければ $u_i\neq v_i$ となる最小の $i\le\min\{|u|,|v|\}$ があり、それが $\iota(u),\iota(v)$ の最初に違う位置なので、両方の順序で大小は $u_i,v_i$ の大小で決まる。
したがって $\leq_{\mathrm{lex}}$ は、prop-lex-total により全順序である $\Sigma_\bot^{\mathbb{N}}$ の辞書式順序を、単射 $\iota$ で $\Sigma^*$ に引き戻したものであり、全順序である（全順序の部分集合への制限は全順序：全順序 の記事の命題「部分集合への制限」）。
$\leq_{\mathrm{sl}}$ は、語 $u$ に組 $(|u|,u)\in\mathbb{N}\times\Sigma^*$ を対応させ、$\mathbb{N}\times\Sigma^*$ の 2 成分の辞書式順序（$\Sigma^*$ には $\leq_{\mathrm{lex}}$）を引き戻したものである。この対応は単射で、2 成分の辞書式順序は prop-lex-total により全順序なので、$\leq_{\mathrm{sl}}$ も全順序である。$\square$

$x=y$ なら明らかである。$x\neq y$ なら $k=d(x,y)$ で $x_k\leq_k y_k$ かつ $x_k\neq y_k$ なので $x_k<_k y_k$、すなわち $x<_{\mathrm{lex}}y$ である。逆については、$\mathbb{N}^2$ で $(0,1)<_{\mathrm{lex}}(1,0)$ だが $1\leq0$ でないので、直積順序では $(0,1)\leq(1,0)$ でない。$\square$

$(x+z)_i=(y+z)_i$ と $x_i=y_i$ は同値なので、$x+z$ と $y+z$ が最初に違う位置は $k=d(x,y)$ であり、そこで $x_k+z_k< y_k+z_k$ である。よって $x+z<_{\mathrm{lex}}y+z$ である。$\square$

prop-lex-total により全順序なので、空でない部分集合 $S$ が最小元をもつことを示せばよい。$a_1,\dots,a_n$ を次のように順に定める。$S_1:=\{x_1\mid x\in S\}$ は $P_1$ の空でない部分集合なので最小元 $a_1$ をもつ。$a_1,\dots,a_{j-1}$ まで定まり、$x_1=a_1,\dots,x_{j-1}=a_{j-1}$ を満たす $x\in S$ が存在するとき、
$$ S_j:=\{x_j\mid x\in S,\ x_1=a_1,\ \dots,\ x_{j-1}=a_{j-1}\} $$
は $P_j$ の空でない部分集合なので最小元 $a_j$ をもち、$x_1=a_1,\dots,x_j=a_j$ を満たす $x\in S$ が存在する。$j=n$ まで進めると $a:=(a_1,\dots,a_n)\in S$ である。
$x\in S$、$x\neq a$ とし、$k=d(x,a)$ とする。$i< k$ では $x_i=a_i$ なので $x_k\in S_k$ であり、$a_k\leq x_k$ である。$x_k\neq a_k$ なので $a_k< x_k$、すなわち $a<_{\mathrm{lex}}x$ である。よって $a$ は $S$ の最小元である。$\square$

1：$\mathrm{a}<\mathrm{b}$ となる $\mathrm{a},\mathrm{b}\in\Sigma$ があれば、ex-lex-descending-words の語 $\mathrm{a}^k\mathrm{b}$ の集合が最小元をもたない。$\Sigma=\{\mathrm{a}\}$ なら語は $\mathrm{a}^m$（$m\ge0$）だけで、$\mathrm{a}^m$ が $\mathrm{a}^{m'}$ の接頭辞であることは $m\le m'$ と同値なので、$\mathrm{a}^m\mapsto m$ は $\Sigma^*$ から $\mathbb{N}$ への順序同型であり、整列順序である。
2：prop-lex-words-total により全順序である。空でない $S\subset\Sigma^*$ をとる。長さ全体 $\{|u|\mid u\in S\}$ は $\mathbb{N}$ の空でない部分集合なので最小元 $m$ をもつ。長さ $m$ の語の間では、辞書式順序は $\Sigma^m$ の辞書式順序と一致する（同じ長さなので接頭辞の場合は起こらない）。thm-lex-well-ordered により $\Sigma^m$ は整列しているので、$S$ の長さ $m$ の語全体は最小元 $w_0$ をもつ。$S$ の他の語は長さが $m$ より大きいか、長さ $m$ で $w_0$ より辞書式に大きいので、$w_0$ は $S$ の $\leq_{\mathrm{sl}}$ に関する最小元である。
$\Sigma$ が有限で $|\Sigma|=s$ なら、語 $w$ より小さい語は長さ $|w|$ 以下なので、その個数は長さ $\le|w|$ の語の個数 $1+s+\cdots+s^{|w|}$ 以下である。$\square$