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.
