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