辞書式順序は全順序をなす

$ (x_1,x_2)\le_{1\times 2}(y_1,y_2):\iff x_1<_1 y_1\lor(x_1=y_1\land x_2\le_2 y_2)

証明

1. 反射律

$ \forall(x_1,x_2)\in A_1\times A_2.(x_1,x_2)\le_{1\times2}(x_1,x_2)

$ \iff\forall(x_1,x_2)\in A_1\times A_2.x_1<_1 x_1\lor (x_1=x_1\land x_2\le_2x_2)

$ \iff\forall x_1\in A_1.x_1<_1 x_1\lor\forall x_2\in A_2.x_2\le_2x_2

$ \iff\forall x_2\in A_2.x_2\le_2x_2

$ \underline{\iff\top\quad}_\blacksquare

2. 推移律

$ \forall(x_1,x_2),(y_1,y_2),(z_1,z_2)\in A_1\times A_2.

$ (x_1,x_2)\le_{1\times2}(y_1,y_2)\land(y_1,y_2)\le_{1\times2}(z_1,z_2)

$ \iff(x_1<_1y_1\lor(x_1=y_1\land x_2\le_2y_2))\land(y_1<_1z_1\lor(y_1=z_1\land y_2\le_2z_2))

$ \iff x_1<_1y_1<_1z_1\lor(x_1<_1y_1=z_1\land y_2\le_2z_2)\lor(x_1=y_1<_1z_1\land x_2\le_2y_2)\lor(x_1=y_1=z_1\land x_2\le_2y_2\le_2z_2)

$ \implies x_1\le_1z_1\lor x_1<_1z_1\lor x_1<_1z_1\lor(x_1=z_1\land x_2\le_2z_2)

$ \underline{\implies(x_1,x_2)\le_{1\times2}(z_1,z_2)\quad}_\blacksquare

3. 反対称律

$ \forall(x_1,x_2),(y_1,y_2)\in A_1\times A_2.

$ (x_1,x_2)\le_{1\times2}(y_1,y_2)\land(y_1,y_2)\le_{1\times2}(x_1,x_2)

$ \iff x_1<_1y_1<_1x_1\lor(x_1<_1y_1=x_1\land y_2\le_2x_2)\lor(x_1=y_1<_1x_1\land x_2\le_2y_2)\lor(x_1=y_1=x_1\land x_2\le_2y_2\le_2x_2)

$ \iff x_1=y_1\land x_2\le_2y_2\le_2x_2

$ \implies x_1=y_1\land x_2=y_2

$ \underline{\iff(x_1,x_2)=(y_1,y_2)\quad}_\blacksquare

4. 完全律