Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Michael Press on 25 Jan 2007 02:30 In article <virgil-5263D4.14184524012007(a)comcast.dca.giganews.com> , Virgil <virgil(a)comcast.net> wrote: > In article <ep7k43$79j$1(a)mailhub227.itcs.purdue.edu>, > Dave Seaman <dseaman(a)no.such.host> wrote: > > > On Wed, 24 Jan 2007 09:19:22 +0100, G Frege wrote: > > > On Tue, 23 Jan 2007 19:45:39 -0500, David Marcus > > ><DavidMarcus(a)alumdotmit.edu> wrote: > > > > >>> > > >>> People cannot conceive of an infinite past, [...] > > >>> > > >> Why not? I believe that was the usual assumption before the Big Bang > > >> was discovered. > > >> > > > Not really... Remember? > > > > > "In the beginning God created the heavens and the earth. Now the earth > > > was formless and empty, darkness was over the surface of the deep, and > > > the Spirit of God was hovering over the waters." > > > > > This happened about 6000 years before Christ's birth, or so. > > > > It was supposed to be 4004 BC, according to Bishop Ussher. > > What o'clock? 9 AM Oct 3, 4004 BC but this date may need to be revised as scholars have revised the date of the Christ's birth since the good bishop published his findings. -- Michael Press
From: mueckenh on 25 Jan 2007 03:19 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. 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 } 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. 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). > > Let us call the union > of all finite trees (your definition) T1. I prefer T(oo). > P1 contains > every finite path, so P1 contains 0.11, T1 does not contain > 0.11, so P1 is not the same as T1. > Of course not. The union of all finite paths contains every path which is contained in one of the trees, including 0.1 and 0.11 and 0.111 and so on. But even this union (which I do NOT consider) is countable. > > 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. > No. Each path in T(oo) is the limit of a (potentially) infintie > sequence. So each path in T(oo) corresponds to > a (potentially) infinite set of paths in the finite trees. You can say so. But see above. The schism becomes clearly visible here. Therefore, there cannot exist an actually infinite set of finite numbers. It would imply the actual infinity of the union of finite paths, i.e., the acual infinity of at least one finite path. > > 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.) > No, the set of (potentially) infinite sets of paths is > not countable. See above. In any case all paths in the union of finite trees form a countable set. > > > > > Going on, we can say: > > > 6) T(oo) = T contains only finite paths. >No. T does not contain a finite path. See above. If path-lengths are natural numbers, then the union of all path-length does not contain an infinite path. > > > 7) T(oo) = T contains all paths including all infinite paths. > No. T contains only infinite paths. > That would not contradict statement (7). Regards, WM
From: mueckenh on 25 Jan 2007 03:24 On 24 Jan., 15:51, "Dik T. Winter" <Dik.Win...(a)cwi.nl> wrote: > In article <1169642941.554024.145...(a)k78g2000cwa.googlegroups.com> mueck...(a)rz.fh-augsburg.de writes: > On 23 Jan., 19:27, Dave Seaman <dsea...(a)no.such.host> wrote: > > > On Tue, 23 Jan 2007 17:15:52 GMT, Andy Smith wrote: > > > > > By definition, a set is "finite" if it has the size of some natural > > > number. If a set isn't finite, then it's called "infinite". > > > > If a colour is not red, then it is called green by set theorists. > > Wrong. not-red. "Not red" is blue or green in the RGB axiom system. But you exclude blue (potential infinity), hence you say green (green stands for "hope", hoping on actually finishing infinity) when you can't see red. Regards, WM
From: mueckenh on 25 Jan 2007 03:33 Dik T. Winter schrieb: > I am beginning to understand. You equate a sequece with a function > f: N -> objects > and talk about the domain and range of that function. Yes. The domain defines the length of the path. > > > > > Therefore there is no uncuntable set of path in the union tree. But > > > > there are all paths in the union trees. > > > > > > Conclusion is false. > > > > Summary > > > > 1) Every complete infinite binary tree T (containing all nodes and > > edges) contains all paths. > > 2) The union tree T(oo) of all finite trees is well defined (as I have > > shown elsewhere) and yields the complete infinite binary tree > > containing all nodes and edges: T = T(oo). > > 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. > > > 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. 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). > > > 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). > 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 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 } then L cannot be larger than S, because there cannot be more limits than 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. This is not only impossible but would also lead to undefined limits. > But this is also wrong. No. When unioning the trees we union also their subsets, including their paths. 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.) The set of paths in T(oo) consists of unions of paths. It cannot contain contain more paths than were unioned, i.e.,countably many. > 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. So the union of two or more paths are nodes. > (The reason is that the set on the left hand side contains infinite subsets, > while the set on the right hand side does *not* contain infinite subsets.) > > > 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. > > > Going on, we can say: > > > > 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. 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. > > 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! Regards, WM
From: Andy Smith on 25 Jan 2007 03:38
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 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. 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). 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). That may be rubbish, but your "counter example" is misrepresenting what I said. 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).? Regards -- Andy Smith |