Re: Power Set and Collection of finites subsets of N

On 22 Jan 2007 08:07:56 -0800, "iAGENT" <rahulgupta83@xxxxxxxxx>
wrote:

Hi,

I know that some of you had a long discussion regarding Countablility,
Uncountability and Diagonalization theorem.
But still the dicussions I went through couldn't solve my doubts.
Hence I am am here before you.

Let me explain what from my doubts arose?

In one of the exercises in a book ("Theory of Computation" author:
Lewis & Papadimitriou, 2nd Edition) that I am studying these days, they
asked me to prove that "The set of all finite subsets of N is
countable".
I divided the whole set into subsets of size 1, 2 ,3 and so on
and used the dovetailing technique to prove it.

Now following this, the author introduced Diagonalization theorem as
one of the fundamental proof techniques used.

I understood the technique, at least the definition and example but
then came the final blow.
A Theorem stating that the Power set of N is uncountable. The author
proved it using Diagonalization technique.

First thing I wasn't able to understand the theorem fully. The notation
wasn't clear to me. If anybody can provide me the proof using
diagonalization technique in a more palatable form, I would be obliged.

Suppose that the power set of N is countable. Then we can list all
the subsets of N in a sequence S[1], S[2], ...; each S[n] is a subset
of N and every subset of N is S[n] for some n.

Now let S be the set of all n in N with the property that
n is not an element of S[n]. (So for example if it happpens
that 1 is an element of S[1] then 1 is an element of S.
If it happens that 2 is not an element of N then 2 is
not an element of S. Etc.)

Then S is a subset of N, but S is _not_ equal to S[n]
for some n, giving a contradiction.

Why is S not equal to S[n]? Suppose that S = S[n].
Now either n is an element of S or not.
If n is an element of S then n is an element of
S[n], and hence by the definition of S it follows
that n is _not_ an element of S. On the other hand,
if n is not an element of S then n is not an element
of S[n], and hence by the definition of S it follows
that n _is_ an element of S. Contradiction.

And the bigger doubt is the following:

Power Set is collection of all subsets of N.
Can anybody tell me how Power Set is different from collection of
finite subsets of N?

Because the power set of N also contains infinite subsets of N.


************************

David C. Ullrich
.

Relevant Pages

  • Diagonalization theorem
    ... Uncountability and Diagonalization theorem. ... asked me to prove that "The set of all finite subsets of N is ... and used the dovetailing technique to prove it. ... A Theorem stating that the Power set of N is uncountable. ...
    (comp.theory)
  • Power Set and Collection of finites subsets of N
    ... Uncountability and Diagonalization theorem. ... asked me to prove that "The set of all finite subsets of N is ... and used the dovetailing technique to prove it. ... A Theorem stating that the Power set of N is uncountable. ...
    (sci.math)