An uncountable countable set
in [Math]
|
Prev: integral problem
Next: Prime numbers
From: Tony Orlow on 25 Aug 2006 13:23 David R Tribble wrote: > Tony Orlow wrote: >> The more I reflect on that wonderful >> newbie's contribution, the question as to how many bits are required to >> list all the naturals in binary, the more I see it as that gaping hole >> in the hull of this wreck. If set theory claims to have a cardinality >> which fits every set, then this set stands out as the counterexample. >> >> Any finite number of bit positions produces a finite set of strings. >> >> Any countably infinite set of bit positions produces an uncountable set of >> strings. > > Which explains why the reals are uncountable (when represented as > infinite binary fractions in [0,1)). Yes, ala Cantor's second proof of uncountability. > > But it does not explain your claim that the naturals are uncountable > when represented as finite bitstrings. It's pretty straightfoward to > show that a countable number of bits produces a countable number > of bitstrings. There is no "in-between" cardinality. You just contradicted yourself. You agree that [me] "Any countably infinite set of bit positions produces an uncountable set of strings", right? That's what [you] "explains why the reals are uncountable (when represented as infinite binary fractions in [0,1))"?But, [you] "a countable number of bits produces a countable number of bitstrings"? Is a countably infinite number of bits countable or not? If so, then does a countably infinite number of bit positions produce a countable, or an uncountable, set of strings? > > It also flies in the face of your statements about infinite binary > trees. If each node is numbered with a natural (being the finite > bitstring of the left/right paths traversed from the root to the node), > then the nodes, and thus the naturals, are obviously countable. > > On the other hand, you don't understand that the infinite paths in > the tree (the ones that don't have a terminating node) are uncountable > and correspond directly to your infinite bitstrings and to the real > binary fractions in [0,1). > I'll wait for your response on the above, since you're still not ready for the answer you've already heard for this. Please don't snip it. It's a good question, and a prime example of standard issues. Tony
From: Tony Orlow on 25 Aug 2006 13:24 mueckenh(a)rz.fh-augsburg.de wrote: > MoeBlee schrieb: > >> Albrecht wrote: >>> We must conclude that we can only say: we can find infinite many points >>> on a line. This is a potential infinity. >> Do you have axioms for your mathematical theory of potential but not >> actual infinity? > > Five Peano axioms. > > Regards, WM > :)
From: Tony Orlow on 25 Aug 2006 13:33 mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > > >> The set of edges of an infinite binary tree are certainly countable, and >> it is not difficult to construct an explicit bijection between them and >> the set of binary representations of the naturals. >> >> The set of paths, however is not countable, as may is shown by >> constructing an explicit bijection between the set of all such paths and >> the set of all subsets on the set of naturals. >> >> Both the bijections referred to above have been presented here with no >> one able to show either to be anything other than as advertised. > > Ok. Let's accept that. But by rational relation we find the set of > paths being *not* larger > than the set of edges. How is that possible? > > Regards, WM > Did anyone see Harry Potter? I think the spell was called "virgiliamus" or something. ;) For every two new edges, one new path is produced, as with the addition of a new bit to a natural, which can be either 0 or 1. One new natural value is produced, though two new strings. When you continue on the left path, and add a 0, you have not created a new path, nor have you defined a new natural number, when all previous bits in the path have been determined. It is only when you add the next nonzero power of 2 that you get a new value. Tony Tony
From: Tony Orlow on 25 Aug 2006 13:40 mueckenh(a)rz.fh-augsburg.de wrote: > Virgil schrieb: > >> In article <1156189552.184903.323170(a)m79g2000cwm.googlegroups.com>, >> mueckenh(a)rz.fh-augsburg.de wrote: >> >>> Dik T. Winter schrieb: >>> But often some expression like 0.111... is ivolved where not all digit >>> positions can be indexed by natural numbers and n is understood to >>> approach something I do not know. >> Your ignorance is not an acceptable excuse to those of us who have no >> trouble indexing every digit of "0.111..." by a natural number. > > The problem is not indexing but "indexing without covering". > That is easy to prove impossible for any finite natural number in unary > representation. And, alas, there are only finite natural numbers. Alas, my dear Wolfgang, though even countably infinite strings of bits represent finite values, still there are uncountably long sequences which represent actual irrationals and actually infinite naturals. We can extend the field. You'll see. :) > >>> Division was possible and was practised in fact long before rings and >>> fields were known. >> Not outside of what later became known as rings. >> Division of rationals by rationals or reals by reals is quite different. >> So we have no reason to suppose that divisions involving other than >> naturals need behave like division of naturals, or even be possible >> without specific definitions of what it is and how it works.. >> > The old Greek already developed the method of geometric division, using > the so-called Gnomon. This method makes no difference between division > of naturals, rationals, reals or whatever deserves the name "number". > Every well educated mathematician knows it. (Geometry is a certain > language of mathematics.) Thank you very much, Wolfgang, for drawing geometry into the discussion. Though I don't want to tip too much of my hand (as in the game of poker, for those who might not get the analogy), I will say this, and I think it's fundamental. Math comes from the universe. The universe begins with space, vaoid and dark as it may start. Geometry is the foundation for quantity and symbol, and quantity is the foundation of logic. These are the principles that seem to be producing fruit for me in my garden, and the beginning of the story. :) >>> One must have a very restricted mind to believe that without fields and >>> rings division was impossible. >> The set of positive naturals is not even a ring, but it allows at least >> two forms of division, and this has been recognized by most of us from >> well before "Mueckenh". > > Your frequence of self contradicitions increases. You just said "Not > outside of what later became known as rings." Get used to it. Have you and Virgil interacted much? > > Regards, WM > Have a nice day, Tony
From: Tony Orlow on 25 Aug 2006 13:43
Dik T. Winter wrote: > In article <1156500654.035798.315570(a)m79g2000cwm.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > > > > Dik T. Winter schrieb: > > > > > > > You apparently do not know what the word "computable" does mean. To > > > > > be precise: all algebraic numbers are computable in the mathematical > > > > > sense. > > > > > > > > To be precise: Each algebraic number is computable. But not all. > > > > Because then the list of all algebraic numbers was computable. > > > > > > But it is. > > > > So you can compute all solutions of a polynomial equation even of > > higher than fourth degree in finite time? I doubt that. > > I did not state that. I said that the numbers were computable, where > I use the mathematical sense of computable. Such that one can specify which finite number of iterations will get one within a specific finite range of accuracy, gven a specific method of approximation? It's a limit concept, really, yes? Tony |