2
$\begingroup$

Taking $\mathbb{N}$ with usual order. Then is the dictionary order on $\mathbb{N}^2$ a well order.
I tried to make hasse diagram for it. $(2,1)$ is clearly greater then $(1,x)$ but where do I put it if $(1,x)$ would go forever?

$\endgroup$
2

2 Answers 2

4
$\begingroup$

Suppose $A$ is a nonempty subset of $\mathbb{N}\times\mathbb{N}$ with the dictionary order. Consider the set $$A_0 = \{n\in\mathbb{N} \mid (n,m)\in A\ \text{for some}\ m\}.$$ As $A$ is nonempty, we must have that $A_0$ is nonempty. Thus $A_0$ is a nonempty subset of $\mathbb{N}$ with its usual ordering, so by the well-ordering of $\mathbb{N}$, there exists $n_1 := \min A_0$. Now consider $$A_1 = \{n\in\mathbb{N} \mid (n_1,n)\in A\}.$$ By a similar argument, there exists $n_2:=\min A_1$. Now show that $(n_1,n_2)$ is the minimal element of $A$.

$\endgroup$
3
$\begingroup$

$\mathbb{N}^2$ is well ordered with respect to the dictionary order as for any subset $A$ of $\mathbb{N}^2$ there exists a least element in the first ordinate due to well orderness of $\mathbb{N}$ and fixing that first ordinate we can get the least elemnt in the second ordinate due to the same argument. That element will be the least element of $A$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .