Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: wellordering?
Replies: 4   Last Post: Dec 1, 2001 2:18 PM

 Messages: [ Previous | Next ]
 Herman Rubin Posts: 6,721 Registered: 12/4/04
Re: wellordering?
Posted: Dec 1, 2001 2:18 PM

In article <%JRM7.70869\$Ud.3453794@news1.rdc1.bc.home.com>,
Elaine Jackson <elainejackson7355@home.com> wrote:
>Let F be the set of all functions f with ran(f)<=dom(f)=(the set of positive
>integers), and consider the lexicographical ordering of F. (Lexicographical
>ordering: f1<f2 iff (1) f1,f2 are different functions, and (2) f1(n)<f2(n),
>where n is the number with f1(k)=f2(k) for all k<n.) Clearly this is a
>linear order, but is it a wellordering? The only thing I can think of is
>this: given a nonempty subset S of F, first throw out all the functions
>whose value at 1 is not minimal (in S), then throw out all the functions
>whose value at 2 is not minimal (in the set remaining from the previous
>step), and so on. If f belongs to every set in the resulting sequence, then
>f is the smallest element of S, but how can you prove that some f belongs to
>every set in the sequence?

This is well known. It is false even if f can only take
on two values or is 1-1. The proof that there is a
well-ordering of either of these sets of functions would
prove that the reals could be well-ordered, and producing
one would provide an explicit well ordering of the reals.

To see that the lexicographic ordering is not a well
ordering for the second case, let f_i(j) be j if j < i,
and j+1 if j >= i. This gives a decreasing sequence
of f's; in fact, each f is less everywhere than the
earlier ones. One cannot have a decreasing sequence
in a well-ordered set.

--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558

Date Subject Author
11/27/01 Elaine Jackson
11/27/01 magidin@math.berkeley.edu
11/27/01 Andy Averill
11/28/01 magidin@math.berkeley.edu
12/1/01 Herman Rubin