Diagonalization theorem

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.

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?

.

Relevant Pages

  • 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)
  • Re: Power Set and Collection of finites subsets of N
    ... I know that some of you had a long discussion regarding Countablility, ... Uncountability and Diagonalization theorem. ... and used the dovetailing technique to prove it. ... A Theorem stating that the Power set of N is uncountable. ...
    (sci.math)