constructible = unconstructible
in [Math]
|
Prev: "NO BOX CONTAINS THE BOX NUMBERS THAT DON'T CONTAIN THEIR OWN BOX NUMBER" ~ XEN
Next: manipulating spectral norm of matrix with normalized columns
From: William Hughes on 10 Jun 2010 07:22 On Jun 10, 7:19 am, WM <mueck...(a)rz.fh-augsburg.de> wrote: > On 9 Jun., 22:58, William Hughes <wpihug...(a)hotmail.com> wrote: > > > To be clear, the assertion I made is > > > There is a set of nodes contained in the list > > that is not contained in any single line of the list. > > > or equivalently. > > > No single line of the list contains all nodes that > > are contained in the list. > > > This assertion is not strange, it is trivially obvious. > > And it is wrong. Only in Wolkenmuekenheim, where the potentially infinite set of nodes covered by the path 111... contains a node that is not is the potentially infinite set of nodes Z={ 1 11 111 ... } Of course this node may be the problem. A fixed node that can change can do anything. - William Hughes
From: WM on 10 Jun 2010 07:45 A lesson for set theorists The complete infinite binary tree contains, by definition, all real numbers between 0 and 1 as infinite paths, i. e., as infinite sequences { 0, 1 }^N of bits. 0, / \ 0 1 / \ / \ 0 1 0 1 / 0 ... The set { a_k | k in N } of nodes a_k of the tree is countable. a0, / \ a1 a2 / \ / \ a3 a4 a5 a6 / a7 ... If every node a_k is covered by an arbitrary infinite path p_k containing that node, then no further node is remaining to distinguish any further path from the paths p_k of the countable set P = { p_k | k in N }. This proves that it is impossible to distinguish more than countably many paths by infinite sequences of bits. FIRST COUNTER ARGUMENT All nodes of a path are covered by other paths. Therefore covering all nodes of the binary tree by a countable set of paths does not show that all paths of the binary tree form a countable set. Here is an example for the counter argument: We can cover every node of path p = 0.111... by means of covering every path p# of the set { 0.000... 0.1000... 0.11000... 0.111000... ....} No. Every path p# of the form 0.111...111000... has at least one node 0 at a position where p = 0.111... has a node 1. So when covering, in the binary tree, all nodes of path p none of the paths p# has been covered. In other words: every p# has an uncovered node after all nodes of p have been covered. Vice versa, when all p# have been covered, then p has not yet been covered. Every path p# deviates from p leaving at least one of its nodes 1 uncovered. Of course this is only an existence proof. After covering all paths p#, an uncovered node of p cannot be named. But if no such node exists, p would have been written down (= covered in the tree) by writing down (= covering in the tree) all paths p#. Then, however, Cantor's diagonal proof would fail because then the possible antidiagonal p = 0.111... of the above list is in the list. SECOND COUNTER ARGUMENT In order to save Cantor's diagonal proof, it must be claimed that although all nodes of p are covered by the set of paths p#, there is no path p# = p. That means: I) All nodes 1 of p = 0.111... are in the list of all paths p# above. II) No line p# contains all these nodes 1, i.e., the limit p is not in the list. These two assertions cannot be satisfied simultaneously. Proof A. If the existence in different lines is claimed, then at least two lines must be shown which cannot be replaced by one line, with respect to their contents of nodes 1. This is obviously impossible. In the contrary, it can be proved by complete induction, hence for every line of the list, that all nodes which are in that line and in all previous lines, also are in the next line. Proof B. Construct the above list, but remove always line number n after having constructed the next line number n + 1. Then the list shrinks to a single line but this single line contains the same as the list because never anything has been removed that had not been added before to an existing line. Therefore this single line contains all node 1. It is the limit p = 0.111... If, however, line number n is not removed after line number n + 1 has been constructed, this cannot change the result for line n + 1 and later lines. If a single line p = 0.111... can be constructed then this line must also be in the complete list. CAN N BE CONSTRUCTED? If this question is denied, then it is impossible to construct a complete Cantor list, in order to prove uncountability, and it is impossible to count beyond any finite number. By simple division, like in decimal 1/9, we can construct p = 0.111... In the sam way we construct N as the set of indices. The indices n can be constructed in the unary system as embodied by the nodes 1 of the p# in the above list. When imaging all nodes 1 in one single line, then nobody will complain about all nodes existing in one single line. When imaging all nodes 1 written as in the above list, then the existence of all nodes 1 in a single line is denied. This result appears paradoxical. But the only paradoxical is the assumption that infinity can be finished and that thousands of rather intelligent people have been believing that for more than 100 years. [This lesson was inspired by a discussion with William Hughes in sci.math on June 9, 2010.] Regards, WM
From: William Hughes on 10 Jun 2010 07:55 On Jun 10, 7:19 am, WM <mueck...(a)rz.fh-augsburg.de> wrote: > On 9 Jun., 22:58, William Hughes <wpihug...(a)hotmail.com> wrote: > > To be clear, the assertion I made is > > There is a set of nodes contained in the list > > that is not contained in any single line of the list. > > or equivalently. > > No single line of the list contains all nodes that > > are contained in the list. > > This assertion is not strange, it is trivially obvious. > And it is wrong. Only in Wolkenmuekenheim, where the potentially infinite set of nodes covered by the path 111... contains a node that is not is the potentially infinite set of nodes Z={ 1 11 111 ... } Of course this node may be the problem. A fixed node that can change can do anything. - William Hughes
From: William Hughes on 10 Jun 2010 08:10 On Jun 10, 7:34 am, WM <mueck...(a)rz.fh-augsburg.de> wrote: <snip> > if we divide 1 by 9, then 0.111... does exist according > to the above definition. > If we write it in a single line, nobody will disagree. > If we write it such that every next 1 is placed in a new line, like > > 0.1 > 0.11 > 0.111 > ... > > then everybody will disagree that all 1 are in one line but all 1 > "must be there somehow". Yes and outside Wolkenmuekenheim, everyone is correct. However inside Wolenmuekenheim there is a 1 in 0.111... that is not in the list. > This leads to the easily disprovable claim > that there are at least two lines required to contain all 1's. Nope, it leads to the easily provable claim that a set of lines, S, that contains all nodes must contain an infinite number of lines. Since any set of infinite lines is sufficient, and there exist disjoint sets of infinite lines, it follows immediately that no two specific lines are required. - William Hughes
From: William Hughes on 10 Jun 2010 08:17
On Jun 9, 10:37 am, WM <mueck...(a)rz.fh-augsburg.de> wrote: > On 9 Jun., 15:19, William Hughes <wpihug...(a)hotmail.com> wrote: > > > It is well known that the set of finite descriptions > > is countable (though not computable). > > The set of all names which unavoidably include all nunbers is > computable. The set of all names, S is computable. The set of all computable numbers, R is a subset of S. A subset of a computable set may or may not be computable. R is not computable. - William Hughes |