Dense Linear Ordering problems.
in [Math]
|
Prev: Is this a valid statement?
Next: lagrange identity
From: Butch Malahide on 24 Nov 2009 13:45 On Nov 24, 5:50 am, David C. Ullrich <dullr...(a)sprynet.com> wrote: > On Mon, 23 Nov 2009 22:00:20 -0800 (PST), Butch Malahide > > > > > > <fred.gal...(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.) Good point. Thanks for the correction.
From: Bill Taylor on 25 Nov 2009 23:05 A thank-you to gentle Butch, and others who responded. Butch Malahide <fred.gal...(a)gmail.com> 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. *No* choice is needed, Of course! Silly me, I should have seen that myself. ....................... > > Any subset of the reals with the usual ordering, > > and continuum many elements in every interval, > > is order-isomorphic to any other. > Blatantly false. Of course; now let me update it with the question I *meant* to ask! Consider subsets of the reals such that both the subset and its complement are continuum many in every interval. Are any two such subsets order-iromorphic? I know that one can produce set-pairs like that which are of zero/full measure, or which are full/sparse category; but I'm not sure if that necessarily prevents them from being order-isomorphic. -- Wondering William
From: Butch Malahide on 26 Nov 2009 04:27 On Nov 25, 10:05 pm, Bill Taylor <w.tay...(a)math.canterbury.ac.nz> wrote: > > Consider subsets of the reals such that both the subset and > its complement are continuum many in every interval. > > Are any two such subsets order-isomorphic? [Spelling typo corrected.] No, but the counterexample won't impress you, because it uses AC. Since you're not going to accept the example anyway, I'll just sketch the argument. Recall that a subset of R is "totally imperfect" if it contains no perfect set (and therefore no uncountable Borel set of any type.) Use AC to obtain a so-called Bernstein decomposition of R, i.e., a totally imperfect set A whose complement B = R\A is also totally imperfect. (Needless to say, they are nonmeasurable sets.) Of course each of the sets A and B contains continuum many points in every interval. As far as I know, A and B may be order-isomorphic. Now, let C be the Cantor set, and consider the set X = A union C and its complement Y = B\C. The modified sets X and Y still contain continuum many points in each interval. I claim that X and Y are not isomorphic. To see this, observe that X contains a subset which is order-isomorphic to R (in fact C contains such a subset), while Y, being totally imperfect, contains no subset order-isomorphic to R.
From: David C. Ullrich on 26 Nov 2009 11:15 On Thu, 26 Nov 2009 01:27:20 -0800 (PST), Butch Malahide <fred.galvin(a)gmail.com> wrote: >On Nov 25, 10:05�pm, Bill Taylor <w.tay...(a)math.canterbury.ac.nz> >wrote: >> >> Consider subsets of the reals such that both the subset and >> its complement are continuum many in every interval. >> >> Are any two such subsets order-isomorphic? [Spelling typo corrected.] > >No, but the counterexample won't impress you, because it uses AC. A counterexample that depends on AC _should_ be of interest even to people who don't "accept" AC! If AC implies that there is no gazebo then it follows, whether one accepts AC or not, that the existence of a gazebo cannot be proved in ZF. >Since you're not going to accept the example anyway, I'll just sketch >the argument. > >Recall that a subset of R is "totally imperfect" if it contains no >perfect set (and therefore no uncountable Borel set of any type.) Use >AC to obtain a so-called Bernstein decomposition of R, i.e., a totally >imperfect set A whose complement B = R\A is also totally imperfect. >(Needless to say, they are nonmeasurable sets.) Of course each of the >sets A and B contains continuum many points in every interval. As far >as I know, A and B may be order-isomorphic. Now, let C be the Cantor >set, and consider the set X = A union C and its complement Y = B\C. >The modified sets X and Y still contain continuum many points in each >interval. I claim that X and Y are not isomorphic. To see this, >observe that X contains a subset which is order-isomorphic to R (in >fact C contains such a subset), while Y, being totally imperfect, >contains no subset order-isomorphic to R. 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.)
From: Virgil on 26 Nov 2009 14:56
In article <m9atg5h0jvcun23n7oj9dq286ut82i9ti2(a)4ax.com>, David C. Ullrich <dullrich(a)sprynet.com> wrote: > On Thu, 26 Nov 2009 01:27:20 -0800 (PST), Butch Malahide > <fred.galvin(a)gmail.com> wrote: > > >On Nov 25, 10:05�pm, Bill Taylor <w.tay...(a)math.canterbury.ac.nz> > >wrote: > >> > >> Consider subsets of the reals such that both the subset and > >> its complement are continuum many in every interval. > >> > >> Are any two such subsets order-isomorphic? [Spelling typo corrected.] > > > >No, but the counterexample won't impress you, because it uses AC. > > A counterexample that depends on AC _should_ be of interest > even to people who don't "accept" AC! If AC implies that > there is no gazebo then it follows, whether one accepts > AC or not, that the existence of a gazebo cannot be proved > in ZF. Nice! And nicely sneaky!! > > >Since you're not going to accept the example anyway, I'll just sketch > >the argument. > > > >Recall that a subset of R is "totally imperfect" if it contains no > >perfect set (and therefore no uncountable Borel set of any type.) Use > >AC to obtain a so-called Bernstein decomposition of R, i.e., a totally > >imperfect set A whose complement B = R\A is also totally imperfect. > >(Needless to say, they are nonmeasurable sets.) Of course each of the > >sets A and B contains continuum many points in every interval. As far > >as I know, A and B may be order-isomorphic. Now, let C be the Cantor > >set, and consider the set X = A union C and its complement Y = B\C. > >The modified sets X and Y still contain continuum many points in each > >interval. I claim that X and Y are not isomorphic. To see this, > >observe that X contains a subset which is order-isomorphic to R (in > >fact C contains such a subset), while Y, being totally imperfect, > >contains no subset order-isomorphic to R. > > 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.) |