Prove that A contains N elements and the different subsets of A is equal to 2?

Answer 1

Assuming the question is: Prove that a set A which contains n elements has 2n different subsets.

Proof by induction on n:

Base case (n = 0): If A contains no elements then the only subset of A is the empty set. So A has 1 = 20 different subsets.

Induction step (n > 0): We assume the induction hypothesis for all n smaller than some arbitrary number k (k > 0) and show that if the claim holds for sets containing k - 1 elements, then the claim also holds for a set containing k elements.

Given a set A which contains k elements, let A = A' u {.} (where u denotes set union, and {.} is some arbitrary subset of A containing a single element no in A'). Then A' has k - 1 elements and it follows by the induction hypothesis that (1) A' has 2k-1 different subsets (which also are subsets of A). (2) For each of these subsets we can create a new set which is a subset of A, but not of A', by adding . to it, that is we obtain an additional 2k-1 subsets of A. (*)

So by assuming the induction hypothesis (for all n < k) we have shown that a set A containing kelements has 2k-1 + 2k-1 = 2k different subsets. QED.

(*): We see that the sets are clearly subsets of A, but have we covered all subsets of A? Yes. Assume we haven't and there is some subset S of A not covered by this method: if S contains ., then S \ {.} is a subset of A' and has been included in step (2); otherwise if . is not in S, then S is a subset of A' and has been included in step (1). So assuming there is a subset of A which is not described by this process leads to a contradiction.