全順序から導入される辞書式順序が全順序であることの証明

(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 )

証明

≤_lex が 半順序であることは すでに示されている ので（問 1 解答）， 比較可能性を示せばよい．
x = y のときは， ≤_lex の定義より x ≤_lex y である．
x ≠ y のときは， m = min { i | x_i ≠ y_i } なる m が存在する． このとき， ≤_m は全順序だから， x_m < y_m または y_m < x_m である． ≤_lex の定義より x_m < y_m のときは x ≤_lex y であり， y_m < x_m のときは y ≤_lex x である．
(Q.E.D.)