Is there an intuition for why power sets come in powers of $2?$

Question

My title is a bit sloppy. First let me say that I perfectly understand the proof that $|P(S)|=2^{|S|}$, I am not asking for an easy to understand proof. My question is more whether there is an intuitive reason why we should expect:

• $|P(S)|$ to be a power of the size of $S$ (by this I mean $|P(S)|=n^{|S|}$ for some $n\in\mathbb{N}$)
• this power to be a power of $2$

In other words, is there anything inherent to the power set operation that should suggest the cardinalities of power sets come in powers of $2?$

(I am not saying there should be - "no, that is just how it is" is a perfectly acceptable answer, if it is indeed so)

Answer 1

Yes. And it's very easy once you understand the proof of the general case, not the finite case.

The reason is that given a set $A\subseteq S$ we have to make $|S|$-many choices of "yes" or "no", whether or not an element is in $A$ or not in $A$.

Answer 2

Consider the set $S=\{a_1,a_2,a_3,\cdot,a_n\}$

The number of subsets of this is equal to $|P(S)|$ by definition.

Any subset can be selected in $2^{n}$ ways, because for every element $a_i$ we have two choices, either to include it in the subset, or to exclude it. Thus $2^{n}$ subsets can be formed, following form the Fundamental Principle of Counting by multiplication.

Is that intuition enough?

Or if you prefer algebra:

Number of subsets is equal to $$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}$$

We have, $$(1+x)^n = \binom{n}{0}+\binom{n}{1}x+\cdots+\binom{n}{n}x^n$$

Substitute $x=1$ and we are done.