Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Virgil on 26 Jan 2007 15:13 In article <1169803486.538431.93450(a)s48g2000cws.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > On 24 Jan., 21:16, Franziska Neugebauer > <Franziska-Neugeba...(a)neugeb.dnsalias.net> wrote: > > > > > > 1) Every complete infinite binary tree T (containing all nodes and > > > edges) contains all paths. > > > No we cannot say so. Please define "contains" first. > > In my definition, a tree has the special structure which I will not > repeat as you know it. Therefore the tree T(n) is well-defined by its > nodes alone. Except that WM's "nodes" are not mere nodes but are nodes containing infiormation on how they are connected to other nodes by edges, i.e., WM has secreted the set of edges inside his set of nodes so that it is invisible to the eye but still there. > If you wish we could use different symbols for the tree > and for its set of nodes, but I do not consider this necessary or > useful (cp. the case omega and aleph_0). In honest trees, the connections between nodes are not secreted, as in WM's trees, but openly available as a set of edges or a set of paths. > As I defined only trees with > paths of equal length, we distinguish trees not by single nodes but by > subsets of the set of nodes which are called levels, denoted by L(n). > Definition of a level is obvious. That only means that every path in the tree is of the same finite length. > > Definition 1: Tree T(n) is contained in tree T(m) if the set of nodes > T(n) is a subset of the set of nodes T(m), i.e., if n =< m. This only works for WM trees, as for honest trees one also needs to state explicitly that the set of edges of T(n) is a subset of the set of edges of T(m) and that the root node of T(n) is the same as the root node of T(m) in order to have the sort of "union" WM envisages. > > This definition is sufficient to include every m,n in N. Notice: It > does not include N. I do not cosider N a natural number. But every > level of the tree is mapped by a natural number, hence for every level > L(n) we necessarily have n =/= N. > > As a tree T is a set of nodes And a set of edges > and a path P is a set of nodes, But only those very special sets of nodes which all include a root node and all include exactly one edge-linked child node for every parent node in that path. > the > definition of "contains" with respect to trees and paths is now > obvious: P c T. Except that WM's definitions are all so mathematically unsatisfactory that one is never certain of what is going on. > > No. I do not read the writings of such writers. I commit to my > definition, again outlined above. In which , for instance, a node is not a mere object but an object with necessarily built in, but hidden from view, connections to other objects in the set of nodes. > > > We cannot say so. *In* std-trees there no paths. The set of paths is > > induced by the tree. > > The trees which I use, uniquely define their paths, which are in these > trees. How is having the set of paths "induced" by the tree different from having them "defined" by the tree? Does one get a different set of paths? > > Are you really not able to understand that the set of real numbers is > proven countable if the set of real numbers in some interval is proven > countable? WM apparently cannot understand that the set of real numbers is proven uncountable if the set of real numbers in some interval is proven uncountable! And proofs that the set of reals in [0,1] is uncountable are ubiquitous, however carefully WM avoids acknowledging them.
From: Andy Smith on 26 Jan 2007 15:20 davidmarcus(a)alum.mit.edu writes > >> >> >Showing that one particular mapping fails to be a bijection is not >> >sufficient. It doesn't rule out the possibility that some other mapping >> >might be a bijection. The point of the diagonal argument is that >> >addresses all possible mappings f: N->R at once, by showing that each one >> >fails to be a bijection. > >> The point of that argument was intended precisely to show that if a >> particular arrangement or the reals is countable, then any arrangement >> is countable, and vice-versa, if a specific ordering of the reals is >> uncountable, then any arrangement is. I think that is probably not very >> controversial? > >You are misusing the word "order". And, you seem to be using >"arrangement" as a synonym for "order". To you, an order or arrangement >seems to be a listing. To us, it means that pi is less than 4 (for >example). With our meaning, it is obvious that order has nothing to do >with countability. With your meaning, it is false. If you have a >listing of all the reals, then the reals are countable. If no listing >of all the reals is possible, then the reals are uncountable. But, if >you have a listing that includes some reals, but not all, then this >tells you nothing about whether the reals are uncountable. For example, >here is a listing of some reals: > >0.1 >0.01 >0.001 >... > >Do you agree? > Yes, sorry for any confusion. From your previous post re permutations, I thought that there was some issue concerning the order in which in the reals were (prospectively) to be indexed. If you think (as I originally thought) that if any one "arrangement" of the reals is countable then any arrangement is countable, and alternatively, if that one can show that a specific "arrangement" cannot be counted, then no arrangement can be. My proposed systematic counting scheme for the reals (as illustrated by you in decimal notation) was systematic precisely to ensure that it was guaranteed to pick up all the reals en route (and of course it doesn't work). >> >> even if one buys the argument above, there is still an issue as to >> >> whether the failure of the counting scheme might not be circumvented by >> >> some other means i.e. does the failure of the counting scheme show that >> >> the reals taken in that order are truly uncountable. >> >> >Uncountability has nothing to do with order. > >> Just so, but not necessarily obvious? > >With our meaning of the words, obvious. > Well I had thought so to, until your earlier post, and hence my earlier response. If a specific arrangement of the reals can be shown to be uncountable, there exists no possible arrangement in which they will be countable. "Obvious", but I thought that was what was being questioned... regards -- Andy Smith
From: MoeBlee on 26 Jan 2007 15:25 On Jan 26, 5:02 am, Andy Smith <A...(a)phoenixsystems.co.uk> wrote: > Sure, I just meant that if there was an injection R->N, then there would > be a 1:1 and onto correspondence between N and the elements of R taken > in any order that we chose. "Order that we chose"? What is that? > >But there is a quite natural one-to-one mapping (injection) N->R. The > >point is that there is no injection going the other way, and from this we > >conclude that there is no bijection. > This is still following on from trying to show that the reals are > uncountable based on trying to count them systematically, showing that > that fails in that instance, and trying to infer that there is no > injection R->N. (because, for me at any rate, that is a direct approach, > and would provide an explanation meaningful to me as to why the reals > are uncountable). We show there is no function from N onto R. That is the case no matter your concerns about "count systematically", whatever that means. There is no function from N onto R. That's the irrevocable verdict as we prove. > even if one buys the argument above, there is still an issue as to > whether the failure of the counting scheme might not be circumvented by > some other means i.e. does the failure of the counting scheme show that > the reals taken in that order are truly uncountable. That kind of musing reflects a very basic lack of understanding the logic of mathematical proof. Universal generalization is what we use. We talk about an ARBITRARY f from N into R and show it cannot be onto. Since f is ARBITRARY, we conclude that ALL functions f are such that it is not from N onto R. > I would say yes, > because there is no scope for any more compact non-infinite > representation of the reals than their infinite binary expansions. You're on a wild goose chase. You need to understand the logic of the proof. MoeBlee
From: MoeBlee on 26 Jan 2007 15:33 On Jan 26, 7:35 am, Andy Smith <A...(a)phoenixsystems.co.uk> wrote: > The point of that argument was intended precisely to show that if a > particular arrangement or the reals is countable, then any arrangement > is countable, and vice-versa, if a specific ordering of the reals is > uncountable, then any arrangement is. I think that is probably not very > controversial? It's not even clear what you mean. What does "an arrangement is countable" mean? I could impose a meaning on it, such as "an ordering, as a set of ordered pairs, is a countable", but I doubt that's what you mean. > For me, at this moment, I would say > that the reals are uncountable because they are infinite, have a > necessarily infinite binary expansion. That is more than you get from > Cantor's diagonalisation argument? It's not enough. Yes, there are infinitely many reals. And, yes, each real is matched with a certain denumerable sequence. But then we still have to prove that there is no bijection between N and R. And that's what the diagonal argument does. MoeBlee
From: Andy Smith on 26 Jan 2007 15:52
Dave Seaman <dseaman(a)no.such.host> writes > (snip) (I think that the other points/misunderstandings subsequently addressed?) > >What is a "necessarily infinite binary expansion"? Doesn't 1/3 have a >"necessarily infinite binary expansion"? Aren't there infinitely many >rationals having such expansions? Does this mean the rationals are >uncountable? > Copied from an earlier post by me in response to DM, if you didn't see it: > Well as I saw it the point is a) if you could index some permutation of the set of the reals you could necessarily index all of them - they would all be indexed, and you can permute the indices and their corresponding reals as you like, and b) if you can't index a given 1 permutation of the reals you can't index any. On reflection, maybe some finite/infinite dubious logic there... But, there is no scope for any compression of representation with the reals. If you have m bits, you have 2^m numbers, however you arrange them. Of course, if you take a subset e.g. the rationals (which are also reals with a necessarily infinite binary representation (so as to distinguish them from other members of the address space that they occupy)) then there is scope for compression, such that they do not have an infinite representation. e.g. you can represent a rational in [0,1] by <c>.<h><r> where <r> is a string of bits <c> long, repeating indefinitely, and <h> is some header string of bits. >The diagonal argument has the advantage of being valid. Your argument >does not. > > Yes, and maybe. But I still would like a clear statement like "the reals are uncountable because they are infinite (require an infinite binary expansion/representation)". Or some alternative explanation. Doubtless Cantor's proof is valid, it's been looked at by experts for a hundred years, but I would like to see something more immediate. -- Andy Smith |