Let $\prec$ be the linear ordering on $\mathbb{N} \times \mathbb{N}$ defined by $(a, b) \prec (c, d)$ if either:
- $a < c$, or
- $a = c$ and $b < d$.
Prove that $\prec$ is a well-ordering of $\mathbb{N} \times \mathbb{N}.$
To my understanding, we must find pick out the smallest $a$ values then once we get that we must get the smallest $b$ values and then declare that the point we found is the least element. How do I formally write this out? I obviously cannot just say $(0,0)$ is the least element.
Also, I want to include that I understand the definition of well-ordering: the set is a linear order and there exist a least element in all non-empty subsets of the set.
It would help if you first proved this fact for $\mathbb{N}$ with its usual order by contradiction using mathematical induction.
Suppose that there exists some non-empty subset $S \subseteq \mathbb{N}$ that does not have a least element. Let $P(n)$ denote the property $n$ is not in $S$. Clearly this holds for $0$ as the set is assumed to not have a least element and should $0\in S$ then $0$ would be the least element of $S$.
Now assume $P(n)$ is true. Then $n$ is not in $S$. Well then $n+1$ cannot be in $S$ as then $n+1$ would be the least element of $S$, as there cannot exist some $m$ such that $n<m<n+1$. Hence, for all $n\in \mathbb{N}$, $P(n)$ holds i.e. $n$ is not in $S$. But then $S= \emptyset$. A contradiction. The source of this is our assumption that $S$ does not have a least element. Hence $\mathbb{N}$ must be well ordered.
The proof for $\mathbb{N} \times \mathbb{N}$ follows as a corallary. You can actually use the proof above as a lemma to conclude that the set $\{a:(a,b)\in S\subseteq \mathbb{N} \times \mathbb{N} \}$ must have a least element $x$, as this is just a subset of $\mathbb{N}$ and then the set $\{c:(x,c)\in S\subseteq \mathbb{N} \times \mathbb{N}\}$ must also have some least element $y$, so $(x,y)$ must be the least element of any non-empty $S \subseteq \mathbb{N} \times \mathbb{N}$.
Hopefully this gives you an intuition for how to rigorously approach such proofs.