We define an ordering $\mathbb N \times \mathbb N$, $\le$ as follows: $(a, b) \le (c, d)$ iff $a \le c$ and $b \le d$. I tried to prove that $\mathbb N \times \mathbb N$ is well ordered under this relation by extending a proof I found on this site for $\mathbb N$ to $\mathbb N ^2$
This was the proof I found: Let $M \subset \mathbb{N}$ be non-empty. We assume $M$ has no first element. Let $$L := \{n \in \mathbb{N}\ |\ \forall m \in M, n\leq m\}.$$
Fact 1: $n \not \leq m$ (i.e. it's not the case that $n \leq m$) iff $n >m$.
Fact 2: For every $n \in \mathbb{N}, 1 \leq n$.
Fact 3: There is no $m$ such that $n < m < n+1$.
$1 \in L$. To see this, suppose towards a contradiction that $1 \not \in L$. By the definition of $L$, this means that there is $m \in M$ such that $1 > m$. But, by the two facts above, this is absurd. So we have $1 \in L$.
Next, suppose $n \in L$ and consider $n+1$. Suppose, again towards a contradiction, that $n+1 \not \in L$. Then there is some $m \in M$ such that $n+1 > m$. But, since $n \in L$, it follows by the definition of $L$ that $n \leq m$, that is, either $n < m$ or $n =m$. If $n=m$, then $n$ is the smallest element of $M$, contradicting the hypothesis that $M$ has no smallest element. If $n <m$, we have $n < m < n+1$, contradicting Fact 3. Either way, we reach a contradiction. So $n+1 \in L$
And, I have shortened the proof a bit, but the two facts above imply that M is empty and thus, no subset of $\mathbb N$ exists such that the subset has no least element.
I extended it to $\mathbb N \times \mathbb N$ by doing the following:
- Assume a subset of $D = \mathbb N \times \mathbb N$, $N$ exists such that $N$ is linearly ordered but has no least element. Define $L:= \{ (m, n) \in D: \forall (p,q) \in N, (m,n) \le (p,q) \}$
It is easy to prove that $(1, 1) \in L$
The next step (I presume) would be to prove that if $(m, n) \in L$, then $(m+1, n) \in L$, and $(m, n+1) \in L$. I believe that that is equivalent to proving that if $n \in L, n+1 \in L$ as in the proof given before, if it can be shown that every ordered pair in D can be defined in this way.
However, this second step easily spirals into a litany of cases which I have confirmed at least partially to be true. I will be honest, I am finding it tedious to finish but I will. However, I wish to ask; is there a better way to go about this proof? and is my second step a correct generalisation (at least to $\mathbb N \times \mathbb N$)? Also, in the last sentence of the previous paragraph, I made a claim. I feel confident in the claim given that from a specific point in a rectangular lattice (which I define as the graphical representation of the cartesian product of $\mathbb N$ with itself), the point can only grow with respect to our ordering in three directions. (I believe the third direction is a combination of the other two). However, as we are to justify our intuitions with proofs, is there a way to build the lattice plane inductively? (I believe, yes) Does it even make sense to do so?
You are mis-using the term "well-ordered." The definition of a well-ordered set is a poset with the property that every nonempty subset has a least element. See, e.g., Wikipedia, MathWorld, LibreTexts, Proof-wiki, among many, many, many others.
In particular, a well-ordered set must be totally ordered, which $\mathbb{N}\times\mathbb{N}$ with the product order is not.
What you seem to be trying to prove is that $\mathbb{N}\times\mathbb{N}$ with the product satisfies a weaker condition than "well-ordered", namely:
This holds for any product of well-ordered sets with the product order; in fact, any product of two sets with this property (in particular, well-ordered sets) equipped with the product order will also have this property. I will give a general proof below.
I don't much care for the argument you are trying to extend (an unnecessary proof by contradiction which will end up using the ideas that will be used in the general theorem, but obscured). But here goes.
You assume that $M$ is a chain in $\mathbb{N}\times\mathbb{N}$ (under the product order) which does not have a least element. We want to prove that $M$ is empty. You let $(m,n)$ be a lower bound for $M$. You want to show that both $(m+1,n)$ and $(m,n+1)$ are also lower bounds for $M$.
First, $(m,n)\notin M$, since a lower bound that lies in the chain must be a least element. Second, for all $(a,b)\in M$, we have $m\leq a$ and $n\leq b$.
If $(m+1,n)$ is not a lower bound for $M$, then there exists $(a,b)\in M$ such that $(m+1,n)\not\leq (a,b)$. We know $n\leq b$, so because $(m+1,n)\not\leq (a,b)$ it must be the case that $m+1\not\leq a$; thus, $a\lt m+1$. However, we also know that $m\leq a$. Thus, $m\leq a\lt m+1$, and therefore $m=a$.
Now consider $\{(m,n), (m,n+1),\ldots,(m,b)\}\cap M$. This is a chain (intersection of two chains), nonempty (since $(m,b)=(a,b)$ lies in the intersection), and finite, so it has a first element $(a,n_0)$. I claim $(a,n_0)$ is the least element of $M$, which would be a contradiction arising from the assumption that $(m+1,n)$ is not a lower bound for $M$).
Indeed, let $(x,y)\in M$. We know that $a=m\leq x$. We also know $M$ is a chain, so either $(x,y)\leq (a,b)$ or $(a,b)\leq (x,y)$. If $(a,b)\leq (x,y)$, then $$(a,n_0) \leq (a,b) \leq (x,y).$$ If $(x,y)\leq (a,b)$, then $x\leq a=m$, so $x=m=a$; thus, $(x,y)=(a,y)$. We also have $y\leq b$, and therefore by choice of $n_0$ we know that $n_0\leq y$ so $(a,n_0)\leq (x,y)$.
Thus, $(a,n_0)$ is a least element for $M$, contradicting our assumption that $M$ does not have a least element. This contradiction arises from the assumption that $(m+1,n)$ is not a lower bound for $M$ when $(m,n)$ is a lower bound for $M$. Thus, if $(m,n)$ is a lower bound for $M$, then $(m+1,n)$ is a lower bound for $M$.
The same argument, mutatis mutandi, shows that $(m,n+1)$ is a lower bound for $M$: if it is not a lower bound, then there exists $(a,b)\in M$ such that $(m,n+1)\not\leq (a,b)$. This means $b=n$, so let $(m_0,b)$ be the least element of $\{(m,n), (m+1,n),\ldots,(a,n)\}\cap M$. Then $(m_0,b)$ is in fact a least element of $M$, contradicting our assumption. Hence, if $(m,n)$ is a lower bound for $M$, then so is $(m,n+1)$.
From this we conclude that the set of all lower bounds of $M$:
This proves the set is all of $\mathbb{N}\times\mathbb{N}$: by 1 and 2, using induction we have that it contains $\mathbb{N}\times\{1\}$; and if it contains $\mathbb{N}\times\{n\}$ then by 3 it contains $\mathbb{N}\times\{n+1\}$, hence it contains $\cup_{n\in\mathbb{N}}\mathbb{N}\times\{n\} = \mathbb{N}\times\mathbb{N}$.
Therefore, $M$ is empty, proving that nonempty chains have a least element.
In fact, there is a much simpler way of showing this.
Theorem. Let $(P,\leq_1)$ and $(Q,\leq_2)$ be posets in which every nonempty chain has a least element. Define the partial order $\leq$ on $P\times Q$ by $(a,b)\leq (x,y)\iff a\leq_1x$ and $b\leq_2y$. Then every nonemtpy chain in $(P\times Q,\leq)$ has a least element.
Proof. Let $\pi_1\colon P\times Q\to P$ be the projection onto the first coordinate. Then $\pi_1$ is monotone (if $x\leq y$, then $\pi_1(x)\leq_1\pi_1(y)$). Similarly for $\pi_2\colon P\times Q\to Q$.
Let $C$ be a nonempty chain in $P\times Q$. Then $\pi_1(C)$ is a nonempty chain of $P$, and hence has a least element, $p_0$. Let $C_{p_0} = \{(x,y)\in C\mid x=p_0\}$. Then $C_{p_0}$ is a nonempty chain, and $\pi_2(C_{p_0})$ is a nonempty chain in $Q$, which has a least element $q_0$.
I claim that $(p_0,q_0)$ is the least element of $C$. Indeed, let $(x,y)\in C$. Then $p_0\leq x$ by choice of $p_0$. If $p_0\lt x$, then $(x,y)\not\lt (p_0,q_0)$, hence $(p_0,q_0)\leq (x,y)$. If $p_0=x$, then $(x,y)\in C_{p_0}$, and therefore $q_0\leq \pi_2(x,y)=y$. Thus, $p_0\leq x$ and $q_0\leq y$, so $(p_0,q_0)\leq(x,y)$, as desired. This shows that $C$ has a least element, as claimed. $\Box$