辞書式順序が半順序であることの証明

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

証明

（反射律）

定義から x = y ならば x ≤_lex y であることより，明らか．

（反対称律）

x ≤_lex y かつ y ≤_lex x とする． もし x = y でないなら， ≤_lex の定義より， m = min { i | x_i ≠ y_i } なる m に対して， x_m < y_m であって y_m < x_m であることになる． これは矛盾なので， x = y でなければならない．

（推移律）

x ≤_lex y かつ y ≤_lex z とする． ≤_lex の定義から， 起こり得る場合は 次の 4 ケースである．

(1)

x = y 　かつ　 y = z .

(2)

x = y 　かつ　 y ≠ z 　かつ　 m = min { i | y_i ≠ z_i } なる m に対して y_m < z_m .

(3)

x ≠ y 　かつ　 l = min { i | x_i ≠ y_i } なる l に対して x_l < y_l 　かつ　 y = z .

(4)

x ≠ y 　かつ　 l = min { i | x_i ≠ y_i } なる l に対して x_l < y_l 　かつ　 y ≠ z 　かつ　 m = min { i | y_i ≠ z_i } なる m に対して y_m < z_m .

(1) のとき

x = z となるので， ≤_lex の定義から x ≤_lex z .

(2) のとき

x ≠ z 　かつ　 m = min { i | x_i ≠ z_i } なる m に対して x_m < z_m となるので， ≤_lex の定義より x ≤_lex z .

(3) のとき

x ≠ z 　かつ　 l = min { i | x_i ≠ z_i } なる l に対して x_l < z_l となるので， ≤_lex の定義より x ≤_lex z .

(4) のとき

まず， ≤_lex の定義より， （l > 0 のとき） 任意の i < l について x_i = y_i であって， （m > 0 のとき） 任意の j < m について y_j = z_j であることに注意する．

さらに場合分けを行なう．

(a) i < m のとき

x_l < y_l = z_l なので， x_l < z_l である． そして， （l > 0 のとき） 任意の i < l について x_i = z_i なので， l = min { i | x_i ≠ z_i } である． したがって， ≤_lex の定義より， x ≤_lex z .

(b) l=m のとき

x_l < y_l < z_l なので， x_l < z_l である． そして， （l > 0 のとき） 任意の i < l について x_i = y_i = z_i なので， l = min { i | x_i ≠ z_i } である． したがって， ≤_lex の定義より， x ≤_lex z .

(c) m < l のとき

x_m = y_m < z_m なので， x_m < z_m である． そして， （m > 0 のとき） 任意の i < m について x_i = z_i なので， m = min { i | x_i ≠ z_i } である． したがって， ≤_lex の定義より， x ≤_lex z .