Prove that 2n>n

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ⁿ elements in the power set, hence we have the notation.

It looks obvious that 2ⁿ>n. Well, it is quite obvious when it is finite. 2³>3, 2⁴>4, how hard is that?

However, when n is infinite, 2ⁿ is also infinite. To compare two infinite sets is tricky. Well, it is easy to see that 2ⁿ≥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. 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.