JRStern
Posts:
34
Registered:
10/27/12
|
|
Re: Peer-reviewed arguments against Cantor Diagonalization
Posted:
Oct 28, 2012 8:27 PM
|
|
On Sun, 28 Oct 2012 15:25:27 -0700 (PDT), Arturo Magidin
<magidin@member.ams.org> wrote:
>On Saturday, October 27, 2012 4:49:32 PM UTC-5, JRStern wrote:
>> Are there any such published?
>
>You said elsewhere you are interested in "peer-reviewed" criticisms to
>Cantor's diagonal argument, but not from the point of view of intuitionism
>or some other logical framework, but strictly within the context of ZFC.
>
>There are no such things, because the argument is a valid argument
>within ZF. It is in fact pretty short and clear.
Then there can be a book taking on the objections one at a time and
knocking them down.
>Recall that given a set X, the Axiom of the Power Set states that
>there is a set Y such that z in Y if and only if z is a subset of X.
>We call this set the "power set of X", an denote it P(X).
>
>THEOREM (Cantor) Let X be any set, and let P(X) be the power set of
>X. If f:X->P(X) is any function, then f is not onto; that is, there
>exists B in P(X) that does not lie in the image of f.
>
>Proof. Let f:X->P(X) be a function. By the Axiom of Separation,
>
>B = {x in X | x is not an element of f(X)}
>
>is a subset of A, hence an element of P(X). We claim that f(y)=/=B for all y\in X.
>
>Indeed, let y in X. Either f(y)=/=B, or f(y)=B. If f(y)=B,
>then y in B -> y in f(y) -> y not in B; since (P->not(P))->not(P) is a tautology,
>we conclude that f(y)=/=B. So if y in X, then f(y)=/=B, proving that B is not
>in the image of f. QED
... and not just telling us that there are other theories with the
same consequent.
J.
>
>LEMMA 1: There is a bijection g:(0,1)->P(N), where P(N) is the power set of the natural numbers.
>
>Proof: There is an injection (0,1) to P(N) as follows: given any number x in (0,1), we can express x in base 2; if there are two expressions for x in base 2, then select the one with finitely many 1s. Map the number x = 0.a_1a_2a_3... to the set S = {n in N | a_n=1}. The map is easily seen to be one-to-one (given that we have specified which expansion to use).
>
>And there is an injection from P(N) to (0,1): given a subset X of N, let x be the real number Sum (a_n/10^n), where a_n=5 if n is not in X, and a_n=6 if n is in X. Again, this is easily seen to be an injection.
>
>Since we have an injection (0,1)->P(N), and an injection P(N)->(0,1), the Cantor-Bernstein-Schroeder Theorem guarantees (in ZF) the existence of a bijection g:(0,1)->P(N). QED
>
>
>COROLLARY: If f:N->R is any function, where N is the natural numbers and R is the real numbers, then f is not onto.
>
>Proof: First, there is a bijection h between R and (-pi/2,pi/2), given by the arctan function; and there is a bijection t between (-pi/2,pi/2) and (0,1), given by t(x) = (x+(pi/2))/pi. And from Lemma 1, we have a bijection g from (0,1) to P(N). Note that the compositum gth:R->P(N) is a bijection.
>
>Let f:N->R be any function. Then the compositum gthf is a function N->P(N). By Cantor's Theorem, this function is not onto. In particular, there exists a subset X of P(N) that is not in the image of gthf. Now let r = (gth)^{-1}(X) (the function (gth)^{-1} exists because gth is a bijection); then r is not in the image of f (for if r = f(n), then (gth)^{-1}(X) = f(n), so X = (gth)((gth)^{-1}(X)) = gth(f(n)) = gthf(n), which contradicts the choice of X).
>
>Thus, f is not onto, as claimed. QED
|
|
