Aielyn
Posts:
21
Registered:
1/16/10
|
|
Re: On the diagonal argument again
Posted:
May 29, 2012 9:16 AM
|
|
On Wednesday, May 16, 2012 7:04:22 AM UTC+10, LudovicoVan 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.)
>
> So, let us try Cantor's diagonal argument against our "list". The diagonal,
> defined as usual, would in this case be the string "(10)". And we can
> readily see that this string along with its symmetric, the diagonal (namely,
> "(01)"), make a perfect fit for the definition of a limit of our enumeration
> (i.e. as entries at positions -I'd think- omega+1 and omega respectively, as
> we are going left to right). In fact, since to all strings (with finite
> indexes) is appended a period (either "(0)" or "(1)"), only as a limit we
> can get the two strings made of all and only alternating digits! (Or so we
> would think.)
>
> Now, the diagonal argument is telling us, informally, that the anti-diagonal
> differs from "every" entry in the list, yet that is meant to hold in the
> *finite*, i.e. over finite indexes, and it in fact holds in the above
> construction too, because our anti-diagonal, it being the limit entry of the
> enumeration as per our construction, would eventually only differ from
> itself at the omega-th position exactly, where the usual diagonal argument
> just does not apply (in the usual diagonal argument, there is no omega-th
> position or omega-th entry under consideration at all). So our list is
> indeed complete while not contradicting the diagonal argument.
>
> (We could even extend the diagonal argument to consider the index omega,
> using infinite-case instead of finite induction and inductive definitions:
> we'd still get definitions by which it is consistent that the anti-diagonal
> cannot differ from itself in the very omega-th position. I have tried and
> shown this elsewhere, or so I think... I could recover a link to it if of
> interest.)
>
> -LV
You have asserted not just that it's possible, but that you have a way to do it. So, let's play that game.
By your enumeration, what is the integer that corresponds to pi (or pi-3, if you want it to be between 0 and 1)? The problem, here, is that there is no integer that corresponds to it - there are various integers that correspond to truncated approximations, but (pi-3) itself is only in the infinite limit case, and thus would have to be assigned the value "infinity"... but so would sqrt(2)-1.
I'll admit, I have an issue with cantor's diagonal method for proving that the reals aren't countable (the issue arises from the fact that repeating 1s at the end of a number is the same as flipping the bit before the first 1, and then setting the 1s to 0s - cantor's diagonal may produce terminating real that is already on the list in its repeating form, or vice versa)... but an iterative method of defining the ordering doesn't work.
Why not? Because the limit isn't well-defined - there's no resulting enumeration because something gets lost as it "approaches infinity". If you list according to depth (0.0, 0.1, 0.01, 0.11, 0.001, 0.011, etc), then all entries in the list that have a finite integer associated with them will be rational (and more than that, will be of the form a/2^b, for integers a and b). If, on the other hand, you insert new members into the list iteratively (starting with {0.0 0.1} and then inserting 0.01 as {0.0 0.01 0.1}, etc), the lack of termination (limits to infinity doesn't terminate) means that the real in the Xth position isn't defined.
In order to create an enumeration that disproves the uncountability of reals, you must use a prescriptive definition - that is, one that you can plug in a real number (or real number between 0 and 1), and it produces an unique positive integer that will not result from putting in any other real. An iterative constructive definition will not produce a meaningful result.
|
|
