From: "Arthur L. Rubin" <216-5888@mcimail.com> Subject: Re: Q & A Date: Sun, 28 Mar 1999 00:03:31 +0700 Newsgroups: sci.math Keywords: linearly-ordered sets order-isomorphic Thomas Bushnell, BSG wrote: > > In discussion with a friend, a question came up. Maybe there's a > well-known easy answer, maybe there's no known answer, but regardless, > here's the question. Please enlighten me. > > Define a topology on the set of rational numbers Q using the normal > metric. This is a nowhere compact topology; it has many interesting > properties like a dense set of disconnection points, being dense > itself, having open sets with no borders, and so forth. > > Now define a topology on the set of algebraic numbers A, again using > the normal metric. This is also a nowhere compact topology; it has > the same sorts of interesting properties as the topology on Q. It > even has the same cardinality. > > So the question is: are the topologies on Q and A isomorphic? > > Another related question: is there an order isomorphism between the > rationals and the algebraic numbers? Yes. A standard "back-and-forth" arguement shows that any two countable dense sets without endpoints are order-isomorphic. See, for example, Rosenstein's "Linear Orderings" (Academic Press, 1982). I can give a more complete reference and proof outline if you need it. This also answers the first question, as the metric topology is the order topology on Q and A. -- Arthur L. Rubin 216-5888@mcimail.com ============================================================================== From: David C. Ullrich Subject: Re: a theorem of Cantor? Date: Sat, 29 May 1999 18:17:37 GMT Newsgroups: sci.math To: finalfntsy@aol.com In article <19990529033301.09480.00004062@ng-fz1.aol.com>, finalfntsy@aol.com (FinalFntsy) wrote: > I looking for a proof (I think adapted from a theorem by Cantor) that all > countable densely packed linearly ordered sets with no smallest or largest > element are isomorphic (to the rationals). If anyone could send it, an > outline, or an appropriate reference I would appreciate it (please e-mail > responces to FinalFntsy@aol.com). > > Note: a countable densely packed linear ordered set with no smallest or largest > element, S, is one that satisfies all of the following properties: > S contains a countable number of elements > a 2 place predicate < is defined on S that satisfies the following properties > (where = has the usual definition): > for all x, ~(x < x) > for all x,y,z, (x < y) and (y < z) -> (x < z) > for all x,y, (x < y) or (x = y) or (y < x) > for all x,y, (x < y) -> there exists a z such that, (x < z) and (z < y) > for all x there exists a y such that, x < y > for all x there exists a y such that, y < x Hmm. Doesn't seem hard to prove that such a set is order-isomorphic to the _dyadic_ rationals (the rationals that can be written p/q with q a power of 2.) Supposing this the result you want follows (since the rationals are themselves a "countable densely packed linear ordered set with no smallest or largest element"). Suppose first that a and b are elements of S and a < b. Then the elements of S between a and b are isomorphic to the dyadic rationals between 0 and 1. You construct an isomorphism like so: First enumerate all the elements of S lying between a and b: a_1, a_2, ... . Now define a map like so: f(0) = a f(1) = b f(1/2) = a_n, where n is minimal subject to f(0) < a_n < f(1) f(1/4) = a_n, where n is minimal subject to f(0) < a_n < f(1/2) f(3/4) = a_n, where n is minimal subject to f(1/2) < a_n < f(1) f(1/8) = a_n, where n is minimal subject to f(0) < a_n < f(1/4) f(3/8) = a_n, where n is minimal subject to f(1/4) < a_n < f(1/2) f(5/8) = a_n, where n is minimal subject to f(1/2) < a_n < f(3/4) f(7/8) = a_n, where n is minimal subject to f(3/4) < a_n < f(1) You get the idea. We've constructed a map from the dyadic rationals in [0,1] and the elements of S between a and b. The map is 1-1 because all the inequalities are strict. And the map is onto because we always take n minimal - this shows that any a_n must be used at some stage. (Details left to the reader...) That takes care of the bit between a and b. To get from there to the result you want we need only show that there exists a map from the integers to S with range cofinal in both directions. Ie we need to find s_n in S (for n in Z) such that s_n < s_(n+1) and such that for any a in S there exist n and m with s_m < a < s_n. (Ie^2, s_n tends to plus infinity as n tends to plus infinity and to minus infinity as n tends to minus infinity.) Then we apply the previous argument to map the part of S between s_n and s_(n+1) to the dyadic rationals in [n, n+1] and we're done. So why is there an increasing cofinal sequence?... Oh: Let a_n be an enumeration of S. Set s_0 = a_0, and having chosen s_0, ..., s_n (n > 0) let s_(n+1) = a_m, m minimal subject to the two conditions a_m > s_n, a_m > a_(n+1) (s_n) is an increasing sequence, and the fact that s_n > a_n shows it's cofinal. Define a_n for n < 0 similarly. Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. ============================================================================== From: scott@math.csuohio.edu (Brian M. Scott) Subject: Re: a theorem of Cantor? Date: Sat, 29 May 1999 19:27:50 GMT Newsgroups: sci.math On 29 May 1999 07:33:01 GMT, finalfntsy@aol.com (FinalFntsy) wrote: >I looking for a proof (I think adapted from a theorem by Cantor) that all >countable densely packed linearly ordered sets with no smallest or largest >element are isomorphic (to the rationals). If anyone could send it, an >outline, or an appropriate reference I would appreciate it (please e-mail >responces to FinalFntsy@aol.com). (posted and mailed) Let (S, <) be a countable, dense, linear order without endpoints, and let (Q, <) be the rationals with their usual order. The usual way to construct an order-isomorphism is by a recursive construction that is often called a 'back-and-forth' argument. The idea is fairly simple. First enumerate S = {s(n) : n in N} and Q = {q(n) : n in N}. Suppose that at stage n a partial order-isomorphism h has been defined in such a way that dom(h) contains each s(k) with k < n, and ran(h) contains each q(k) with k < n. Suppose first that s(n) is not in dom(h). In the ordering of S, either s(n) precedes all members of dom(h), or it follows all of them, or it lies between two of them. In the first case choose h(s(n)) to be any rational less than all members of ran(h); in the second, take h(s(n)) to be any rational larger than all members of ran(h); and in the third, if s(n) lies between s(i) and s(j), which are adjacent in dom(h), choose h(s(n)) to be any rational between h(s(i)) and h(s(j)). If s(n) is already in dom(h), nothing need be done here. Similarly, if q(n) is not in ran(h), we can find an s(i) in S\dom(h) such that if we set h(s(i)) = q(n), the resulting extended h is still an order-isomorphism; and if q(n) is already in ran(h), we do nothing. This completes the n-th stage of the construction. Clearly the recursion goes through to yield an order-isomorphism whose domain is S and whose range is Q. It's not actually necessary to work back and forth in constructing h. We could just as well assume at stage n that dom(h) = {s(i) : i < n} and take h(s(n)) to be the first rational (in the enumeration of Q) that falls in the appropriate gap determined by ran(h). One can then show without much work that h is onto. Brian M. Scott ============================================================================== From: Robin Chapman Subject: Re: a theorem of Cantor? Date: Sat, 29 May 1999 19:36:46 GMT Newsgroups: sci.math To: finalfntsy@aol.com In article <19990529033301.09480.00004062@ng-fz1.aol.com>, finalfntsy@aol.com (FinalFntsy) wrote: > I looking for a proof (I think adapted from a theorem by Cantor) that all > countable densely packed linearly ordered sets with no smallest or largest > element are isomorphic (to the rationals). If anyone could send it, an > outline, or an appropriate reference I would appreciate it (please e-mail > responces to FinalFntsy@aol.com). Let A and B be two such sets. Enumerate them: A = {a_1, a_2, ...} and B = {b_1, b_2, ....}. We shall produce a set of maps phi_n: A_n --> B_n which are order-preserving bijections between n-element subsets of A and B with |A_n| = |B_n| = n. Also each phi_n "extends" the previous one. Finally the union of the A_n (resp. B_n) is A (resp. B) so that by putting all the phi_n together we get an order-isomorphism phi: A --> B. Start with A_0 and B_0 empty. At odd stages, choose the first element a_k of A (in the given enumeration) not in A_{n-1} and insert it in A_{n-1} to give A_n. Now in each "gap" between the elements of B_{n-1} and in the "gaps" before the first and after the last element of B_{n-1} there are elements of B. Thus there is a suitable b in B so that the extension phi_n of phi_{n-1} to B_n given by phi(a_k) = b is order-preserving. The cunning thing is that even stages we do the same in *reverse*. Take the first element of B we haen't used and choose a suitable element of A to map to it. This guarantees that after 2k stages both a_k and b_k have been paired off. Robin Chapman Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't. ============================================================================== From: Fred Galvin Subject: Re: Isn't omega an ordinal number? Date: Thu, 7 Oct 1999 21:50:35 -0500 Newsgroups: sci.math On Thu, 7 Oct 1999, Fred Galvin wrote: > On Thu, 7 Oct 1999, Richard Carr wrote: > > > I'm not disagreeing because I know you know a lot more about this than me, > > but I thought that eta was the order-type of the irrationals. Evidently, I > > am wrong: is it mu that is the order type of the irrationals. > > I don't know much, I didn't even know that there was any standard symbol > for the order type of the irrationals. I'm not sure if Cantor used eta for > the order type of the rationals, but Hausdorff did: "Man bezeichnet den > Typus der (natuerlich geordneten) Menge der rationalen Zahlen mit [eta], > der reelen Zahlen mit [lambda]."--Felix Hausdorff, _Grundzuege der > Mengenlehre_, 1914. Hausdorff also defined (elsewhere) the generalized > eta-types, eta_alpha for every ordinal alpha, with eta_0 = eta = the order > type of the rationals. Yes, Cantor used eta for the order type of the rational numbers (but theta instead of Hausdorff's lambda for the order type of real numbers) in his 1895 paper "Contributions to the founding of the theory of transfinite numbers" (Jourdain's English translation, Dover edition, pp. 123, 133).