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: WM on 9 Jun 2010 05:10 Binary Tree The complete infinite binary tree contains all real numbers between 0 and 1 as infinite paths i. e. 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. This distinguishability, however, is a precondition for Cantors diagonal argument. The binary tree can be constructed because it consists of all its distinct nodes which form a countable set. The binary tree cannot be constructed because it consists of all its distinct paths which form an uncountable set. Regards, WM
From: Brian Chandler on 9 Jun 2010 06:15 WM wrote: > Binary Tree > > The complete infinite binary tree ... Oh no. Is there no end to it? Brian Chandler
From: William Hughes on 9 Jun 2010 07:58 Can you distinguish the path x= 111... from every path in the set of paths Y={ 000... 1000... 11000... 111000... .... } ? Please begin your answer yes or no. - William Hughes
From: WM on 9 Jun 2010 08:55 On 9 Jun., 13:58, William Hughes <wpihug...(a)hotmail.com> wrote: > Can you distinguish the path > > x= 111... > > from every path in the set of paths > > Y={ > > 000... > 1000... > 11000... > 111000... > ... > > } Yes, we can! Wouldn't your question have been rather nonsensical if I could not? Of course we, me and you, can distinguish those paths because you used finite definitions like "xyz..." to name them. Can you distinguish by "xyz..." more than countably many paths? Please begin your answer yes or no. Regards, WM
From: William Hughes on 9 Jun 2010 09:19
On Jun 9, 9:55 am, WM <mueck...(a)rz.fh-augsburg.de> wrote: > On 9 Jun., 13:58, William Hughes <wpihug...(a)hotmail.com> wrote: > > > Can you distinguish the path > > > x= 111... > > > from every path in the set of paths > > > Y={ > > > 000... > > 1000... > > 11000... > > 111000... > > ... > > > } > > Yes, we can! Wouldn't your question have been rather nonsensical if I > could not? Of course we, me and you, can distinguish those paths > because you used finite definitions like "xyz..." to name them. > > Can you distinguish by "xyz..." more than countably many paths? > > Please begin your answer yes or no. No. (I interpret your question as "Can you distinguish more than countably many paths using finite descriptions") It is well known that the set of finite descriptions is countable (though not computable). Does the set of paths Y cover every node in the tree? Please begin your answer yes or no. - William Hughes |