Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Virgil on 25 Jan 2007 17:51 In article <1169740568.082762.116480(a)v33g2000cwv.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > On 25 Jan., 15:57, Franziska Neugebauer > <Franziska-Neugeba...(a)neugeb.dnsalias.net> wrote: > WM ] > > | The union of two natural numbers is defined to be the larger one. > > | This is a set theoretic union. > > `---- > > > > So the union of two natural numbers is _not_ defined to be the larger > > one but the "larger" of two distint naturals (sets) a and b is defined > > to be a iff > > > > b c a > > > > or b iff > > > > b c a. > > > > So the order _is_ relevant to successfully prove you wrong. > > The union of two different natural numbers is defined to be the larger > one. Provided that each natural is required to be a set, which is not always the case. There are systems in which a natural number is an equivalence class of bijectable sets, whose union is certainly not a natural number in any sense.
From: davidmarcus on 25 Jan 2007 19:09 On Jan 25, 12:45 pm, G. Frege <nomail(a)invalid> wrote: > On Thu, 25 Jan 2007 12:27:49 -0500, David Marcus > <DavidMar...(a)alumdotmit.edu> wrote: > > >>> I am interested whether there are irrational numbers. [WM] > > >> Well, fact is, no one has ever seen one of them so far. > > >> (On the other hand, the same is true for natural numbers, integers, > >> and rational numbers, too. :-) > > > Responding to WM? Isn't that pointless? :) > Sure it is! :-) It seems WM will no longer reply to any of my posts. If we could figure out how I accomplished this, maybe others could do the same!
From: davidmarcus on 25 Jan 2007 19:28 On Jan 25, 2:28 pm, Andy Smith <A...(a)phoenixsystems.co.uk> wrote: > IDavid Marcus <DavidMar...(a)alumdotmit.edu> writes > (snip) > > >> 1) Any systematic method for counting the reals is equivalent (you would > >> probably say isomorphic under permutation). > > >This is wrong or at least too vague to say whether it is right or wrong. > >What do "systematic method" and "equivalent" mean? And, I don't know > >what "isomorphic under permutation" means, so I wouldn't say that. > > >Does the following qualify as a "systematic method" for enumerating the > >reals? > > >0 > >0.1 > >0.2 > >... > >0.9 > >0.01 > >0.02 > >... > >0.09 > >0.11 > >0.12 > >... > >0.19 > >... > Yes, that is exactly what I suggested - in binary that addressing is > achieved by mirroring the bits about the binary point. Looks more > straightforward as you have set it out. > > >Is the following what you are saying? > > >We can enumerate the reals by first enumerating the reals that take only > >1 bit to write in binary, then the ones that 2 bits, then the ones that > >take 3 bits, etc. This doesn't work because we never get to the ones > >that take an infinite number of bits. > > >If so, that's fine as far as it goes, but it doesn't tell us whether > >some other method of enumerating the reals will work. > 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... I'm not sure what you mean by "permutation". Do you mean enumeration or listing? Maybe you mean bijection (a map that is one to one and onto). Let's be more precise: Let's suppose that by "permutation" you mean a bijection . Suppose p is a permutation of [0,1] and f: N -> R is a surjection. Let g be defined by g(x) = p(f(x)). Then g is a surjection N -> R. On the other hand, if h: N -> R is not a surjection, why should this imply that no surjection exists? For example, here is a list of rational numbers: 0.1 0.01 0.001 .... This is clearly not a surjection onto the rationals. However, we know that a surjection N -> Q does exist. > 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. As a heuristic, that is OK, but it doesn't actually prove that the reals aren't countable. > >> Incidentally, if you will excuse the cross-threading, re the > >> space-filling curve, yes it fills the space, but with my variant, are > >> the points in the plane painted white or black (at each stage of > >> iteration by construction the white area = black area).? > > >I'm sorry, but I didn't understand your variant well enough when I first > >read it to answer your question. Please explain it again. > I just said, make the "generator" a thick line, such that the area of > the line is the same as that of the enclosing space, with the line > painted black and the external area painted white. You can consider such > a generator as two lines of zero width delineating boundaries between > black and white if you wish. The topology of inside and outside is > preserved with each iteration of the fractal scheme, and on each > iteration you have equal areas of black and white in the output. In the > limit, any point on the plane is covered by both the lines defining the > boundaries to the thick generator. So, is a point on the covered plane > painted black or white? I don't think this is clear enough to answer your question. From your description, it isn't clear if it is even possible to do what you say. With the usual construction of a space filling curve, there are no points missed by the curve. Also, there is no reason to think that a point's color converges to a limit. For example, I can alternately color a point white and black. If I repeat this an infinite number of times, then the limit of the colors doesn't exist.
From: Dik T. Winter on 25 Jan 2007 20:21 In article <1169740229.047316.94890(a)v33g2000cwv.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > Dik T. Winter schrieb: > > > 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}. > > Correct. But this union does not enter my proof other than by the > theorem: The set of paths contained in T2 is but a subset of the > *countable* union of the sets of paths in T1 and T2. That is important. > But I do not define the union of trees by paths. I am not interested so much in the union of trees as well as in the union of sets of paths, that is what I repeatedly try to make clear. > > > 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. > > I do not use the union of sets of paths but the union of nodes. Wrong. See above (and I quote again): > The set of paths contained in T2 is but a subset of the > *countable* union of the sets of paths in T1 and T2. That is important. You *explicitly* use the union of sets of paths. > The set of paths in the union is a subset of the union of all > sets of paths. But I do not use this latter union for my proof. Both statements are incorrect. > > > 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. > > Correct. Nevertheless there is no natural number which is larger than > any path-length. Well, of course you say "correct". It is a statement by yourself. However, if we use finite-length paths only, there still is *no* natural number that is larger than any path-length. That is the same as stating that there is a natural number that is larger than all other natural numbers, as you very well do know. > > > 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. > > A path-length which has no upper bound may be sufficent to be called > infinite. Sorry, a path-length is something fixed, so the wording is inadequate. But if you call a path-length infinite you do not satisty (1), because there you associate 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. > > First explain why path-length which has no upper bound is not to be > called infinite. In (1) you associate path-lengths with natural numbers. "infinite" is not a natural number. > If you find a reasonable argument, then I will consider your > suggestion. I think that is a reasonable argument against (1). As you allow only two possibilities, (2) 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. > > You are in error. a_1k, a_2k, a_3k, ... is an element of S. Observe the > symbol { | } above. No. a_1k, a_2k, a_3k, ..., is *not* an element of S. a_1k is an element of S. The best you can state is that that sequence is a *subset* of S. In set notation, the first element is the element between the opening brace and the first comma. Following elements are between successive comma's. > > 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 } As an afterthought, if you want it directly: S = {{a_1k, a_2k, a_3k, ...}| a in {0, 1}, k in N } Note the additional braces. > > That would be a set of at most two bits. Why? Lets restrict k to {1, 3}. S_1 = { a_11, a_21, a_31, ...}, an ordered set. S_2 = { a_12, a_22, a_32, ...}, an ordered set. S_3 = { a_13, a_23, a_33, ...}, an ordered set. So: S = { S_1, S_2, S_3 }, a set with three elements. The elements are S_1, S_2 and S_3, all three ordered sets. The cardinality of S is 3. This is all very basic set theory. > We require sequences a_1k, > a_2k, a_3k, ... They are there, as elements. > > 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. > > S above is in fact a list of sequences. The enumeration by N is > justified by the fact that S is a subset of a countable set. Not proven. > T(oo) and > all its constituents are at most countable. As set of nodes, yes. But if T(oo) is a set of nodes, it is *not* a set of paths, nor a set of edges, nor a set of levels. Consider the following tree: o / \ / \ o o / \ / \ As a set of nodes it has cardinality 3, as a set of edges it has cardinality 6, as a set of levels it has cardinality 2 and as a set of paths it has cardinality 4. So a tree can not be considered a set of nodes at one time and as a set of edges or whatever at another time. You have to clearly state what kind of set a tree is. > > There are no different limits for one sequence. > > Yes. Therefore the cardinality |R| of the limits R cannot surpass the > cardinality |S| = |N| of the sequences S. Sorry. Your interpretation of your S is fundamentally wrong. See above. > > > 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. > > Of course it does not do that. The *set* of paths of the union is a > subset of the union of all *sets* of paths. Wrong. > > > 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 more paths than were unioned, i.e.,countably many. > > > > But this is, eh, also correct. Sorry, I should have stated partly correct. As every path in the union is a union of finite paths, but the set of those paths is not countable. > > Still that makes it *not* the union > > of countably many *sets* of paths. > > Bu it shows that the *set* of paths of the union is a proper subset of > the union of all *sets* of paths. And, again, that is fundamentally wrong. It does not show anything of that kind. The union of all sets of paths from finite trees contains only finite paths. That is pretty basic set theory. If none of the sets used in the union contains an infinite path, there is also not an infinite path in their union. > > > the union of two or more paths are nodes. > > > > Eh? The union of two or more paths is a set of nodes. > > I was a bit slopy here. A set of nodes is correct. But it need not be a > path. Right. > > > 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. > > That is what I proved. In the union of the *sets* of paths in the > finite trees there is no infinite path. And that is what I am stating all along, but you are arguing against. > Hence the subset which is in > T(oo) also does not contain an infinite path. Indeed. That subset is empty. Because by your definitions *none* of the finite paths is a path in T(oo). Indeed, also, *none* of the paths in some T(m) is a path in T(n) when n > m. But, also by your definitions, T(oo) does contain paths. Or do you now claim that T(oo) does not contain paths at all? > > > > > 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. > > T(oo) contains only finite path. Which ones? Care to specify a finite path that is in T(oo)? This reasoning is *exactly* the same as stating that N is finite. > > 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. > > Yes. It is a subset. But I do not *define* the union of trees by their > paths! Does not matter. With your reasoning I can only conclude that T(oo) contains no paths at all. But whatever. You never did even try to prove that statement. > > Which is in itself nonsense. > > Which according to set theory is correct. No, it is wrong. It assumes that N is finite. > > But if we elide "of finite sets" it makes sense, > > No. Below you talk about "finite trees". This implis finite paths and > finite sets. You do apparently not see *why* it makes no sense. I will try to explain, you write: > > > > > 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. Let us analyse and give some symbols to some of the terms: P is the set of paths in T(oo). P(k) is the set of paths in the finite tree T(k). P_C is the set of finite sets P_C. Now P_C is indeed a countable set. Its elements are P(1), P(2), etc. A subset of P_C is something like { P(1), P(2) } with as elements *sets* of paths. However, P is a set with as elements paths. So P can *not* be a subset of P_C. > > 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. > > Also this union is countable. > > > 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. > > Of course I consider paths, because I wish to consider real numbers, > but I do not *define* the union of trees by their paths! You consider *sets* of paths. You appear to have problems with sets of sets. In set theory the sets N and {N} are different. The first one has a large number of subsets, the second one only two. Also the cardinality is quite different. -- 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 20:41
In article <1169740568.082762.116480(a)v33g2000cwv.googlegroups.com> mueckenh(a)rz.fh-augsburg.de writes: > On 25 Jan., 15:57, Franziska Neugebauer > <Franziska-Neugeba...(a)neugeb.dnsalias.net> wrote: > WM ] > > | The union of two natural numbers is defined to be the larger one. > > | This is a set theoretic union. .... > The union of two different natural numbers is defined to be the larger > one. In the von Neumann model. But that is a model about ordinal numbers, that start at 0. There are a few subtle differences. I think you are a bit confused here. In the von Neumann model we have that an ordinal number 'k' is the set of all its predecessors ( {0, 1, 2, ..., k-1), if k is not a limit ordinal). And so the union of two ordinals is the larger one. In this case, the ordinal 'k', is also the ordinal number of the set of predecessors. When you shift to '1' base, the latter statement is no longer true. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ |