Subject: Why Cantor Was Wrong
Author: Cattabriga
Date: 18 Jul 99 20:55:51 -0400 (EDT)
Mark Adkins wrote:
>Cantor's diagonal proof of the uncountability of certain
>infinite sets (such as the set of real numbers) is fatally
>flawed. Cantor's proof begins with what is taken to be a
>complete list of real numbers. It then constructs "a real
>number not on the list" by a diagonal method which is no doubt
>familiar to those with a basic knowledge of this issue. Thus,
>his proof claims to demonstrate that the initial assumption
>(that the reals are countable) is false. In fact, the analytical
>flaw in Cantor's proof is in thinking that such a procedure
>would generate a real number at all. Since the list is
>assumed complete, there is no real number not on the list,
>and no such number can be generated. The flaw is in thinking
>that a procedure which can be applied to any single element of
>a complete list (to produce a single digit of the diagonal
>number), or to any finite number of elements of a complete list
>(to produce a finite number of digits of the diagonal number),
>or to any infinite *subset* of a complete list (to produce an
>infinite diagonal number, i.e. a real number -- albeit one
>elsewhere on the list) can be applied to a complete list as a
>whole. Obviously not, since this contradicts the axiomatic
>assumption that it is complete!
Good point! Till now none has never recognized that this
axiomatic assumption of completeness is incorrect. But not the
same does the theory itself! by means of its own axioms!
The explanation goes directly through Cantor's 'theorem'.
The axiomatic assumption of completeness of the list is
expressed by the axioms of ZF by means of the universal
quantifiers of the Subsets Axiom Schema
AzEyAx(x in y <-> x in z and P(x))
where the existential quantifier states the existence of
a set, i.e. GENERATES the fateful set.
Till now no objection about the fact that in Cantor theorem
the property P which define the incriminate set is in itself
a contradiction, a flaw (The axiom of comprehension was erased by
this reason and it was replaced by the above one which was
considered yielding no contradiction - what irony! the axioms
of the Subsets was constructed by Zermelo to prevent any
contradiction but finished to legitimate the use of the
property P as a contradiction of the kind (A <-> not A) within
Cantor's 'theorem' !).
But it's easy to show that the axioms of ZF itself firmly
objects to this assumption of completeness when the property
P is a contradiction.
By the same axiom of the Subsets the complementary set of the
incriminate Cantor's set
B = {x in A| x notin g(x)}
(which is only another notation for
Ax(x in B <-> x in A and x notin g(x)) )
can be defined
~B = {x in A| x in g(x)} (*
(which is only another notation for
Ax(x in ~B <-> x in A and not (x notin g(x)))
i.e. the relative complement of B in A).
Hence directly by the axiom of Extensionality
(AxAy[Az(z in x <-> z in y) -> x = y]) we get
(b in ~B <-> b in g(b)) -> ~B = g(b)
since A was 'already' defined (by Zermelo axiom ;-)
(b in ~B <-> b in g(b)) is only an example of the
above definition of ~B (*.
We can then derive by modus ponens
~B = g(b)
which is equivalent to
|-ZF not (B = g(b))
(where (B = g(b)) is diagonalization in Cantor's 'theorem').
In simple words, the axioms of ZF by themselves tell us that
to consider P = 'x notin g(x)' along Cantor's 'theorem' is
unacceptable, since in ZF the negation of the
diagonalization can be derived as a theorem of ZF.
More explanations can be found in
http://www.serdata.it/cattabriga/
I know you were talking of the Cantor's diagonal method over reals,
but Cantor's 'theorem' talk of the UNcountability of 'all' the
subsets of a given set and does it by diagonalization (i.e.
a self-referring procedure (i.e. an incontrovertible contradiction))
which is at the end the same thing of the diagonal method (...and
exactly the same of the Goedel formula in the 'theorem' of
UNcompleteness
for PA) and to understand/clarify precisely where the "axiomatic
assumption
of completeness" is wrong you must refer to the universal quantifiers
in front at the formula that usually mathematicians utilize for
defining sets!
I already posted all that in sci.math in the past.
Paola Cattabriga
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
Subject: Why Cantor Was Wrong
Author: Cattabriga
Date: 27 Jul 99 08:35:02 -0400 (EDT)
From: "Brian M. Scott"
In Message-ID: <[email protected]>
References: <[email protected]>
Brian M. Scott wrote:
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
> In Message-ID: <[email protected]>
> Martin Schlottmann wrote:
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
> is considered to be a one-to-one correspondence,
The proof of Cantor's theorem contains no such assumption. The
function
g is not assumed to be one-to-one (injective), and it is not assumed
to
map onto P(A). The rest of your objection is therefore irrelevant.
Brian M. Scott
In
Message-ID: <[email protected]>
References: <[email protected]>
Martin Schlottmann wrote:
>
> In Message-ID: <[email protected]>
> "Brian M. Scott" wrote:
>
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
>
> In Message-ID: <[email protected]>
> Martin Schlottmann wrote:
> > >
> > >
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
>
>
>
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
>
> is considered to be a one-to-one correspondence,
>Again, we don't consider this.
>
>We consider. An arbitrary function g. Defined
>on an arbitrary set A.
>
>We don't. Assume. Anything else. About. The function g.
--
Martin Schlottmann
It is clear now we were not referring to the same version of
the so-called Cantor's 'theorem'. All this is especially unfair
from Martin since he knew very well the 'version' I was
talking about, till from the beginning. I am sorry, as regard to
Brian M. Scott, for the misunderstanding.
Well, nothing come on this earth only to hurt. There are many
different versions of the so-called Cantor's 'theorem', but for sake
of brevity I will reproduce here only the two we were
talking/misunderstanding about, which are both extract from well-known
handbooks (references can be found in my hpg).
VERSION I --------------------------------------------------------
(Notation)
x <_{c} y and x =<_{c} y denote respectively that the set x has
cardinality properly less that the cardinality of y, and that the
set x has cardinality less than y.
x ~sim y denotes that the sets x and y are not equal in cardinality,
namely there exixts no one to one correspondence between
their elements.
x sim y denotes that the sets x and y are equal in cardinality,
namely there exixts a one to one correspondence between
their elements.
(Cantor's proposition)
For every set A in ZF,
A <_{c} P(A)
i.e. A =<_{c} (A) but A ~sim P(A).
(so-called Cantor's 'proof')
That A =<_{c} P(A) follows from the fact that the function
x |-> {x}
which associates with each member x of A its singleton
{x} is an injection. To complete the proof, we assume, toward
a contradiction, that there exists a one to one correspondence
g:A |-> P(A)
which establishes that A sim P(A) and we define the set
B = { x in A | x notin g(x)}.
Now B is a subset of A and g is a surjection, so there
must exist some b in A such that B = g(b) (diagonalization),
and (as for each x in A ) either b in B or b notin B.
(*) If b in B then b in g(b) since B = g(b),
so that b does not satisfy the condition which
defines B , and hence b notin B ,
contrary to hypothesis.
(**) If b notin B , then b notin g(b) , so that b now
satisfies the defining condition for B and hence
b in B, which again contradicts the hypothesis.
Thus we reach a contradiction from the assumption that the
bijection g exists.
------------------------------------------------------------------
This is the version I was referring with
<<...
1) g:A |-> P(A) ==>
2) B = {x in A| x notin g(x)} ==>
3) B=g(b) ==>
4) [(b in B) and (b notin B) and (b notin B) and (b in B)].
maybe you do not accept 3) after or before '|-', only for make you
happy,
we can consider it like
g:A |-> P(A), B = {x in A| x notin g(x)} |- [(b in B) and (b notin B)
and (b notin B) and (b in
B)]
...>>
in a previous posting, answering to Schlottmann when he was talking
of a proof by contradiction.
You both are instead talking of a 'proof' which we could
call 'constructive' of the following type:
VERSION II -------------------------------------------------------
(Notation)
x neq y denotes y is not equal to y.
x subseteq y denotes x is a subset of y.
(x subset y denotes x is a proper subset of y.)
(so-called Cantor's 'proof')
Let g:a |-> P(a). We will construct a subset b of a
that is not in ran g. Specifically let
i) b = { x in a | x notin g(x)}.
Then b subseteq a, but for each x in a
ii) x in b <-> x notin g(x).
Hence b neq g(x).
------------------------------------------------------------------
I wish to state very clearly I will tolerate no longer any mistaken
of B=g(b) (and |-ZF not (B = g(b)) of my previous postings), as
referring
to VERSION I, with [b neq g(x)] within VERSION II.
The reasons are simple VERSION II*[b neq g(x)] is a conclusion of a
deduction, while VERSION I* B=g(b) is a statement after or before '|-'
along a proof toward a contradiction ( an assumption if before, i.e.
"so there must exist some b in A such that B = g(b)"
in VERSION I, a consequence if after).
Of course in no case VERSION I* B=g(b) can be considered a conclusion.
(See Schlottmann's Message-ID: <[email protected]>
Sat, 24 Jul 1999 17:51:46 -0600)
Moreover the notation about set and function are different for the two
versions, thus no type of melting of the two versions will be no more
accepted.
All my previous postings were referring to VERSION I.
Let me resume what I tell about VERSION I:
about VERSION I ----------------------------------------------------
Let us connect again to the step of the definition of B within
VERSION I .
The relative complement can always be defined, C(B) = A - B
as the relative complement of B in A , i. e.
C(B) = { x in A | x notin B}.
One can easily see that
C(B) = { x in A | x in g(x)\}.
Then in ZF we have
g:A |-> P(A)
B = {x in A | x notin g(x)}
C(B) = {x in A | x in g(x)}
Thus B and C(B) are subsets of A , B U C(B) = A .
By its definition g is a surjection ( g:(B U C(B)) |-> P(B U C(B))
)
and for each b in A we have either b in B or b in C(B) ,
so there must exist some b in A such that either B=g(b) or
C(B)=g(b) .
Clearly, b in B or b in C(B) but not both, and B=g(b) or
C(B)=g(b) but not both. We then have the main consequence of taking
into consideration the definition of the relative
complement with respect to Cantor's argumentation in ZF.
Immediately by Exstensionality we get
(b in C(B) <-> b in g(b)) -> C(B) = g(b)
and hence by C(B) = {x in A | x in g(x)}
C(B) = g(b).
Moreover since b in B or b in C(B) but not both, and B=g(b) or
C(B)=g(b) but not both we have
not (B = g(b)).
In other terms, by the axiom schema of Subsets and the axiom of
Extensionality diagonalization is not true in ZF. The assertion
is false by
Extensionality. Accordingly (*) and (**) cannot be accomplished
in VERSION I and Cantor's 'theorem' does not hold in ZF.
In fact we have only two cases
1. b in B and C(B) = g(b), then b notin g(b) so that
b satisfies the condition which defines B, and hence b in B,
accordingly to the hypothesis;
2. b in C(B) and C(B) = g(b), then b in g(b)
so that b satisfies condition which defines C(B), and hence b in C(B),
accordingly to the hypothesis.
-------------------------------------------------------------
But you prefer now to utilize VERSION II.
Well we can do all that.
about VERSION II----------------------------------------------
In VERSION II*[b neq g(x)] is a conclusion and the 'proof'
in VERSION II has the form
g:a |-> P(a) ==>
b = { x in a | x notin g(x)} ==>
x in b <-> x notin g(x) ==> [b neq g(x)]
i.e.
g:a |-> P(a),
b = { x in a | x notin g(x)},
x in b <-> x notin g(x)|- [b neq g(x)]
(OF COURSE THIS IS NOT A PROOF FOR CONTRADICTION)
The treatment is already in the words of Martin:
>Yes, I can show that:
>Let x be an arbitrary member of A.
>Then x in B or x in ~B and not both.
>If x in B, then x not in g(x) by definition of B,
> hence not(B=g(x)) by extensionality.
>If x in ~B, then x in g(x) by definition of ~B,
> hence not(B=g(x)) by extensionality.
>In both cases not(B=g(x)), therefore,
>(Ax)(x in A -> not(B=g(x)).
>
>See? I have derived "B is not in the range of g"
>without any assumption on g apart that it is a
>function defined on A.
except that being not a 'proof' for contradiction (no restriction
on the use of generalization as regard to proof for contradiction),
we don't need extensionality here (which regards, in all my postings,
only VERSION I).
Let me formalize the proof as follows (where eq denotes equal):
g:a |-> P(a),
Aa(a in b <-> a notin g(a)),
(a in b <-> a notin g(a)),
((a in b <-> a notin g(a)) <-> (a notin b <-> not(a notin g(a)))),
((a in b <-> a notin g(a)) -> (a notin b <-> not(a notin g(a)))),
(a notin b <-> not(a notin g(a))),
Aa(a notin b <-> not(a notin g(a))),
Aa(a notin b <-> a in g(a)),
EyAx(x in y <-> x in a and x notin b),
y=c, (y not free in (x in a and x notin b),
EyAa(a in y <-> a notin b),
(a in c <-> a notin b),
(a in c <-> a in g(a)),
Ax(x in c <-> x in g(x)),
c eq g(x).
i.e.
g:a |-> P(a),
b = { x in a | x notin g(x)},
(x in c <-> x in g(x))|- [c eq g(x)].
The existence of c cannot be denied since
EyAx(x in y <-> x in a and x notin b) is an example of
Aussonderung, hence we have
constructed a subset c of a that is in ran g.
*********************************
>You keep saying this.
>And what does "g:[C(B) U B] -> P([C(B) U B])"
>have to do _at all_ with the question if
>g is surjective or not?
Well, as regard to VERSION I I already showed you all that
Version I----------------------------------------------------
g cant be surjective if within A is defined only B:
A
____________________
| | |
| | |
| | |
| | B |
| | |
| | |
| | |
____________________
but g can be surjective if within A is defined also C(B)
(for C(X)= the complement of X)
C(B) = { x in A | x in g(x)}:
A
____________________
| | |
| | |
| | |
| C(B) | B |
| | |
| | |
| | |
____________________
since
[C(B) U B] = A then g:[C(B) U B] |--> P[C(B) U B]
For the function g:[C(B) U B] -> P([C(B) U B]),
* letting C(B) = ... , there IS a b such that C(B)=g(b)
Hence, NOT(for any) function g: A->P(A) ,
* g is not surjective.
--------------------------------------------------------------
as regard to VERSION II maybe better you don't ask to me, you
could find it posted to sci.math next year ;-) .
On my personal point of view as regard to VERSION II
g:[C(B) U B] -> P([C(B) U B])
can lead to the proof that g can be surjective or that g can be
one-to-one working on the composition of functions and their
inverse. All young rebels are invited to think about.
(As regard to me, I am going to take my rest ;-)
Paola Cattabriga
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
Up to previous page:
March 2000 / Homepage / Paola Cattabriga