In article <2009061512093016807-angrybaldguy@gmailcom>, Owen Jacobson <angrybaldguy@gmail.com> wrote:
> On 2009-06-14 14:41:40 -0400, WM <mueckenh@rz.fh-augsburg.de> said: > > > On 14 Jun., 17:31, Owen Jacobson <angrybald...@gmail.com> wrote: > >> On 2009-06-13 14:29:05 -0400, WM <mueck...@rz.fh-augsburg.de> said: > >> > >>> We agree that in Cantor's diagonal argument, applied to real numbers, > >>> the numbers are represented and identified solely by their digits. No > >>> further information is available. > >> > >>> We assume that a real number p can be distinguished from a set Q of > >>> real numbers q by general considerations, for instance, if p is a > >>> transcendental number and Q consists of rational numbers q only. > >> > >>> Of course it would be impossible to distinguish p from all q, because > >>> for every digit d_n of p, there is a number q that shares all digits > >>> up to d_n with p. > >> > >> Wait, so you're arguing that you can't distinguish 1/pi (roughly > >> 0.31830988...) from a set containing all rationals in [0, 1] because, > >> for example, 3/10 is equal to 1/pi to the first decimal place, 31/100 > >> is equal to the second, and so on? What about the non-zero difference > >> between any one rational number and 1/pi? > >> > >> |1/pi - 3/10| is greater than the rational 1/50. |1/pi - 31/100| is > >> greater than the rational 1/125. In fact, for each rational q in [0, > >> 1], 1/pi differs from q by an amount greater than some other rational r > >> in [0, 1], so we can distinguish 1/pi from every rational in [0, 1]. > > > > If 1/pi exists as an actually infinite digit sequence. > > Since there is a function g from N to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} > that, for *every* element n of N, produces the n'th decimal place of > 1/pi, it's safe to say that 1/pi has an infinite decimal > representation. There's also a function g' from N to {0, 1} that > produces, for *every* element n of N, the n'th bit of the binary > representation of 1/pi. > > > There are two statements: > > 1) Path p can be distinguished from every path of the countable set P > > that is used to construct the tree. > > 2) Path p cannot be distinguished from every path of P. > > Reading upstream a bit, I think you've misapprehended the point people > are making. If P is a set of paths, and the union of all elements of P > is the maximal complete binary tree, then there can be paths in the > union of all elements of P that are not in P. If P is a countable set, > then there are necessarily paths in the union of all elements of P that > are not in P. > > In fact, one such set P is the set of finite rooted paths, which is > isomorphic to the set of nodes in the maximal complete binary tree. > We'll adopt a notation where each node is labelled with the set of left > (denoted as 0) and right (denoted as 1) branchings necessary to reach > it, prefixed by a dot (.): > > . is the root node. > .0 is the left child of the root node. > .1 is the right child of the root node. > .00 is the left child of the left child of the root node. > .01 is the right child of the left child of the root node. > .10 is the left child of the right child of the root node. > .11 is the right chind of the right child of the root node. > (And so on.) > > Because every node can be reached in only finitely many branchings (as > a consequence of the tree being representable as an infinite set of > finite paths), every node has a finite label. > > We'll denote paths in the standard way, as sets of nodes: > > {., .0} is the path from the root to the leftmost rank 1 node. > {., .0, .01} is the path from the root to the right-hand child of the > left-hand child of the root node. > > Finite rooted paths can also be identified, for convenience, by their > terminal node: there is one and only one path from the root node to the > node .001101, so writing out the complete path is pointless. However, > *infinite* paths do not have a terminal node, so they must be described > in some other way - for example, by a function from N to the nodes of > the tree. > > A path exists in the tree if and only if (every node on that path is in > the tree) and (the path is a connected, linear subgraph of the tree). > Two paths A and B are equal if and only if the set of nodes in path A > is equal to the set of nodes on path B. > > There is a function f from N to the set of nodes that, for every > natural number n, produces the node labelled by the first n binary > places of 1/pi's binary expansion. This function describes a path. This > path is distinct from every path in the set of finite paths used to > describe the tree, because for every path in that set, the path > described by this function contains more nodes. > > Informally, the path q from 1/pi under f is > {., .0, .01, .010, .0101, .01010, .010100, .0101000, .01010001, > .010100010, ...}. (Formally, it is only finitely describable as a > function, not as an element-by-element list of nodes.) > This path is distinct from each finite path: > {.} is missing the node .0, which is in q. > {., .0} is missing the node .01, which is in q. > {., .0, .01} is missing the node .010, which is in q. > > In fact, we can continue this indefinitely; none of the finite rooted > paths from which the tree is derived contains every node in q. However, > every node in q is in the tree, since every one of its infinitely-many > nodes is reachable from the root node after finitely many branchings. > So q is a path over the maximal complete binary tree even though the > maximal complete binary tree can be derived from a set that does not > contain q. > > This is equivalent to the argument from arithmetic that there is, for > every rational x, a rational y that is closer to 1/pi than x, presented > above. > > > One of them is false, unless it is a magic tree where something > > happens during construction. But I do not believe in magic, least in > > mathematics. > > That a union of infinitely many distinct finite paths can contain > infinite paths does not surprise me. In ZFC, one formulation of the > axiom of infinity takes exactly the form of an infinite union of finite > elements. Only a union of finitely many finite elements or a (possibly, > infinite) union of finitely many distinct finite elements ({1} U {1} U > {1} U {1} U {1} U ... = {1}, for example), neither of which is > sufficient to produce the maximal complete binary tree, is a finite set. > > Conversely, in a set theory with no infinite sets, there is also no > binary tree containing the path q (from above). Both kinds of theory > can be internally consistent, which is as close to "true" as anything > in mathematics gets. > Very nice!
