[Math] 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.

Best Answer

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$.