If $\leq$ is a total order on a set $S$, then the new relation $<$ defined by $x < y$ iff ($x \leq y$ and $x \neq y$) is a strict total order on $S$.
If $<$ is a strict total order on a set $S$, then the new relation $\leq$ defined by
$x \leq y$ iff ($x < y$ or $x = y$) is a total order on $S$.
In other words, in a fairly evident way one can always exchange a total order for a strict total order and conversely. So it doesn't really matter which definition is taken. One can easily check that the definition of a well-order in one setting carries over to the definition of a well-order in the other setting.
The order in (1) is known as the lexicographic order on $\Bbb N\times\Bbb N$ and is actually a total order. To show that it’s antisymmetric, suppose that $\langle m_1,n_1\rangle\le\langle m_2,n_2\rangle$ and $\langle m_2,n_2\rangle\le\langle m_1,n_1\rangle$.
- Since $\langle m_1,n_1\rangle\le\langle m_2,n_2\rangle$, we know that either $m_1<m_2$, or $m_1=m_2$ and $n_1\le n_2$.
- Since $\langle m_2,n_2\rangle\le\langle m_1,n_1\rangle$, we know that either $m_2<m_1$, or $m_2=m_1$ and $n_2\le n_1$.
We cannot have $m_1<m_2$: that would imply that $m_2\not<m_1$ and $m_2\ne m_1$, contradicting (2). Thus, $m_1=m_2$, and $n_1\le n_2$. And from (2) we can then see that $n_2\le n_1$ as well, since $m_2=m_1$. Finally, the usual order on $\Bbb N$ is antisymmetric, so $n_1\le n_2$ and $n_2\le n_1$ imply that $n_1=n_2$. We’ve now shown that $m_1=m_2$ and $n_1=n_2$, i.e., that $\langle m_1,n_1\rangle=\langle m_2,n_2\rangle$, as desired.
In the second problem you’re given a transitive relation $<$ on some set $X$, and you’re further told that $<$ has the trichotomy property: for any $x,y\in X$, exactly one of the statements $x<y$, $x=y$, and $y<x$ is true. Now you’re to define a new relation, $\le$, on $X$ by setting $x\le y$ if and only if either $x<y$ or $x=y$. Finally, you’re to prove that this new relation $\le$ is a total order.
To do this you must show that $\le$ is reflexive, antisymmetric, transitive, and total. Reflexivity and transitivity are pretty straightforward, and I’ll leave them to you. For antisymmetry, suppose that $x\le y$ and $y\le x$. Since $x\le y$, we know that either $x<y$ or $x=y$. Suppose that $x\ne y$. Then $x<y$, and by the trichotomy property we know that it is not the case that $y<x$. But then we have $y\not<x$ and $y\ne x$, so be definition it’s not the case that $y\le x$. This contradiction shows that we cannot have $x\ne y$ and hence that $x=y$, as desired. Finally, to show that $\le$ is total, use trichotomy again: for any $x,y\in X$, either $x<y$, in which case $x\le y$; or $x=y$, in which case $x\le y$; or $y<x$, in which case $y\le x$.
This exercise shows how you can turn any so-called strict linear (or total) order $<$ on a set $X$ into an ordinary total order $\le$ in such a way that the $\le$ symbol has the obvious, expected meaning.
This is just the opposite of the previous problem: starting with a total order $\le$ on $X$, turn it into a strict linear order by ‘throwing away the equals part of it’. That is, given the total order $\le$ on $X$, define a new relation $<$ on $X$ by $x<y$ if and only if $x\le y$ and $x\ne y$. Now you’re to show that this new relation is transitive and has the trichotomy property: for any $x,y\in X$, exactly one of $x<y$, $x=y$, and $y<x$ holds. Proving transitivity is very straightforward, and I’ll leave it to you. Trichotomy isn’t much harder, but you do have to check two things: you must show that for any $x,y\in X$ at least one of $x<y$, $x=y$, and $y<x$ holds, and you must also show that it’s never the case that more than one holds. To see, for example, that it’s not possible to have both $x<y$ and $y<x$, note that $x<y$ implies that $x\le y$, and $y<x$ implies that $y\le x$. The relation $\le$ is antisymmetric, so $x=y$. But then by definition $x\not<y$, and we have a contradiction. I’ll leave the rest to you, but feel free to ask for help if you get stuck.
Best Answer
A well-ordering, as you say, is a linear ordering where every nonempty set has a least element. Every well-ordering is a linear ordering by definition$^*$, but the converse is not true - the following are examples of linear orders which are not well-ordered:
$\mathbb{Z}$ ($\mathbb{Z}$ itself has no least element).
$\{{1\over n+1}: n\in\mathbb{N}\}\cup\{0\}$ (while the whole set does have a least element, the nonempty proper subset $\{{1\over n+1}: n\in\mathbb{N}\}$ does not).
$\mathbb{Q}$, $\mathbb{R}$, $[0, 1]$, ... There are lots.
The simplest examples of well-orderings are the finite linear orders and $\mathbb{N}$ itself (the fact that $\mathbb{N}$ is well-ordered is the thing that makes proof by induction work!). However, there are bigger well-orderings; for example, "$\mathbb{N}+\mathbb{N}$," where "$+$" denotes the sum of linear orders (put the first "after" the second). Concretely, an example of a linear ordering of type $\mathbb{N}+\mathbb{N}$ would be $$\{1-{1\over n+1}: n\in\mathbb{N}\}\cup\{2-{1\over n+1}: n\in\mathbb{N}\}$$ with the usual ordering.
Indeed, there are arbitrarily large well-orderings, even though they get increasingly difficult to visualize. For any infinite cardinal $\kappa$, the set of isomorphism types of well-orderings$^{**}$ of cardinality $\le \kappa$ is itself well-ordered by "embeds into," and has cardinality $>\kappa$ (in fact, $\kappa^+$). For a concrete example, there are uncountable well-ordered sets! Note that this does not rely on the axiom of choice.
$^*$Actually, we can say a bit more: any antisymmetric relation $R$ on a set $X$ satisfying $$\mbox{For all nonempty $Y\subseteq X$, there is some $y\in Y$ with $yRz$ for all other $z\in Y$}$$ is actually a well-ordering (that is, the "linear ordering" requirement is superfluous): we already have antisymmetry, so now just show trichotomy and transitivity:
For trichotomy, given $x\not=y$ think about the two-element set $\{x, y\}$ ...
For transitivity, suppose $xRy$ and $yRz$ (note: by antisymmetry this means $x\not=z$) but $x\not Rz$. By trichotomy, we have $zRx$. But now think about the three-element set $\{x, y, z\}$ ...
$^{**}$There's a bit of an issue here actually: an isomorphism type is a proper class, so we can't form the set of isomorphism types of well-orderings of a given cardinality. There are various ways to get around this, and it's at this point that the von Neumann ordinals should be introduced. But this should really be a side issue.