|
|
Re: Peer-reviewed arguments against Cantor Diagonalization
Posted:
Oct 28, 2012 6:25 PM
|
|
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.
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
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
--
Arturo Magidin
|
|
