Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
    
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

2 Answers 2

up vote 6 down vote accepted

"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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.