Uncountability of the Rationals?
in [Math]
|
Prev: Collatz conjecture
Next: Beginner-ish question
From: David R Tribble on 8 Jun 2010 19:39 Tony Orlow wrote: > Remember my big challenge? What > is the width of a countably infinite complete list of digital numbers? It's not clear what you're asking, but if by that you mean, "what is the length of the longest digit sequence in the countably infinite list of all possible finite-length digit sequences?" then the answer is: there is no longest digit sequence in the list. But you already knew that, having been told so dozens of times. If instead you mean, "what is the number of digits required to list all possible finite-length digit sequences?" then the answer is: omega. But you already knew that, too, having been told so dozens of times. > This is the same question as CH. Hardly. Those questions have nothing to do with the CH, nor do they have any need to deal with any ordinal or cardinal greater than omega. -drt
From: David R Tribble on 8 Jun 2010 19:53 David R Tribble wrote: >> Here's a few example sequences: >> S1 = 0, 1, 2, 3, 4, 5, 6, ... >> S2 = 0, 2, 1, 4, 3, 6, 5, ... >> S3 = 0, 2, 4, 6, ..., 1, 3, 5, 7, ... >> S4 = 0, 1, 3, 4, 6, 7, 9, 10, ..., 2, 5, 8, 11, ... >> >> You'll notice that all of these particular sequences are >> *different* (which is why I gave them different names), >> even though they all contain the same values (all of the >> naturals, as it happens, in these examples). > Virgil wrote: > S1 and S2 may be regarded of as sequences (provided the relative > position of each entry is taken as argument for the function providing > the value in that position). > > But even in that limited sense, neither S3 nor S4 is a sequence. Yeah, I had my doubts about S3 and S4, since there is no direct mapping between their elements and N. What do you call it when a sequence has order greater than omega? S3 and S4 could be taken as concatenations of (proper) sequences, but I don't know the terminology. (I'm no expert on this.) At any rate, all of this is lost on Tony.
From: Tony Orlow on 8 Jun 2010 19:53 On Jun 8, 12:51 pm, David R Tribble <da...(a)tribble.com> wrote: > Tony Orlow wrote: > >> What is your personal definition of a sequence, again? > > David R Tribble wrote: > >> Fairly close to the actual definition. Essentially, it's a > >> set that maps the naturals to a function (a function being > >> a set itself, of course, within set theory). > > >> Here's a few example sequences: > >> S1 = 0, 1, 2, 3, 4, 5, 6, ... > >> S2 = 0, 2, 1, 4, 3, 6, 5, ... > >> S3 = 0, 2, 4, 6, ..., 1, 3, 5, 7, ... > >> S4 = 0, 1, 3, 4, 6, 7, 9, 10, ..., 2, 5, 8, 11, ... > > >> You'll notice that all of these particular sequences are > >> *different* (which is why I gave them different names), > >> even though they all contain the same values (all of the > >> naturals, as it happens, in these examples). > > Tony Orlow wrote: > > By the axiom of extensionality, as sets they are identical. > > No, they are not. Each sequence is a *different* set. > > I'll use a more expressive notation to depict these sequences > as actual sets: > > S1 = {<0,0>, <1,1>, <2,2>, <3,3>, <4,4>, <5,5>, <6,6>, ...} > S2 = {<0,0>, <1,2>, <2,1>, <3,4>, <4,3>, <5,6>, <6,5>, ...} > > This notation shows more clearly the mapping between the > naturals and the values of each sequence. In a purer (but > harder to read) set notation, each '<a,b>' pair would be written > as '{a, {b}}', or something similar. > > I've only bothered to show the first two sequences (the rest being > slightly more complicated since they are concatenations of > subsequences), but it's plainly obvious that they are all *different* > sets. Different sequences, thus different sets. > > And to be even more instructive, here are two more different ways to > write sequence S1 as a set: > > S1 = {<1,1>, <0,0>, <3,3>, <2,2>, <5,5>, <4,4>, <6,6>, ...} > S1 = {<3,3>, <4,4>, <5,5>, <0,0>, <1,1>, <2,2>, <6,6>, ...} > > All three ways of writing S1 are different, but the set itself is > exactly the *same* for all three. > > Again, and it bears repeating, by themselves *sets have no order*. > They are just collections of their members. Better to think of them > as special kinds of bags or sacks than as lists or sequences. > > Really, Tony, these concepts are very, very simple. My > explanations are pretty easy to follow. I don't claim to be an > expert in these matters, but these ideas are so simple I don't > have to be in order to understand and explain them. > > > As sequences they differ. If a sequence contains the same members as > > another which is monotonically increasing, then that other can be used > > to calculate the bigulosity of both sets/sequences. > > If you say so, but what if they don't? Can you calculate the > (relative?) "bigulosity" between S1 and S2? > > -drt- Hide quoted text - > > - Show quoted text - Yeah I get all that. What is your point? By the axiom of extensionality they are the same set with different order. Yes, it's a relation between N and the countably infinite set. So? Did you invent that all by yourself? That's very good Davey. Tony
From: David R Tribble on 8 Jun 2010 20:09 MoeBlee wrote: >> WHAT exact ordering on sets in GENERAL do you mean '<' to stand for? > Tony Orlow wrote: > I was referring to sets of real (or hyperreal) quantities, specifically. But then what about other ordered sets containing members other than reals, hyperreals, naturals, or numbers at all? Does your "bigulosity" still apply to them, in general? For example, consider the sets constructed from the "primitive" element 'o'. Some examples: T1 = { o } T2 = { o, {o} } T3 = { o, {o}, {{o}} } Likewise consider some infinite sets built in this same way: R1 = { o, {o}, {{o}}, {{{o}}}, ... } R2 = { o, {{o}}, {{{{o}}}}, {{{{{{o}}}}}}, ... } Now we'll define an order relation '<' for these particular sets. We define o < {o}. So in general, o < {o} < {{o}} < {{{o}}} < {{{{o}}}} < ... Now we can see that all of the sets above can be ordered sets, using our new '<' relation. So the question is, given these ordered sets, can you calculate the relative bigulosity for them? Specifically, does R1 have a larger or smaller bigulosity than R2? -drt
From: Tony Orlow on 8 Jun 2010 21:46
On Jun 8, 7:39 pm, David R Tribble <da...(a)tribble.com> wrote: > Tony Orlow wrote: > > Remember my big challenge? What > > is the width of a countably infinite complete list of digital numbers? > > It's not clear what you're asking, but if by that you mean, > "what is the length of the longest digit sequence in the countably > infinite list of all possible finite-length digit sequences?" > then the answer is: there is no longest digit sequence in the list. > But you already knew that, having been told so dozens of times. > > If instead you mean, > "what is the number of digits required to list all possible > finite-length digit sequences?" > then the answer is: omega. > But you already knew that, too, having been told so dozens of times. > > > This is the same question as CH. > > Hardly. Those questions have nothing to do with the CH, nor > do they have any need to deal with any ordinal or cardinal greater > than omega. > > -drt Yes, it is directly related to CH, except that it addresses the question of what lies between the finite and countably infinite. It is generally accepted that a countably infinitely wide complete list of digits contains all reals within the range of its greatest digit (between 0 and 1 for digits from -1 down, for instance). Thus, aleph_1 is taken to be 2^aleph_0 (in binary) or x^aleph_0 in base x. Any list of finite length can contain only a finite number of distinct strings. A countably infinitely wide list has an uncountable number of strings. What width would be required of a complete list of base-x strings which is countably infinitely long? This question is whether there exists an infinity less than aleph_0, as opposed to one between aleph_0 and c, but is essentially the same type of question. The answer is, as long as the number of digits is countable, so is the number of strings. There is no finite formulaic relationship between the countably infinite and the uncountably so. The width of such a list can only be properly expressed as a function on N. JMHO Tony |