Proof by mathematical induction in sets How would I go about writing a proof for this question? Is there too little information given about set A itself?
Prove by mathematical induction that |2^A| = 2^|A| for every finite set A.
I'm new to the idea of sets but I do know that 2^A is the powerset of A and |2^A| is the number of elements in the powerset of A.
E.g. A = {1,2,3}
2^A = { {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
|2^A| = 8 = 2^|A|
 A: A proof by induction involves proving a statement is true for all natural numbers. How do we turn your statement into a statement about natural numbers? For a finite set $A$, we must have $|A|=n$ for some $n\in\mathbb{N}$. This way, we can say "for all sets $A$ such that $|A|=n$ for some $n\in\mathbb{N}$, we have that $|2^A|=2^{|A|}=2^n$.
Now, for any proof by induction, you need two distinct subproofs: i) you have to prove the base case. ii) you have to prove the inductive step.
i) The base case is simply proving that your statement is true for $n=0$. Since $|A|=0$ implies $A=\emptyset$, this boils down to showing that $|2^\emptyset|=2^0$.
ii) This inductive step is the so called "lining up the dominoes". In this subproof, you have to show that when ever your statement is true for a natural number $k$, the statement has to be true for the next natural number, $k+1$. This requires proving an implication statement for all natural numbers. The implication statement you want to prove is that if $|2^A|=2^{|A|}$ is true for any set such that $|A|=k$, then it is true for any set $|A|=k+1$. How do you do this? You must assume $|2^A|=2^{|A|}$ is true for $k=|A|$ and then deduce $|2^A|=2^|A|$ for any set such that $k+1=|A|$.
A: Start with the empty set, so |A| = 0. Your formula can be shown to be true for this set. Then move to a set with cardinality $n$, and assume your hypothesis to be true. If you add one element to the set, then the power set doubles, because you start with the power set of the set with $n$ elements, then add same set, but to every set in the power set, add the $(n + 1)$st element. This doubles the number of sets in the original power set, hence showing that by adding one element to a set, you double the cardinality of its power set.
