From: ags@seaman.cc.purdue.edu (Dave Seaman) Subject: Re: Mapping Ordinals onto Rationals Date: 3 Aug 2000 13:34:26 -0500 Newsgroups: sci.math Summary: [missing] In article <8mcaoq$3ov$1@nnrp1.deja.com>, Dave Ashley wrote: >You are confusing me. >Of course you can map the ordinals onto the reals. Since the set of >ordinal numbers is a subset of the reals, f(x) = x will do the trick. No, the ordinal numbers are not a subset of the reals. For example, omega (the first transfinite ordinal) is not a real number, nor is any ordinal larger than omega a real number. In fact, the ordinals are not even a set. There are too many of them. However, the *countable* ordinals are a set. >In article <8mc3i3$10n0@edrn.newsguy.com>, > daryl@cogentex.com (Daryl McCullough) wrote: >> I've heard that every countable ordinal can be mapped into the reals >> so that if alpha < beta, f(alpha) < f(beta). Is this true for the >> rationals, as well, or is there some maximum ordinal gamma such that >> it is impossible to map gamma into the rationals in an >order-preserving >> way? There is a difference between saying "every countable ordinal can be mapped..." and "all countable ordinals can be mapped...." Lemma. Let Q(0,1) be the set of rationals in the interval (0,1). Then there is an order-preserving map f: Q -> Q(0,1). Proof. Divide (0,1) into a countable number of subintervals such that the set of subintervals has the same order type as Z. For example, the partition points may be 1/2 +/- 1/2^k for k = 2, 3, 4, .... For each n, construct an order-preserving map of the rationals in [n,n+1) into the n-th subinterval of (0,1), where [1/2,3/4) is the zeroth subinterval. Proposition. Let alpha be a countable ordinal. Then there is an order-preserving map f: alpha -> Q. Proof. By transfinite induction. The case for successor ordinals follows immediately from the lemma. Suppose gamma is a countable limit ordinal, and suppose { alpha_k } is a countable sequence of ordinals with lim_k alpha_k = gamma, where for each alpha_k we have an order-preserving f_k : alpha_k -> Q. Using the lemma, we may construct an order-preserving g_k : alpha_k -> Q(k,k+1), where the range is the set of rationals in the interval (k,k+1). Then we define f: gamma -> Q such that for each beta < gamma, we let k be the least index such that beta < alpha_k, and then define f(beta) = f_k(beta). The resulting map is clearly order-preserving, Q.E.D. Notice it does not follow from this that there is an order-preserving map defined on the union of all the countable ordinals, since that is an uncountable set and any partition of the reals or rationals into nondegenerate intervals is necessarily a countable collection. In fact omega_1, the first uncountable ordinal, is the smallest ordinal that cannot be so mapped onto the rationals (or the reals). >> A related question: is there a simple to describe order-preserving >> mapping of epsilon-0 into the reals? I'll pass on that. We know that an order-preserving map exists. -- Dave Seaman dseaman@purdue.edu Amnesty International calls for new trial for Mumia Abu-Jamal ============================================================================== From: Robin Chapman Subject: Re: Mapping Ordinals onto Rationals Date: Thu, 03 Aug 2000 17:46:46 GMT Newsgroups: sci.math In article <8mc3i3$10n0@edrn.newsguy.com>, daryl@cogentex.com (Daryl McCullough) wrote: > I've heard that every countable ordinal can be mapped into the reals > so that if alpha < beta, f(alpha) < f(beta). Is this true for the > rationals, as well, or is there some maximum ordinal gamma such that > it is impossible to map gamma into the rationals in an order-preserving > way? Yes, to the first question: every countable ordinal can be mapped into Q in an order-preserving way. I don't understand the second question. There's a *minimum* ordinal which cannot be order-mapped into Q -- the smallest uncountable ordinal. It can't be order mapped into R either. It's easy to prove that every countable totally ordered set can be order-mapped into Q. Let the set be {a_1,a_2, ...}. Let f(a_1) be any rational. If a_2 > a_1 let f(a_2) be any rational greater than f(a_1) otherwise let it be a rational less than f(a_1). Then f(a_1) and f(a_2) define 3 intervals in Q. Let f(a_3) be in the appropriate one of these intervals according to its ordering with a_1 and a_2 etc. etc. ... > A related question: is there a simple to describe order-preserving > mapping of epsilon-0 into the reals? I shouldn't think so, but I'd like to see someone prove me wrong :-) -- Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html "`The twenty-first century didn't begin until a minute past midnight January first 2001.'" John Brunner, _Stand on Zanzibar_ (1968) Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Fred Galvin Subject: Re: Mapping Ordinals onto Rationals Date: Thu, 3 Aug 2000 19:53:24 -0500 Newsgroups: sci.math On Thu, 3 Aug 2000, Robin Chapman wrote: > Yes, to the first question: every countable ordinal can be mapped > into Q in an order-preserving way. I don't understand the second > question. There's a *minimum* ordinal which cannot be order-mapped > into Q -- the smallest uncountable ordinal. It can't be order > mapped into R either. > > It's easy to prove that every countable totally ordered set > can be order-mapped into Q. [Good proof snipped.] Alternatively: Let A be any countable totally ordered set. Choose a 1-to-1 function k:A-->N. Define functions g:A-->R and h:A-->R by setting g(x) = the sum of 2^{-k(z)} over all z < x, and h(x) = the sum of 2^{-k(z)} over all z <= x. Then x < y implies g(x) < h(x) <= g(y) < h(y). Now define f:A-->Q by choosing, for each x in A, a rational number f(x) between g(x) and h(x).