*If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.*
(I am wondering if I shall add a "level-indicator" on the page, because somehow the level of knowledge is not quite even among my posts...)

Preliminary concept: A set is just a collection of objects. A (possible empty) part of the set is called a subset. The set consists of all subsets of a specified set is called the power set of the specified set.

e.g.

*A*={1,2,3,4} is a set. { }, {1}, {1 3}, and

*A* itself, are subsets of

*A*. The power set of

*A* is

P(*A*) ={{ }, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4},

{3,4}, {1,2,3}, {1,2,4}, {1,3,4},{2,3,4},{1,2,3,4} }
The power set of

*A*, can be denoted by P(

*A*) or 2

^{A}. It is not hard to see that for a set with n elements, there is exactly 2

^{n} elements in the power set, hence we have the notation.

It looks obvious that 2

^{n}>n. Well, it is quite obvious when it is finite. 2

^{3}>3, 2

^{4}>4, how hard is that?

However, when n is infinite, 2

^{n} is also infinite. To compare two infinite sets is tricky. Well, it is easy to see that 2

^{n}≥n: If

*A*={a,b,c,...} then the size of

*A* is the same as

{{a},{b},{c},...

} which is a subset of P(

*A*).

The hard part is: We have to make sure 2

^{n}≠n. In other words, we have to establish the fact that there is no one-to-one correspondence between

*A* and P(

*A*).

Consider a correspondence from

*A* to P(

*A*) such that any element

*a*∈

*A* corresponds to a subset S(

*a*)∈P(

*A*).
Since

*A* is infinite, we cannot write down all its elements, but we can have a local list:

....

α : ....α∈S(α)? β∈S(α)? γ∈S(α)? δ∈S(α)?

β : ....α∈S(β)? β∈S(β)? γ∈S(β)? δ∈S(β)? ....

γ : ....α∈S(γ)? β∈S(γ)? γ∈S(γ)? δ∈S(γ)? ....

δ : ....α∈S(δ)? β∈S(δ)? γ∈S(δ)? δ∈S(δ)? ....

....

It is a table of true and false. Now construct a new subset

*B* containing only those element

*a* such that the question

*a*∈S(

*a*)? is fales.

Note that if

*a*∈S(

*a*) then

*a*∉

*B* and so S(

*a*)≠

*B*; likewise if

*a*∉S(

*a*) then

*a*∈

*B* and so S(

*a*)≠

*B*. Hence the list

....α∈S(

*B*)? β∈S(

*B*)? γ∈S(

*B*)? δ∈S(

*B*)? ....

is different from any S(

*a*) at exactly the

*a*∈S(

*a*)?-position. (We can see now it is exactly the

Cantor's diagonal argument used in the previous two posts:

*Not enough names for numbers* and

*The are uncountably many subsets of natural numbers*)

Therefore no element of

*A* corresponds to B and so this correspondence is not a one-to-one correspondence. As this is just any correspondence, so one-to-one correspondence cannot exist.