Expert: Sherry Wallin - 10/16/2009

Question
Hi

could you plz give me a hint about the problem below:

Use induction on the size of S to show that if S is a finite set , then |2^S| = 2^|S|.

actually i can't understand if S is a set like S = {a , b} , how can we define something like 2^S for it and what does 2^S indicates?

thanx
Bita


Answer
Bita~
    You are looking at the characteristic of the set and namely that characteristic is the size of the set S. You are wanting to show that if S is finite then the absolute value of the number of elements in the set S is 2 to the absolute value of the number of elements in the set. This should seem reasonable since the number of elements in any set is at least 0 in which case you have just the empty set (1 element and 2^0 = 1). The point I am making is that the power is non negative regardless of the size of S so certainly the absolute value of a non negative number is non negative. Use induction on n, the number of elements in the set S, i.e., let n = 'size of S'

Outline of the proof by induction:
When n = 0 then |2^n| = |2^0| = |1|= 1, so it is true for n = 0
When n = 1 then |2^n| = |2^1| = |2| = 2, so it is also true for n = 1 (you may or may not need to use this in your proof depending on how you show it)

Suppose it is true for n = k, i.e, it assume it is true that |2^k|=2^|k|

Show it is true for n = k + 1:
|2^(k+1)| = ... (use your inductive step)... = 2^|k+1|   ...= you fill in the details

I hope this helps...


Math Prof