Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: imaginatorium on 25 Jan 2007 06:59 Andy Smith wrote: > David Marcus <DavidMarcus(a)alumdotmit.edu> writes > >> > > >> If you want to index 2^n numbers, you require 2^n indices. You require > >> as many bits to define your indices as log(no of numbers,base 2). With > >> the reals defined as an infinite series of bits, you require an infinite > >> series of bits to define your indices. > > > >Bzzt. Not proven. Why doesn't the same argument prove that the set > > > > {sqrt(2)/n | n = 2,3,4,...} > > > >is uncountable? Each of the numbers in the set does not have a finite > >decimal representation. > > > >And, it the number of numbers is infinite, your formula log(no of > >numbers,base 2) is meaningless. > > > I said I am going to quit this NG for a bit and I will, but I am not > letting this one go. > > With respect you are not paying attention, and in this instance you make > a category error, confusing the map with the territory. Just because I > am a nitwit doesn't mean that everything I say is rubbish... I think the implication you refer to is indeed false, and I rather agree that DM's contribution doesn't seem relevant. OTOH, perhaps he just interprets you as meaning something different from what I do. > I said (and this ought not to be controversial) that if you have n > objects you need an address space defined by log(no of items, base 2) to > index(i.e. count) them. It isn't controversial, provided that n is a natural number, i.e. that the set of these things to be indexed is finite. > In your example, A n e N you need an address space of log(n,2) bits. The > address space is finite for all finite n. > > When I talked about the reals, I will say it again: > > 1) Any systematic method for counting the reals is equivalent (you would > probably say isomorphic under permutation). Not sure what this means - but since the reals are not countable, you must be using "count" in an unusual sense. > 2) I proposed to try to count the reals by progressively increasing the > degree of precision of their representation. To n bits precision, there > are 2^n distinct numbers, requiring 2^n indices. If I wish I can > represent a unique set of indices covering this space by e.g. reflecting > the bit pattern of the reals to the first n bits about the binary point. > > 3) For all finite n, no problem. The set of indices are finite, and this > basically is just indexing (a subset of) the rationals. However the > reals require an infinite n and cannot be represented with indices with > a finite number of bits. (Aristotle would say that the natural numbers > are potentially infinite, but the reals are actually infinite). How do you know what Aristotle would say? Here's the difference in indexing: (For anyone who isn't watching carefully, a registe is a register with only one end) (1) To represent all of the naturals requires a registe, because no (two-ended) register is big enough to represent all of them. (2) To represent all of the reals requires a registe. Actually a registe is required for many individual reals (irrationals, etc.). (3) It is true that for any particular natural number there is a register that can hold it, but those without quantifier dyslexia will see that this does not contradict (1). So let's try to understand your paragraph: > 3) For all finite n, no problem. What is n *exactly*? It seems to be "the number of reals/naturals in the subset I've counted so far". So this just says "no problem with finite subsets of reals or naturals". Fine. > The set of indices are finite, ... The grammatical infelicity is symptomatic. Do you mean "The set of indices _is_ finite"? Anyway... > The set of indices [is] finite, and this > basically is just indexing (a subset of) the rationals. However the > reals require an infinite n and cannot be represented with indices with > a finite number of bits. I'm lost already. What is this "n" that the reals require it to be infinite, in a way that plausibly the naturals say don't? The set of reals is infinite - it goes on forever, and the set of bit positions required to represent all reals is also infinite - it goes on forever, and exactly the same is true of the natural numbers. > (Aristotle would say that the natural numbers > are potentially infinite, but the reals are actually infinite). So why on earth would he say this, and what does it mean in mathematical terms? Brian Chandler http://imaginatorium.org
From: William Hughes on 25 Jan 2007 07:39 On Jan 25, 3:19 am, mueck...(a)rz.fh-augsburg.de wrote: > On 24 Jan., 14:41, "William Hughes" <wpihug...(a)hotmail.com> wrote: > > > On Jan 24, 6:58 am, mueck...(a)rz.fh-augsburg.de wrote: > > > > I guess you have a different definition for the union of all finite > > > > trees. > > > > > Let R be a set of finite trees with the property that: > > > > there is a (fixed) tree t_D in R, such that: > > > > if s is in R, then > > > > s is a subtree of t_D > > > > > Definition i:Here you snipped both definitions that I gave without > > noting this fact. Naughty! I will restore this section.Sorry. Both definitions are not my definition and are of no relevance > in further discussion. > > > > > > > Definition i: > > > The union of all finite trees in R is > > the tree t_D. (Note that using this definition, > > the union of all finite trees in R is a finite tree.) > > > Defintion i': > > > The union of all finite trees in R > > is a set of paths, S, where S contains any > > path that is in a tree in R. (Note that i and i' > > are almost equivalent.) > > > Now let W be the set of all finite trees. > > We know that there does not exist a (fixed) t_D > > in W such that every tree in W (that is > > every finite tree) is a subtree of t_D. So > > we cannot use definition i. Instead I use > > definition i'. By definition i', T1 contains > > every finite path.I do not use your definitions. Further you introduced new symbols. > which might confuse lurkers. Therefore I snipped them, now with notice. > > > > > > > The union of all finite treesis the tree which has all nodes and edges which are in at least one > > > finite tee.As I noted, you have a different definition for the union of all finite > > trees. > > > As before, let the set of all finite trees be W. > > Let P1 be the set of all finite paths, that is if p is > > an element of P1, then there is a tree t in W, such > > that p is a path in t. > > > We will adopt your definiton of the union of all finite > > trees. Under this definition the union of all finite trees, T1, > > is the infinite tree T2.Of course. Denote it better by T(oo) = T. > > > However, the set of paths in T1 is > > not the union of paths in P1. Each path in T1 is the limit of a > > sequence > > of paths from P1. Union and limit are two > > different things.Due to the schism "infinite set of finite numbers" there are two > answers possible (but not more). > 1) If we identify path-lengths with natural numbers, then there is no > infinite path in any of the finite trees, because there is no infinite > natural number. Therefore, also the union of all finite trees cannot > contain an infinite path. Clearly the tha path-length of an infinite path cannot be a natural number. We are left with > 2) If we identify path-length with sets of natural numbers, then there > are infinite paths in the union tree T(oo). >However, if L is a set of > limits L_k > L = { L_k | k in N } L is the set of finite limits. L is countable. Note that the set L does not contain an infinite limit. > and S is the set of corresponding sequences > S = { a_1k, a_2k, a_3k, ... | a in {0, 1}, k in N } > then L cannot be larger than S, because there cannot be more limits > than sequences. Note that S contains only infinite sequences. S can be and is larger than L. S is not countable. > Different limits for one sequence would mean a path > splitting at a level n beyond any natural number, i.e., n not in N. > This is not only impossible but would also lead to undefined limits. > > Therefore, even if union and limit are two different things (due to the > schism), both things lead to countably many paths in T(oo). > No. The set of paths in T(oo) is the set of sequences S. This set is not countable. -William Hughes
From: Dik T. Winter on 25 Jan 2007 07:44 In article <1169714020.350577.110980(a)q2g2000cwa.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: .... > > No, you have not shown it. But I have given some definitions that *do* > > show it. This can only be done if a tree is *defined* as a set or as > > a collection of sets. For other obejcts than set the concept of union > > is not defined. > > The tree is a collection of sets, namely the collection of levels L(n) > as well as the collection of subtrees like T(n) = L(0) U L(1) U ... U > L(n). The tree is also a set. Its elements are nodes. A path is a > subset with the special property that it contains all nodes which go > from top to the end or, in case there is no end, continue to go on. So now back to the largest paths again. In that case the union of the sets of paths in two different trees is not the set of paths in the union tree. If tree T1 contains the path {a, b, c} and T2 contains the paths {a, b, c, d}, the union of T1 and T2 contains the path {a, b, c, d} but the union of the set of paths in T1 and the set of paths in T2 contains both {a, b, c} and {a, b, c, d}. > > > 3) The union of all finite trees includes the union of all nodes and, > > > with it, the union of all such subsets which are paths (because every > > > path is a well defined subset of the set of nodes if the structure of > > > the tree is well defined). > > > > If a tree consists (amongst others) of the set of nodes in it, the union > > of two trees indeed consists (amonst others) of the union of the sets of > > nodes. > > I agree. But this union may not be intermingled with pair-axiom. The > union of two or more paths is a set of nodes which can but need not be > a path. But you are talking about the union of *sets* of paths. > In the tree T(1) > a > /\ > b c > There are two paths, namely p1 = {a, b} and p2 = {a, c}. By pair axiom > we get a set {p1, p2} containing two paths as elements. The union p1 U > p2 = {a, b, c}, however, is not a path. > > The tree T(0) = a contains only one path p(0) = a. The union of p(0) > and p(1) is a path, namely p(1). But note that the union of the sets of paths in T(0) and T(1) is the set of paths: {p0, p1, p2}. So the set of paths in a union is *not* the union of the sets of paths. > > > 4) The set of paths in T(oo) is a subset of the countable set of finite > > > sets of all paths in the finite trees. > > > > As worded this is trivially wrong: it states that "the set of paths in > > T(oo) is one of the set of finite sets of all paths in finite trees", > > or "the set of paths in T(oo) is the set of paths in one of the finite > > trees". > > I need not specify and do not specify how the paths in T(oo) come in. I > merely express that some paths like 0.010 belong to one set of paths > (namely those of tree T(3)) but do not belong to the set of path in > T(oo). > T(oo) contains no paths which are only initial segments of paths of > T(oo). That it not what is stated there. Your wording was wrong, see below. > > I think you mean: > > 4) The set of paths in T(oo) is a subset of the countable union of > > finite sets of all paths in the finite trees. > > Yes. But due to the schism "infinite set of finite numbers" there are > two answers possible (but not more). > 1) If we identify path-lengths with natural numbers, then there is no > infinite path in any of the finite trees, because there is no infinite > natural number. Therefore, also the union of all finite trees cannot > contain an infinite path. > 2) If we identify path-length with sets of natural numbers, then there > are infinite paths in the union tree T(oo). However, if L is a set of (1) if you allow infinite paths (as you do) you can *not* identify path-lengths with natural numbers. (2) you can identify path-lengths with *ordinal* numbers (this also allows for the zero-length path. However in some models the ordinal numbers up to, and including, omega can be represented as sets of natural numbers. So that is the way to go. > However, if L is a set of > limits L_k > L = { L_k | k in N } > and S is the set of corresponding sequences > S = { a_1k, a_2k, a_3k, ... | a in {0, 1}, k in N } This can not be S because you define S as a set of digits, not of sequences. Properly done I get somethink like: S_k = { a_1k, a_2k, a_3k, ... } with a in {0, 1} and k in N S = { S_k | k in N } > then L cannot be larger than S, because there cannot be more limits > than sequences. Yes. What is the relevance? If you have countably many sequences, you have countably many limits. But you are thinking that you have countably many sequences, and so have to prove that. As S above is precisely the list from Cantor's proof, we know that S does not contain *all* possible sequences. > Different limits for one sequence would mean a path > splitting at a level n beyond any natural number, i.e., n not in N. There are no different limits for one sequence. > > But this is also wrong. > > No. When unioning the trees we union also their subsets, including > their paths. What do you mean with this? The answer is probably "yes". But this does *still* not make the union of the *sets* of paths the *set* of paths of the union. > A subset of a tree is a path if and only if all its elements (nodes) > are connected by edges. > The union of two paths is a path if and only if all its nodes are > connected by edges. (See the examples above.) Yes, but this is all irrelevant for the *set* of paths. > The set of paths in T(oo) consists of unions of paths. Ah, perhaps yes, but badly worded. > It cannot > contain contain more paths than were unioned, i.e.,countably many. But this is, eh, also correct. Still that makes it *not* the union of countably many *sets* of paths. > > An easier example. P(x) denotes the powerset of > > set x, i.e. the set of subsets. We have: > > N = U[n in N] {1, 2, ..., n} > > P(N) !subset U[n in N] P({1, 2, ..., n}) > > so the union of the sets of subsets is not the set of subsets of the union. > > But the union of all elements of the powerset is N. U(U P(N))) = N. That notation is wrong in many ways. I would write it as: U ( A in P(n)) = N. > But the union of all elements of the powerset is N. U(U P(N))) = N. So > the union of two or more paths are nodes. Eh? The union of two or more paths is a set of nodes. > > > 5) A countable union of countable sets is a countable set (according to > > > ZF with AC). > > > ==> The set of all path is countable. (==> The real numbers are > > > countable.) > > > > The statement is correct, but what you state does follow, does not follow. > > The set of all paths is *not* the countable union of countable sets of > > paths. > > The set of all paths in T(oo) is not the union but only a subset of the > countable union of countable sets of paths. No, you have not proven that. You use in the union the *sets* of paths in the finite trees. As none of those sets contains an infinite path their union also does not contain an infinite path. > > > 6) T(oo) = T contains only finite paths. > > > 7) T(oo) = T contains all paths including all infinite paths. > > > > By your definition (paths are specific subsets of nodes), T contains > > infinite paths. Conclusion (6) is false. On the other hand, the > > union of the sets of paths contains only finite paths. And they are > > countable indeed. > > If T(oo) = T concerning the set of nodes and edges, then they are > identical with respect to paths to. I do not contradict that. > There is no further parameter to > fix. If you do not accept this identity, then further discussion is not > meaningful. Then you may maintain ZFC and may say that it is free of > contradictions, but you must tolerate that a unique structure may yield > different results, i.e. is not unique. Well, as I do not contradict that, this remark has no value. > > > But not the union of the trees T1 and T2. The union contains only the > > > path {a, b, c, d, e}. > > > > But you are talking about the union of sets of paths. > > No, no, no! Eh? You stated: > > > 4) The set of paths in T(oo) is a subset of the countable set of finite > > > sets of all paths in the finite trees. Which is in itself nonsense. But if we elide "of finite sets" it makes sense, but is wrong. Also if we change "countable set" to "countable union" it makes sense, but still is wrong. Note that: the countable set of all paths in the finite trees is identical to the countable union of finite sets of all paths in the finite trees. So both changes make it a sentence that can be interpreted, but is still wrong. And in both cases you are actually talking about the union of sets of paths. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: Dik T. Winter on 25 Jan 2007 08:46 In article <1169728742.271970.13430(a)v33g2000cwv.googlegroups.com> "William Hughes" <wpihughes(a)hotmail.com> writes: > On Jan 25, 3:19 am, mueck...(a)rz.fh-augsburg.de wrote: .... > > and S is the set of corresponding sequences > > S = { a_1k, a_2k, a_3k, ... | a in {0, 1}, k in N } > > then L cannot be larger than S, because there cannot be more limits > > than sequences. > > Note that S contains only infinite sequences. S is not a set of sequences. S is an ordered multi-set of the digits 0 and 1. Or, alternatively, S is one of the sets {0, 1}, {0} or {1}. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
From: mueckenh on 25 Jan 2007 09:33
On 24 Jan., 21:42, Virgil <vir...(a)comcast.net> wrote: > > T = T(oo). > Only if one also requires that it have every path that can be > constructed from those nodes and edges. So a countable set can get an uncountable set by your *requirement*? > > A set of nodes is not enough. For a set of only three nodes, > there are at least 3 different binary trees which can be formed, 6 if > one counts mirror images as distinct. For trees as I defined them this is wrong. There is but one cut tree with 3 nodes, namely 0. /\ 0 1 Please stay to my definition when discussion my proof. Or indicate that you are discussion something else which mght be of interest to somebody else. > > > 4) The set of paths in T(oo) is a subset of the countable set of finite > > sets of all paths in the finite trees. >Often claimed, but never proved by WM, and often disproved by others. but only by such who deny the law of cause and effect in mathematics. Trying to establish some fuzzy set theory? > > But in either case, we have no problem with the existence of the > sequence itself. Only because you have no problem with thought craft, telekinesis and that stuff. > Conclusion: By finite induction, for all n in N, the pseudo-union of > binary trees of max path length up to n is a finite binary tree. > Of course. Every natural number is a finite number. Why do you think induction would not reach every finite number? > One never gets to any infinite pseudo-unions in such standard inductive > arguments. Do you know why this is so? There are only finite numbers. They do not lead to an infinte number of numbers. One never gets to any infinite union by standard inductive arguments. You have said it. You know i5t. You know why it is so and why it cannot be else. You only resist to admit that it is so. Regards, WM |