Dense Linear Ordering problems.
in [Math]
|
Prev: Is this a valid statement?
Next: lagrange identity
From: Bill Taylor on 24 Nov 2009 00:11 I have two clusters of questions. Conjecture 1: ========== Any countable dense linear ordering with no end-points is order-isomorphic to any other. This is easily proved with AC, is that right? In fact, it only needs DC, is that right? But CC is not sufficient, is that right? (I'd guess this is hard.) _________________ Conjecture 2: =========== Any subset of the reals with the usual ordering, and continuum many elements in every interval, is order-isomorphic to any other. Is this true? Easily proved? If we merely say they must have uncountably many elements in every interval, is it still true - and do we need to assume CH for this? I presume we still need AC for this set of results - is it so? -- Baffled Bill
From: Virgil on 24 Nov 2009 00:51 In article <0b7f88ea-b4bf-4b70-9fe6-0c3cf0a03d45(a)u18g2000pro.googlegroups.com>, Bill Taylor <w.taylor(a)math.canterbury.ac.nz> wrote: > I have two clusters of questions. > > Conjecture 1: > ========== > Any countable dense linear ordering with no end-points > is order-isomorphic to any other. > > This is easily proved with AC, is that right? > > In fact, it only needs DC, is that right? > > But CC is not sufficient, is that right? (I'd guess this is hard.) > _________________ > > Conjecture 2: > =========== > Any subset of the reals with the usual ordering, > and continuum many elements in every interval, > is order-isomorphic to any other. > > Is this true? Easily proved? It is false. Consider the standard reals, R, and the set of non-zero reals, S. Both R and S satisfy your criteria, BUT: Note that in R every set which is bounded above has a least upper bound in R Note that in S there are many sets which are bounded above but which have no least upper bound in S. Since order isomorphisms must carry least upper bounds to least upper bounds, R and S cannot be order-isomorphic.
From: Butch Malahide on 24 Nov 2009 01:00 On Nov 23, 11:11 pm, Bill Taylor <w.tay...(a)math.canterbury.ac.nz> wrote: > I have two clusters of questions. > > Conjecture 1: > ========== > Any countable dense linear ordering with no end-points > is order-isomorphic to any other. A theorem of Cantor, the first use of the famous back-and-forth method. > This is easily proved with AC, is that right? > > In fact, it only needs DC, is that right? > > But CC is not sufficient, is that right? (I'd guess this is hard.) *No* choice is needed, this is a ZF theorem. You don't need the axiom of choice to choose elements from *countable* sets! > _________________ > > Conjecture 2: > =========== > Any subset of the reals with the usual ordering, > and continuum many elements in every interval, > is order-isomorphic to any other. > > Is this true? Easily proved? Blatantly false. The set of all irrational numbers is not order- isomorphic to the set of all real numbers.
From: William Elliot on 24 Nov 2009 04:15 On Mon, 23 Nov 2009, Butch Malahide wrote: > On Nov 23, 11:11�pm, Bill Taylor wrote: >> Any countable dense linear ordering with no end-points >> is order-isomorphic to any other. > > A theorem of Cantor, the first use of the famous back-and-forth > method. > Here's a proof not needing the back and forth method. Top and bottom elements can be added and removed afterwards. Let S = { s0, s1, ... } be a countable linear order with s0 = bottom, s1 = top. Let D = Z[1/2] /\ [0,1] Define f:S -> D by induction: f(s0) = 0, f(s1) = 1 and for k > 1, let bk = max { sj | j < k, sj < sk } tk = min { sj | j < k, sk < sj } f(sk) = (f(bk) + f(tk))/2 It can be show that f is an increasing injection. Now assume that S is dense. To show f is an injection, the following intuitively apparent lemma is needed. If f(sj) = (p-1)/2^m, f(sk) = p/2^m, p,m in N, and sn = s_n in (sj,sk), then j,k < n. To simplify the lemma, let n = min{ n | sn in (sj,sk) } and show j,k < n. That's possible since sj < sk and (S,<=) is dense linear order. I dislike proclaiming by construction, j,k < n. Would you help with proofing the lemma? ----
From: David C. Ullrich on 24 Nov 2009 06:50
On Mon, 23 Nov 2009 22:00:20 -0800 (PST), Butch Malahide <fred.galvin(a)gmail.com> wrote: >On Nov 23, 11:11�pm, Bill Taylor <w.tay...(a)math.canterbury.ac.nz> >wrote: >> I have two clusters of questions. >> >> Conjecture 1: >> ========== >> Any countable dense linear ordering with no end-points >> is order-isomorphic to any other. > >A theorem of Cantor, the first use of the famous back-and-forth >method. > >> This is easily proved with AC, is that right? >> >> In fact, it only needs DC, is that right? >> >> But CC is not sufficient, is that right? �(I'd guess this is hard.) > >*No* choice is needed, this is a ZF theorem. You don't need the axiom >of choice to choose elements from *countable* sets! That last bit is unfortunately phrased - it can happen that you need AC to choose elements from finite sets. What's true is that if S is countable then you don't need AC to choose elements of subsets of S. (Which of course suffices to show that no AC is needed above.) >> _________________ >> >> Conjecture 2: >> =========== >> Any subset of the reals with the usual ordering, >> and continuum many elements in every interval, >> is order-isomorphic to any other. >> >> Is this true? �Easily proved? > >Blatantly false. The set of all irrational numbers is not order- >isomorphic to the set of all real numbers. David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.) |