# Is 'well founded' the same as 'well ordered'?

Can someone please kindly help me understand the differences between 'well ordered' and 'well founded' (if any).

From what I understand, to be 'well founded' is where all non-empty subsets of S has a R-minimal element, and for 'well ordered' it is where where there is a least element for all such sets. Are these equivalent?

I feel I'm missing something though, and would greatly appreciate some enlightenment. Thanks!

-
–  Willie Wong Mar 5 '12 at 11:28
The wikipedia page for well founded also contains many examples of well founded relations which are not total orderings. (And hence they cannot be well orderings.) –  Willie Wong Mar 5 '12 at 11:31

"Well-ordered" means linearly-ordered and well-founded.

As an example of a well-founded partial order which is well-founded but not well-ordered, consider the family $\omega^{<\omega}$ of all finite sequences in $\omega$ and order this by $s \sqsubseteq t$ iff $s$ is an initial segment of $t$ (i.e., $\mathrm{dom}(s) \subseteq \mathrm{dom}(t)$ and $s(n) = t(n)$ for all $n \in \mathrm{dom}(s)$). This is well-founded, because for every nonempty $A \subseteq \omega^{<\omega}$ there is a minimal $n \in \omega$ such that $A \cap \omega^n \neq \emptyset$, and then take any element of this intersection. It is not well-ordered since there are many $\sqsubseteq$-incomparable elements.

-

Another example besides Arthur’s may be helpful.

Let $P=\Bbb{N}\times\Bbb{N}$, and for $\langle m_0,n_0\rangle,\langle m_1,n_1\rangle\in P$ write $\langle m_0,n_0\rangle\preceq\langle m_1,n_1\rangle$ iff $m_0\le m_1$ and $n_0\le n_1$. If you think of $P$ as the set of integer points in the first quadrant, $p\preceq q$ simply means that $p$ is below and to the left of $q$ (including direcly to the left and directly below). Let $A$ be any non-empty subset of $P$; to show that $\preceq$ is well-founded, we need to show that there is some $\preceq$-minimal $a\in A$. Let $A_0$ be the set of all first coordinates of $A$; $\varnothing\ne A_0\subseteq\Bbb{N}$, so $A_0$ has a smallest element, $m_0$. Now let $A_1=\{n\in\Bbb{N}:\langle m_0,n\rangle\in A\}$; $\varnothing\ne A_1\subseteq\Bbb{N}$, so $A_1$ has a smallest element, $n_0$; ; $n_0$ is the smallest second coordinate that ever appears in the same ordered pair with the first coordinate $m_0$. You should have little trouble verifying that $\langle m_0,n_0\rangle$ is a minimal element of $A$ with respect to $\preceq$, i.e., that there is no $\langle m,n\rangle\in A$ such that $\langle m,n\rangle\preceq\langle m_0,n_0\rangle$ and $\langle m,n\rangle\ne\langle m_0,n_0\rangle$.

But $P$ is not well-ordered by $\preceq$, because it’s not even linearly ordered by $\preceq$: $\langle 0,1\rangle\not\preceq\langle 1,0\rangle$ and $\langle 1,0\rangle\not\preceq\langle 0,1\rangle$. Another way to observe this is to let $A=\{\langle 0,1\rangle,\langle 1,0\rangle\}$, and note that although both elements of $A$ are minimal with respect to $\preceq$, but neither is minimum.

-