# Inductive definition of power set for finite sets

I'm stuck on a problem using recursive definitions:

Let $X$ be a finite set. Give a recursive definition of the set of all subsets of $X$. Use Union as the operator in the definition.

I can see how the union of all subsets separately gives a set of all subsets, but I don't understand how to prove it. I'm not even sure what the base case would be in this situation.

• Base cases, empty set and singletons. Feb 16 '15 at 17:22
• Suppose $X$ is a finite set and $x^* \notin X$. Describe all the subsets of $X \cup \{x^*\}$. Hint: If $A \in 2^{X \cup \{x^*\}}$, then either $x^* \in A$ or $x^* \notin A$. Feb 16 '15 at 17:24
• I've added to my answer something which might be more appealing to you, as a CS student. Feb 16 '15 at 17:36

For induction you have to define some explicit base case, what is the smallest finite set? The empty set. Define its power set explicitly.

Now suppose that you defined the power set of a set with $n$ elements, and $A=\{a_0,\ldots,a_n,a_{n+1}\}$, find a way to write $A$ as the union of $A'$ and a singleton, with $A'$ having $n$ elements; now ask yourself, what sort of subsets of $A$ are there, and how do they relate to subsets of $A'$ and that additional singleton?

Since you're a computer science student (according to the user's profile), here is another way to think about it.

Recall that there is a canonical identification between subsets of $\{0,\ldots,n-1\}$ and binary strings of length $n$. Namely, $A\subseteq\{0,\ldots,n-1\}$ is mapped to the string $\langle a_0,\ldots,a_{n-1}\rangle$ such that $a_i=0$ if and only if $i\notin A$.

Now you can think about this as defining a string of length $n+1$ as a concatenation of a string of length $n$ with either $0$ or $1$.

Let $X_n = \{1, 2, \dotsc, n\}$ be the finite set of $n$ elements (unique up to a bijective morphism). Denote the power set of a set $X_i$ as $\mathcal{P}(X_i)$. Let's write out the first few power sets of these finite sets: \begin{align} \mathcal{P}(X_0) = \mathcal{P}(\{\}) &= \{\{\}\} \\ \mathcal{P}(X_1) = \mathcal{P}(\{1\}) &= \{\{\},\{1\}\} \\ \mathcal{P}(X_2) = \mathcal{P}(\{1,2\}) &= \{\{\},\{1\},\{2\},\{1,2\}\} \\ \mathcal{P}(X_3) = \mathcal{P}(\{1,2,3\}) &= \{\{\},\{1\},\{2\},\{1,2\}, \{3\},\{1,3\},\{2,3\},\{1,2,3\},\} \\ \end{align}

We can see that each $\mathcal{P}(X_i)$ consists of elements $s$ and $s\cup \{i\}$ for each $s \in \mathcal{P}(X_{i-1})$. In other words: $$\mathcal{P}(X_i) \;= \bigcup_{s \in \mathcal{P}(X_{i-1})} \Big\{s, s\cup\{i\}\Big\} \;\;=\;\; \mathcal{P}(X_{i-1}) \cup \big\{s\cup\{i\} \mid s \in \mathcal{P}(X_{i-1})\big\}$$

• The finite set with $n$ elements? Feb 16 '15 at 17:33
• @egreg, right. I've edited the answer to clarify. Feb 16 '15 at 17:44

Since the set is finite, without loss of generality, assume that $X_n = \{1,2, \ldots, n\}$. Then, note that: $$\mathcal{P}(X_1) = \mathcal{P}(\{1\}) = \{\phi,\{1\} \} = \{\phi, X_1\}$$ $$\mathcal{P}(X_n) = \mathcal{P}(X_{n-1}) \cup \{Y \cup \{n\} : Y \in\mathcal{P}(X_{n-1})\}\; \forall \; n \ge 2$$

This is a recursive definition of $\mathcal{P}(X_n)$ with only union as the operation in the definition. In language of sets, the power set of $X = X_n$ is just the union of power set of $X_{n-1}$ and the set of unions of $\{n\}$ with elements of $\mathcal{P}(X_{n-1}) \; \forall \; n \ge 2$.

One can show that: $$P(A\cup B)=\{a\cup b : (a,b)\in P(A)\times P(B)\}$$ which is a recursive definition (very clearly if we take $B$ to be a singleton disjoint from $A$). It states that to get the power set of a union $A\cup B$, we choose any pair of a subset $a\subseteq A$ and $b\subseteq B$ and take their union. In particular, for disjoint $A$ and $B$, we can show, using the above definition, that: $$|P(A\cup B)| = |P(A)|\cdot |P(B)|$$ implying that the size of a power set is exponential in the size of the original set. Computing the power set of a singleton set $\{s\}$ tells you the base of the exponent.