Re: CANTOR's theorem
- From: Virgil <ITSnetNOTcom#virgil@xxxxxxxxxxx>
- Date: Sun, 15 May 2005 12:08:07 -0600
In article <1116136479.569189.31760@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
mueckenh@xxxxxxxxxxxxxxxxx wrote:
> Virgil wrote:
> > In article <1116088861.173262.228860@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> > mueckenh@xxxxxxxxxxxxxxxxx wrote:
> >
> > > All those naturals n, which are mapped upon sets S(n) which do not
> > > contain n, form a set M. Call them non-generators. If e.g. 2 -->
> {1,3}
> > > then 2 is a non-generator. It is in M. M is in P(M). Hence there
> must
> > > be a natural m which is mapped upon M. M contains only the
> > > non-generators. If m is not in M, then it is a non-generator, and m
> > > must be included into M. But if m is in M, then it is not a
> > > non-generator and it must be removed. This dilemma cannot be
> solved.
> > > Therefore, no surjective mapping N --> P(N) is possible.
> > >
> > > That is the reasoning of the Cantorians.
> >
> > That looks vaguely like a parody of the proof that there does not
> exist
> > any surjection from any set to its powerset (set of all subsets of
> the
> > given set).
> >
> > The facts are these:
> >
> > Cantor's theorem:
> >
> > In Zermelo-Frnkel set theory, Cantor's theorem states that the power
> set
> > (set of all subsets) of any set S has a strictly greater cardinality
> > than that of S. In particular, the power set of a countably infinite
> set
> > is un-countably infinite. To illustrate the validity of Cantor's
> theorem
> > for infinite sets, just test an infinite set in the proof below.
> >
> > The proof
> >
> > Let f be any function from S into the power set of S. It must be
> shown
> > that f is necessarily not surjective. To do that, it is enough to
> > exhibit a subset of S that is not in the image of f.
> >
> > Such a subset is M = { x in S : x not in f(x)}
> >
> > To show that M is not in the image of f, suppose the contrary, that M
> is
> > in the image of f. Then for some y in A, we have f(y) = M.
> >
> > Now consider whether y in B or not. If y in M, then y in f(y), but
> that
> > implies, by definition of M, that y is not in M. On the other hand,
> if y
> > is not in M, then y in f(y) and therefore y is in M. Either way, we
> get
> > a contradiction.
> > Thus there cannot be any y in S with f(y) = M, and the mapping cannot
> be
> > surjective. QED.
> >
> >
> > > But it is wrong. Not the
> > > mapping is proven impossible but the set M cannot exist. It is an
> > > impossible set.
> > > Here is he proof. Consider the bijection P(N) --> P(N) which
> certainly
> > > does not suffer from too small a cardinality on either side. For
> > > instance consider the identical mapping id: P(N) --> P(N).
> > > Introduce the condition that the set {a,b,c,...} of all
> non-generators
> > > of the form {n} be the image of a set {m}. This condition which
> already
> > > is implicite in the mapping N --> P(N) cannot be satisfied.
> >
> > For the Identity Mapping from P(N) to P(N) we need only to find an
> image
> > set which is does not contain as a subset any singleton set. The
> empty
> > set as image springs to mind. So that falsifies WM's example with the
>
> > identity mapping on P(N).
>
> Here is an improved vesion: consider a mapping of N in P(N). This
> mapping need not be bijective, injective oder surjective. The only
> condition is that some natural number m be mapped on M = { x in S : x
> not in f(x)}.
>
> You see that this condition cannot be satisfied (even if M were empty).
> Therefoe the proof of Cantor's theorem does not prove anything about
> cardinalities. It proves only that the mapping on M is impossible in
> any case.
>
> Regards, WM
Since that estabishes that there cannot be any surjection from N to
P(N), it perfectly establishes that the cardinality of P(N) is greater
then that of N, Q.E.D.
.
- Follow-Ups:
- Re: CANTOR's theorem
- From: mueckenh
- Re: CANTOR's theorem
- From: mueckenh
- Re: CANTOR's theorem
- References:
- CANTOR's theorem
- From: mueckenh
- Re: CANTOR's theorem
- From: Virgil
- Re: CANTOR's theorem
- From: mueckenh
- CANTOR's theorem
- Prev by Date: Re: Math symbols in e-mail messages
- Next by Date: Re: CANTOR's theorem
- Previous by thread: Re: CANTOR's theorem
- Next by thread: Re: CANTOR's theorem
- Index(es):
Relevant Pages
|
