
Re: Peerreviewed arguments against Cantor Diagonalization
Posted:
Oct 29, 2012 10:38 PM


Arturo Magidin wrote:
> On Monday, October 29, 2012 9:37:20 AM UTC5, JRStern wrote: > > On Sun, 28 Oct 2012 19:20:51 0700 (PDT), Arturo Magidin > > > > <magidin@member.ams.org> wrote: > > > > > > > > >> How can this be unclear? > > > > > > > > > > Because I did not simply state the conclusion. > > > > > I gave you the "diagonal argument". > > > > > > > > I did not recognize the argument you gave as a/the "diagonal" > > > > argument. > > That suggests you are not very familiar with the argument. > > > I saw a separate argument for the same conclusion. > > It was not. > > > The diagonal argument as I've seen it starts with enumerations of > > > > numbers, selects out digits, and constructs from those digits, and > > > > then makes an assertion about the result. > > Like I said: if you want to discuss specific steps in a specific > argument, then you must provide that argument explicitly and in > detail. Otherwise, we may be talking about different things. > > I will allow that there are many expositions of the argument that are > not very precise, or very clear, or that are overly complicated (it > is very common to present the argument as an argument by > contradiction, although it really is not such). But that only makes > it all the more necessary that you be very explicit and very precise > about exactly what argument you are talking about. > > > > If you are questioning whether it is "coherent", then you should > > > > > point to whatever point you find incoherent, rather than simply > > > > > quote and then give a sentence fragment. > > > > > > > > This is (perhaps too obviously) not my area of expertise, and rather > > > > than try to present my own proof or even formal objection at this > > > > point  I came looking for further background. > > A common presentation of the corollary (which in reality can be > obtained from the presentation I gave), is the following: > > THEOREM. If N is the natural numbers, (0,1) are the real numbers > between 0 and 1, not inclusively, and f:N>(0,1) is any function, > then f is not onto. That is, there exists a real number r(f) (which > depends on f) such that f(n)=/=r(f) for every n in N. > > Proof. Suppose that f:N>(0,1) if any function from the natural > numbers to the numbers in (0,1) (this is equivalent to a function > from N to the reals, using the bijection between (0,1) and the reals > afforded by the arctan function and a simple linear map, like I did). > > I claim that f is not onto. > > To that end, for each n in N, consider the decimal expansion of f(n) > (if f(n) has two expansions, select the one with only finitely many > nonzero entries). That is, > > f(n) = Sum_{i=1}^infty (a_{n,i}/10^n) 0<= a_{n,i} <= 9 > > (this is equivalent to saying f(n) = 0.a_{1,1}a_{1,2}a_{1,3}.... is > the decimal expansion) > > We construct a sequence b_n of digits as follows: > > b_n = 5 if a_{nn}=/=5 > b_n = 6 if a_{nn} = 5. > > The existence of (b_n) is guaranteed by the Principle of Induction, > which is a theorem of ZF (follows from the construction of N, which > is welldefined by the Axiom of Infinity). > > Let r(f) = Sum_{i=1}^{infty} b_n/10^n. > > This is a real number, since the sequence is Cauchy. It is less than > 1, because it is term by term strictly smaller than Sum (9/10^n) = 1; > it is greater than 1 because it is term by term strictly larger than > Sum (1/10^n) = 0.11111.... Thus, r(f) is a real number in (0,1). > > I claim that r(f)=/=f(n) for all n. First, note that r(f) has a > unique decimal expansion; thus, if f(n) has two decimal expansions, > then it cannot equal r(f). Hence, in order to ensure that r(f)=/=f(n) > it suffices to show that there is a k such that b_k=/=a_{n,k} > (because either f(n) has a unique decimal expansion, in which case > the fact that b_k=/=a_{n,k} suffices; or else f(n) has two decimal > expansions, in which case it cannot equal r(f)). > > By construction, b_k=/=a_{k,k}; hence r(f)=/=f(n). Thus, r(f) is not > in the range of f, so f is not onto. QED > > As to its validity: we are assuming that f is given; the fact that > f(n) has a decimal expansion follows by construction of the real > numbers as equivalence classes of Cauchy sequences. Our ability to > define b_n is guaranteed by the fact that we know f and we know the > expansion of f(n) (because we know f); and the fact that we have > defined a full sequence follows by induction. That r(f) is a real > number follows because the sequence of partial sums is Cauchy, hence > it represents a unique real number. > >
You have made the proof slightly more rigorous by pointing out the antidiagonal is Real using Cachy sequences.
Two problems with this:
1. The cranks don't dispute the antidiagonal is a Real, so you are not addressing their issue (whatever it is, but its not that the antidiagonal is not Real).
2. Your average Cantor crank wouldn't recognise a decimal expansion is a Cauchy sequence, or that Cauchy sequences specify Real numbers.
You may have been better off proving P(S) > S (where you have access to the axioms of ZF) and then showing c > N is a special case where S = N. As of course others have done in this thread.
For whatever (never stated) reason cranks don't like the digit changing proof of the uncountability of R. Objections to the Powerset version of the proof are much less common.

