Find, without using the axiom of choice, an order relation that makes $\omega \times 2$ a well-ordered set.

Question

Let $\omega$ denote the set of the natural numbers defined as: $0 = \emptyset$, $1 = \{ \emptyset \}$, $2 = \{ \emptyset, \{\emptyset\} \}$, ...

How can I, without using the axiom of choice, find an order relation that makes $\omega \times 2$ a well-orderer set?

I've tried to put the relation $(a,b) \leq (c,d) \iff a \subset c$ and $b \subset d$. However, with this relation $\{ (4,0), (2,1) \}$ has not a minimal element, so it's not a well-order.

Help?

Answer 1

Since $\omega$ and $2$ are both well orders, you can take the lexicographical order, i.e. $$(a,b) < (c,d) \Leftrightarrow a < c \,\text{or}\, (a=c \,\text{and}\, b < d) $$

Answer 2

The usual order is $0,1,2,3,\ldots,\omega,\omega+1,\omega+2,\ldots$.

Why is this a well-order?