Prove by induction: For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $2^N$ subsets. [duplicate]

For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $2^N$ subsets.

How do I prove this by induction?

-

marked as duplicate by Git Gud, Davide Giraudo, Américo Tavares, Amzoti, Dominic MichaelisApr 3 '13 at 22:30

I missed that, sorry, @Git Gud. –  amWhy Apr 3 '13 at 21:49
@amWhy No problem. –  Git Gud Apr 3 '13 at 21:50
What have you tried? –  Hayden Aug 11 at 12:09
This should help you with the inductive step: How many subsets of $\{1,2,\dots,n,n+1\}$ do not contain $n+1$? How many subsets of this set, which contain $n+1$ are there? –  Martin Sleziak Aug 11 at 12:21

Of course the empty set has $0$ elements and $1 = 2^0$ subsets.

Suppose you know the result for every set with $N-1$ elements. Let $A$ be a set with $n > 0$ elements. Fix an element $a_0 \in A$. Then a subset $C$ of $A$ is one of two kinds:

1. If $a_0 \in C$, then $C = \{ a_0 \} \cup B$, where $B$ is a subset of $A \setminus \{ a_0 \}$, so by induction there are $2^{N-1}$ subsets here, or
2. $a_0 \notin C$, and then $C \subseteq A \setminus \{ a_0 \}$, and here there are also $2^{N-1}$ subsets here.

The total is $2^{N-1} + 2^{N-1} = 2^{N}$.

-

We'll prove it for the set $S_n = \lbrace 1,2,\cdots, n\rbrace$ but it works for any set with $n$ elements.

For $n = 0$ we have $S_0 = \emptyset$ so there is only one subset $\emptyset$: there are $2^0$ subsets.

For $n = 1$ we have $S_1 = \lbrace 1\rbrace$, The subsets are $\emptyset$ and $\lbrace 1\rbrace$: there are $2^1$ subsets.

Assume the property holds for $0\leq k \leq n$.

Note that if $A \in \mathcal{P}(S_n)$ then $A\cup \lbrace n+1\rbrace\in \mathcal{P}(S_{n+1})$

And if $(n+1) \in A' \in \mathcal{P}(S_{n+1})$ then $A' = A \cup \lbrace n+1\rbrace$ for some $A \in \mathcal{P}(S_n)$.

That means that we have as many subsets of $S_{n+1}$ that contain $(n+1)$ as subsets we have in $S_n$.

Note also that the subsets of $S_{n+1}$ that don't contain $(n+1)$ are exactly the subsets of $S_n$.

Therefore $\vert S_{n+1}\vert = 2\vert S_n\vert$.

But by induction, we know that $\vert S_n\vert = 2^n$, so $\vert S_{n+1}\vert = 2·2^n = 2^{n+1}$ as we wanted to prove.

-

You check it for $N=0$ to establish the induction base.

Now, for the induction step, assume the claim holds for $N=k$, and let $S$ be a set with $k+1$ elements. Pick an element $a\in S$ and fix it for the rest of the proof. Now, any subset $B\subseteq S$ either contains $s$ or it does not. Consider these two cases separately. How many subsets $B\subseteq S$ are there that do not contain $b$? Well, such a subset is simply a subset of $S-\{a\}$, and so you can use the induction hypothesis to answer that. How many subsets $B\subseteq S$ are there that do contain $a$? Well, such a subset $B$ is completely and uniquely determined by $B-\{a\}$, which is just an arbitrary subset of $S-\{a\}$, so the induction hypothesis again tells you how many such subsets you have. Combine the two result to obtain a proof of the induction step, and thus the proof by induction is complete.

-

Hint. Verify for $N=0$, assume true for $N=n$ and prove for $N=n+1$, using the fact you know it for $n$ already.

-

Hint: If $N=\{a_1,\ldots,a_n\}$, then all subsets of $N$ can be obtained from subsets of $\{a_1,\ldots,a_{n-1}\},$ say $A$, by considering $A$ or $A\cup\{a_n\}$.

-

Let the statement be denoted by P(N) Case N=0. We have to prove P(0):set with zero elements has 2^0 (=1) subsets. Clearly a set with no elements is $\emptyset$ (null set) there fore has only $\emptyset$ as its subset.

Thus P(0) is true.

Case N=1. We have to prove P(1):set with one element has 2^1 (=2) subsets.

Clearly a set with 1 element has only 2 subsets,that and null set. Thus P(1) is true.

Now suppose P(x) is true where x $\varepsilon$ N. ie a set having x no. of elements has 2^x subsets.

we have to prove that P(x+1) is true when ever P(x) is true. P(x+1) : A set having x+1 elements has 2^(x+1) subsets. In this set we have n1,n2....nx and then nx+1 newly added. apart from the subsets that can be formed with n1,n2...nx. we can form subsets by choosing from any number among n1,n2...nx. ie.xC0+xC1+.... xCx = 2^x (xC0 for a set with nx+1 alone). Now trying to account for total number of subsets it becomes. 2^x+2^x = 2*2^x = 2^(x+1)

Thus by principle of induction P(x) is true for all x=0,1,2.

-
To format mathematics use tex code between dollar signs. E.g., $\emptyset$, the empty set, is formatted by writing \emptyset between dollar signs. –  Ittay Weiss Apr 3 '13 at 22:02
Thanks...Please upvote if u think answer is correct. –  Sreekanth Karumanaghat Apr 3 '13 at 22:07
you might also want to correctly format the rest of your answer. The answer is basically correct, but you should adhere to the standards of typesetting your posts with care. –  Ittay Weiss Apr 3 '13 at 22:09