Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: On the diagonal argument again
Replies: 199   Last Post: Jun 10, 2012 10:12 AM

 Messages: [ Previous | Next ]
 William Hughes Posts: 1,555 Registered: 12/7/10
Re: On the diagonal argument again
Posted: May 15, 2012 7:21 PM

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.)
>

1010101010...

Date Subject Author
5/15/12 LudovicoVan
5/15/12 LudovicoVan
5/15/12 William Hughes
5/15/12 LudovicoVan
5/15/12 Virgil
5/16/12 Graham Cooper
5/15/12 Shmuel (Seymour J.) Metz
5/15/12 LudovicoVan
5/15/12 Virgil
5/16/12 mueckenh@rz.fh-augsburg.de
5/16/12 Daryl McCullough
5/16/12 LudovicoVan
5/16/12 LudovicoVan
5/16/12 Virgil
5/16/12 LudovicoVan
5/16/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 Graham Cooper
5/18/12 Michael Stemper
5/18/12 Daryl McCullough
5/18/12 Shmuel (Seymour J.) Metz
5/18/12 LudovicoVan
5/16/12 Graham Cooper
5/16/12 Shmuel (Seymour J.) Metz
5/16/12 LudovicoVan
5/16/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/18/12 Virgil
5/18/12 Graham Cooper
5/18/12 David Bernier
5/18/12 Graham Cooper
5/18/12 K_h
5/18/12 |-| E R C
5/18/12 K_h
5/18/12 Graham Cooper
5/18/12 Graham Cooper
5/19/12 K_h
5/19/12 Graham Cooper
5/19/12 Graham Cooper
5/19/12 David Bernier
5/19/12 Graham Cooper
5/19/12 Graham Cooper
5/20/12 K_h
5/20/12 Graham Cooper
5/21/12 K_h
5/21/12 Graham Cooper
5/29/12 mueckenh@rz.fh-augsburg.de
5/29/12 Virgil
5/19/12 K_h
5/19/12 Graham Cooper
5/18/12 LudovicoVan
5/18/12 LudovicoVan
5/18/12 Shmuel (Seymour J.) Metz
5/17/12 Graham Cooper
5/17/12 Shmuel (Seymour J.) Metz
5/18/12 LudovicoVan
5/19/12 Shmuel (Seymour J.) Metz
5/19/12 LudovicoVan
5/20/12 Shmuel (Seymour J.) Metz
5/19/12 LudovicoVan
5/19/12 LudovicoVan
5/20/12 Shmuel (Seymour J.) Metz
5/19/12 LudovicoVan
5/19/12 LudovicoVan
5/16/12 Graham Cooper
5/16/12 Virgil
5/18/12 K_h
5/15/12 dilettante
5/16/12 LudovicoVan
5/16/12 dilettante
5/16/12 LudovicoVan
5/16/12 dilettante
5/16/12 Graham Cooper
5/16/12 dilettante
5/16/12 Graham Cooper
5/16/12 dilettante
5/16/12 Graham Cooper
5/16/12 LudovicoVan
5/16/12 dilettante
5/16/12 LudovicoVan
5/16/12 Virgil
5/17/12 William Hughes
5/17/12 LudovicoVan
5/17/12 William Hughes
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/16/12 Graham Cooper
5/16/12 Virgil
5/16/12 |-| E R C
5/16/12 LudovicoVan
5/16/12 Virgil
5/16/12 LudovicoVan
5/16/12 Jim Burns
5/16/12 LudovicoVan
5/16/12 Graham Cooper
5/16/12 Jim Burns
5/16/12 LudovicoVan
5/16/12 Jim Burns
5/16/12 |-| E R C
5/17/12 LudovicoVan
5/17/12 Jim Burns
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/16/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/18/12 Virgil
5/17/12 |-| E R C
5/18/12 Shmuel (Seymour J.) Metz
5/19/12 LudovicoVan
5/16/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 Graham Cooper
5/18/12 Daryl McCullough
5/18/12 Graham Cooper
5/18/12 Virgil
5/17/12 LudovicoVan
5/17/12 Virgil
5/17/12 LudovicoVan
5/17/12 YBM
5/17/12 LudovicoVan
5/18/12 Virgil
5/18/12 Shmuel (Seymour J.) Metz
5/19/12 LudovicoVan
5/17/12 Shmuel (Seymour J.) Metz
5/19/12 LudovicoVan
5/20/12 Shmuel (Seymour J.) Metz
5/16/12 Virgil
5/29/12 Aatu Koskensilta
5/29/12 Graham Cooper
5/30/12 K_h
5/30/12 Virgil
5/30/12 Curt Welch
5/30/12 Graham Cooper
5/30/12 ross.finlayson@gmail.com
5/30/12 Graham Cooper
5/30/12 K_h
6/1/12 ross.finlayson@gmail.com
6/8/12 Albert van der Horst
5/29/12 Aielyn
5/29/12 Aielyn
5/29/12 Graham Cooper
5/29/12 Aielyn
5/29/12 Mike Terry
5/31/12 Aielyn
5/31/12 Virgil
5/31/12 Aielyn
5/31/12 Virgil
5/31/12 Aielyn
5/31/12 Shmuel (Seymour J.) Metz
5/31/12 Shmuel (Seymour J.) Metz
5/31/12 Mike Terry
6/1/12 Graham Cooper
6/1/12 Guest
6/1/12 LudovicoVan
6/1/12 LudovicoVan
6/1/12 LudovicoVan
6/1/12 LudovicoVan
6/1/12 Graham Cooper
6/1/12 Virgil
6/1/12 Graham Cooper
6/1/12 LudovicoVan
6/1/12 |-| E R C
6/10/12 Aielyn
6/10/12 Shmuel (Seymour J.) Metz
5/29/12 Tim Little
5/31/12 LudovicoVan
6/5/12 Shmuel (Seymour J.) Metz
6/4/12 Aatu Koskensilta
6/4/12 Graham Cooper
6/4/12 ross.finlayson@gmail.com
6/4/12 ross.finlayson@gmail.com
6/4/12 Graham Cooper
6/4/12 ross.finlayson@gmail.com
6/4/12 |-| E R C