# [Math] Inductive definition of power set for finite sets

elementary-set-theoryinduction

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.

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