halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: herbzet on 14 Aug 2008 02:52 Daryl McCullough wrote: > herbzet says... > > >I've been ignoring the problem of dual representations of > >numbers, e.g. .1000... = .0111... but I guess someone else > >could cope with that if they cared to. The fact that we can > >easily cope with it using base 10 numeration is a satisfactory > >solution anyway. > > There are several ways to cope with dual representations. > One is to use a higher base. > Another is to assume that the original list includes every > dual-representation real in both its representations. > Another is to take bits two at a time and at stage n, > make sure that the diagonal differs from real number > in both bit number 2n and bit number 2n+1. (Which is > really equivalent to using base-4 instead of base-2) Yes, I think I may have read about other strategies also. I actually regretted posting that last bit. This business of dual representations is just an annoyance and not germane to the fundamental situation. Let me put it this way: To show: the reals cannot be enumerated in a list (cannot be bijected with N). Choose a subset of those reals: the set of all reals in [0,1] that can be represented by a decimal point followed by infinite sequences of two digits, say, '5' and '7'. Assumption: this subset can be enumerated in a list L. Construct the anti-diagonal of L by substituting '5' for '7' and vice versa for the digits in the diagonal of L. The resulting sequence is not a member L, since it differs from each member of L. Therefore this subset of the reals in [0,1] cannot be enumerated; the assumption is false. Therefore, the set of sequences of '5' and '7', and the reals they represent, cannot be bijected with the natural numbers, and a fortiori, neither can their superset of reals. -- hz
From: Daryl McCullough on 14 Aug 2008 11:47 herbzet says... >I actually regretted posting that last bit. This business >of dual representations is just an annoyance and not germane >to the fundamental situation. Yes, except for the fact that some anti-Cantor crackpots have latched onto the double representation to prove that the Cantor argument is wrong. >Let me put it this way: > >To show: the reals cannot be enumerated in a list (cannot >be bijected with N). > >Choose a subset of those reals: the set of all reals in [0,1] >that can be represented by a decimal point followed by infinite >sequences of two digits, say, '5' and '7'. > >Assumption: this subset can be enumerated in a list L. > >Construct the anti-diagonal of L by substituting '5' for '7' >and vice versa for the digits in the diagonal of L. > >The resulting sequence is not a member L, since >it differs from each member of L. > >Therefore this subset of the reals in [0,1] cannot >be enumerated; the assumption is false. > >Therefore, the set of sequences of '5' and '7', >and the reals they represent, cannot be bijected >with the natural numbers, and a fortiori, neither >can their superset of reals. Yes, that's a better argument. -- Daryl McCullough Ithaca, NY
From: herbzet on 15 Aug 2008 01:07
Daryl McCullough wrote: > herbzet says... > > >I actually regretted posting that last bit. This business > >of dual representations is just an annoyance and not germane > >to the fundamental situation. > > Yes, except for the fact that some anti-Cantor crackpots > have latched onto the double representation to prove that > the Cantor argument is wrong. > > >Let me put it this way: > > > >To show: the reals cannot be enumerated in a list (cannot > >be bijected with N). > > > >Choose a subset of those reals: the set of all reals in [0,1] > >that can be represented by a decimal point followed by infinite > >sequences of two digits, say, '5' and '7'. > > > >Assumption: this subset can be enumerated in a list L. > > > >Construct the anti-diagonal of L by substituting '5' for '7' > >and vice versa for the digits in the diagonal of L. > > > >The resulting sequence is not a member L, since > >it differs from each member of L. > > > >Therefore this subset of the reals in [0,1] cannot > >be enumerated; the assumption is false. > > > >Therefore, the set of sequences of '5' and '7', > >and the reals they represent, cannot be bijected > >with the natural numbers, and a fortiori, neither > >can their superset of reals. > > Yes, that's a better argument. It also shows that the set of subsets of N is uncountable, because each sequence of the digits '5' and '7' can be seen as picking out a subset of N -- if '5' occurs in the nth place of the sequence, then n is in the subset, otherwise n is not in the subset. -- hz |