Is there an issue with the reasoning behind this inductive proof for a set X having $2^n$ subsets?

Question

I understand the normal inductive proof behind there being $2^n$ subsets for a given set X, however, I was wondering if our inductive hypothesis was to assume that the statement holds for n, then would be valid to consider a new set Y = XU{a} with n+1 elements and say "Let's remove an element from set Y, we then have a set with n elements and by our inductive hypothesis this will have $2^n$ elements."

I feel like there has to be something off here, but I can't tell what. My confusion stems from the fact that I've seen inductive proofs like in graph theory for example where if we were doing induction on the number of edges, in the k+1 case we can remove an edge and note that the resulting graph is one covered by our hypothesis. Similarly, in a question I did with an m x n grid, for the k+1 case, i.e. for the a grid of larger size we just had to remove a row or column in a certain way such that we are back in a case covered by our hypothesis.

Those proofs for those questions made sense to me, so I'm wondering if it isn't valid to use the same idea in this case, why not? What is the difference? Also, if the specific example questions are required, I will try and find them

Thanks

Answer 1

As mentioned by lulu, there is nothing wrong with your one line statement, but you need a complete proof.

Step case: Assume for any set $X$ with $n$ elements there exist a bijective mapping

$\tag 1 \phi_X: \{1,2,3,\dots,2^n\} \to \mathcal P(X)$

and $Y$ has $n + 1$ elements. Select an element $a \in Y$ and set $Z = Y \setminus \{a\}$. By our assumption there exist a bijection

$\tag 2 \phi_Z: \{(1,n),(2,n),(3,n),\dots,(2^n,n)\} \to \mathcal P(Z) \hookrightarrow \mathcal P(Y)$

We define a mapping $\mu_Y : \{(1,n+1),(2,n+1),(3,n+1),\dots,(2^n,n+1)\} \to \mathcal P(Y)$ with

$\tag 3 (k, n+1) \mapsto \phi_Z(k,n) \cup \{a\}$

Let

$\tag 4 N = \{(1,n),(2,n),\dots,(2^n,n)\} \cup \{(1,n+1),(2,n+1),\dots,(2^n,n+1)\}$

The set $N$ contains $2^n + 2^n$ elements, or said another way, $|N| = 2^{n+1}$.

We define a mapping $\phi_Y$ on $N$ by

$$ \phi_Y(k,y) = \left\{\begin{array}{lr} \phi_Z(k,y), & \text{when } \phi_Z \text{ is defined on } (k,y) \\ \mu_Y (k,y), & \text{when } \mu_Y \text{ is defined on } (k,y) \end{array}\right\} $$

It is easy to see that $\phi_Y$ is a bijection between $N$ and $\mathcal P(Y)$.

The proof of the inductive step case has been completed.

Answer 2

Think about it this way: if $S\subseteq A$, every element of $A$ has two possibilities: either it is in $S$ or it isn't. If you're comfortable with the standard counting principles, this means there are $2^n$ possible subsets.

If you'd rather prove it by induction: pick some $a \in A$. Then, each subset $S\subseteq A$ has two possibilities: either it contains $a$ or it doesn't.

Case 1: $a \not \in S$. Then, the inductive hypothesis tells us that there are $2^{n-1}$ such subsets.

Case 2: $a \in S$. There is a 1-1 correspondence between the subsets containing $a$ and the subsets not containing $a$ (think about how I might prove this). Then, there also $2^{n-1}$ such subsets.

Putting these together, there are a total of $2^{n-1} + 2^{n-1} = 2^n$ subsets of $A$.