On Jun 15, 6:39 pm, Owen Jacobson <angrybald...@gmail.com> wrote: > On 2009-06-15 14:52:51 -0400, WM <mueck...@rz.fh-augsburg.de> said: > > > > > On 15 Jun., 18:09, Owen Jacobson <angrybald...@gmail.com> wrote: > >> On 2009-06-14 14:41:40 -0400, WM <mueck...@rz.fh-augsburg.de> said: > >> 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. > > > That is similar to every bit of 1/3 = 0.010101... in binary. Evere bit > > has a finite label. > > Similar to, but not the same. Under this labelling, there is no node > labelled with the binary representation of 1/3, because that > representation is not finite. > > There is a *path* which can be produced for 1/3, informally rendered as > {., .0, .01, .010, .0101, ...} > and formally rendered as a function h from N to the set of nodes such > that h's image is a path. > > > > >> 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. > > > And for *every* bit a_n of this infinite path > > Paths do not contain bits. They contain nodes, and edges. Please be rigorous. > > > there is a terminating path in the tree that contains n^n^n more nodes. > > This is a red herring. There are, for any finite path x that is a > subpath of the path described by f, infinitely many finite paths that > contain x as a subpath. If the path x is rooted, then *every natural > larger than the preimage of x under f* identifies the terminal node of > a finite rooted path that contains x as a subpath. > > If paths were "constructed" in a stepwise fashion, then this would be a > solid argument that such a stepwise process can never finish > constructing the path described by f. However, paths are not > "constructed". We give the function f, and its domain (N), and consider > the complete path to have been described. It already existed; with > those two entities, we have enough information to identify it and work > with it. > > > > >> 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. > > > No it can't, unless magic plays a role. Every path in the tree is a > > finite path. > > Okay, wiseass. Which node in the path described by f is not in the tree? > > Every path in one of the sets from which the tree can be described is > finite. That set is not the only way to describe the tree; we could, > for example, describe it using a set of all of its infinitely-long > paths, instead. Would you then argue that the tree contained no finite > paths? > > >> 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. > > > And for each of these claoser rationals is far away from pi. > > I cannot even guess at what you meant to say here. > > >>> 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. > > > There is no union. But even in set theory a union of sets should not > > contain elements that are in none of the united sets. > > Once again: which element do you claim the path corresponding to 1/pi > contains that is not contained in any of the finite paths used to > describe the tree? > > If that path is not in the tree, then it must contain a node, or an > edge, that is not in the tree. So which one is it? > > -o
Musatov produced:
[PS] SIGACT News Complexity Theory Column 36 William Gasarch: (Univ of MD, 2100, P=NP) NP-completeness is important since (as we. tell our students) if a problem is NP-complete you look for other ways ... http://www.cs.umd.edu/~gasarch/papers/poll.ps
