On May 15, 6:04 pm, "LudovicoVan" <ju...@diegidio.name> wrote: > Trying yet another approach to the diagonal argument: sometimes I think it > is valid in some fundamental way, sometimes, as here, I can concoct > counter-arguments... Constructive comments, corrections, explanations, etc. > etc. are all very welcome. (Unconstructive contributions will be ignored.) > > Let us systematically enumerate the infinite binary strings. As an > approach, we can "search" the complete binary tree as follows (note that > this enumerates [0;1[, not [0;1], which is someway a key point though for > reasons not covered in this post): > > We will use a so called depth-first search to enumerate the nodes. To each > node we associate one and only one infinite path by way of considering the > path along a straight direction (which can be encoded as a period, i.e. > "(0)" or "(1)") from the given node: to the left if the node is odd (i.e. it > is 1) at an odd level of the tree, or even (i.e. it is 0) at an even level > of the tree; otherwise to the right (the node is even at an odd level or odd > at an even level). IOW, go down left if the parity of the node matches that > of its tree level, go right otherwise - 'R' is considered even. > > 0: [R] > * > 1: 0 > * > 2: 0 > * > ....................... > > 'R' encodes as "(0)" > > 0: (R) > / > 1: [0] > / * > 2: 0 1 > / * > ....................... > > 'R0' encodes as "0(1)" > > 0: (R) > / \ > 1: (0) [1] > / \ * > 2: 0 1 0 > / \ * > ....................... > > 'R1' encodes as "1(0)" > > 0: (R) > / \ > 1: (0) (1) > / \ / > 2: [0] 1 0 > / * \ / > ....................... > > 'R00' encodes as "00(1)" > > 0: (R) > / \ > 1: (0) (1) > / \ / > 2: (0) [1] 0 > / \ * \ / > ....................... > > 'R01' encodes as "01(0)" > > 0: (R) > / \ > 1: (0) (1) > / \ / > 2: (0) (1) [0] > / \ / \ / * > ....................... > > 'R10' encodes as "10(1)" > > 0: (R) > / \ > 1: (0) (1) > / \ / \ > 2: (0) (1) (0) [1] > / \ / \ / \ * > ....................... > > 'R11' encodes as "11(0)" > > And so on... > > In short, the enumeration we get is (omitting quotes): > > (0) > 0(1) > 1(0) > 00(1) > 01(0) > 10(1) > 11(0) > ... > > which is pretty easy to define recursively. > > And, since this systematically searches the nodes of the complete tree, the > enumeration (when considered as a whole) is a complete enumeration of all > the infinite binary strings! (Or so logic tells.) >
