辞書式順序

(X₁, ≤₁)， (X₂, ≤₂)， . . . ， (X_n, ≤_n) を半順序集合とする．
x=(x₁, x₂, . . . ， x_n)， y=(y₁, y₂, . . . ， y_n) ∊∏_i=1ⁿ X_i に対して，

x ≤lex y	⇔	x = y 　 または
		( x ≠ y 　かつ　 m = min { i | xi ≠ yi } なる m に対して xm < ym )

次の例から， この順序がなぜ「辞書式」と呼ばれるかがわかるだろう．

例 1

順序集合 (X, ≤) を X = { a, b, c }， a < b < c で定め， (X₁, ≤₁) = (X₂, ≤₂) = (X₂, ≤₃) = (X, ≤) とおくと， ∏_i=1³ X_i = X³ 上の辞書式順序 ≤_lex は 下のようになり， 辞書での単語の並び方と同じになっている．

	(a, a, a)	< lex	(a, a, b)	< lex	(a, a, c)
< lex	(a, b, a)	< lex	(a, b, b)	< lex	(a, b, c)
< lex	(a, c, a)	< lex	(a, c, b)	< lex	(a, c, c)
< lex	(b, a, a)	< lex	(b, a, b)	< lex	(b, a, c)
< lex	(b, b, a)	< lex	(b, b, b)	< lex	(b, b, c)
< lex	(b, c, a)	< lex	(b, c, b)	< lex	(b, c, c)
< lex	(c, a, a)	< lex	(c, a, b)	< lex	(c, a, c)
< lex	(c, b, a)	< lex	(c, b, b)	< lex	(c, b, c)
< lex	(c, c, a)	< lex	(c, c, b)	< lex	(c, c, c)

問 1

≤_lex が 直積 ∏_i=1ⁿ X_i 上の半順序であることを示せ． 　解答

問 2

≤₁， ≤₂， . . . ， ≤_n がすべて全順序 ならば ≤_lex も全順序であることを示せ． 　解答