Minimum Number of Sets Needed to Generate the Power Set Take a finite set $A$ with $|A|=n.$ Let $\mathscr{F}$ be the power set of $A$. What is the smallest number of sets needed to generate $\mathscr{F}$? That is, if $\mathscr{C}$ is a set of subsets of $A$, what is the minimum size of $\mathscr{C}$ such that $\sigma (\mathscr{C})=\mathscr{F},$ where $\sigma (\mathscr{C})$ denotes the sigma-field generated by $\mathscr{C}.$
My approach to this is to look at $\mathscr{C}$ being able to generate all the singletons of $A$. So we have an upper bound on the size of $\mathscr{C}$ at $n$, this comes from just letting $\mathscr{C}$ be the set of singletons. 
However, looking at the example of $A=\{ 1,2,3\},$ I can get a set that $\mathscr{C}=\{\{1,2\},\{2,3\}\}$ generates $\mathscr{F}$. So I know that $n$ is not the minimal size, but I am unsure how to go about finding the minimal size.
Thanks for any help! 
 A: The minimal such size is $\lceil \log_2 n \rceil$. 
To see this, we'll first show that if $|\mathscr{C}| < \lceil \log_2 n \rceil$, then $\mathscr{C}$ cannot generate $\mathscr{F}$. This follows from the fact that $2^{|\mathscr{C}|} < n$, so two elements of $A$ must appear in exactly the same sets of $\mathscr{C}$, so they will appear in exactly the same sets in $\sigma(\mathscr{C})$. However, there exist sets in $\mathscr{F}$ which contain one of these two elements but not the other, hence leading to a contradiction.
On the other hand, we'll show that there is a $\mathscr{C}$ with $|\mathscr{C}| = \lceil \log_2 n \rceil$ that suffices. Let $S_i$ be the subset of $\{0, 1, \dots, n-1\}$ consisting of those elements whose $i$th bit (from the right) equals $1$ (when written in binary), and let $\mathscr{C}$ be the collection of $S_i$ for $1 \leq i \leq \lceil \log_2 n \rceil$. Now, to construct any singleton $\{i\}$, let $X$ equal the set of positions $j$ such that the $j$th bit of $i$ is $1$, and let $Y$ equal the set of positions $j$ such that the $j$th bit of $i$ is $0$. It then follows that
$$\{i\} = \bigcap_{j\in X} S_j \cap \bigcap_{j \in Y} \overline{S_j}$$
and hence this set generates $\mathscr{F}$. 
