Q:

Minimal collection of subsets to reconstruct singletons

I have come across the following problem in a technical application. For a given integer $n$, what is the minimal collection of subsets of $\{1,\dots,n\}$ such that all "singleton" sets $\{1\}, \{2\}, \dots, \{n\}$ can be "reconstructed" by set operations (intersection, union, set difference, complement) on those subsets?
For example, with $n = 5$ a possible collection is $S_1 = \{1,2,3\}, S_2 = \{2,3,4\}, S_3 = \{3,4,5\}$, because we can write
$$ \{1\} = S_1 \setminus S_2 \\
\{2\} = S_2 \setminus S_3 \\
\{3\} = S_1 \cap S_2 \cap S_3 \\
\{4\} = S_2 \setminus S_1 \\
\{5\} = S_3 \setminus S_2$$
In believe that in general, the sets $S_k = \{k,k+1,\dots,k+c-1\}$, $1\le k \le n-c+1$ and $c = \lceil n / 2 \rceil $ are sufficient, but I am not convinced they are minimal.
I am sure this problem has been studied in some context but I am not a professional mathematician and I don't even know where to look ... Any help appreciated!

A:

It turns out you can get by with only $\lceil \lg n\rceil$ sets, where $\lg$ as usual denotes logarithm base $2$.  I'll give a construction and prove that it is optimal.
Note that you can construct all singletons with set operations if and only if you can construct all subsets of $[n]=\{1,\ldots,n\}$; it can be useful to think of the latter as an equivalent goal.
For each $i\ge 0$, let $S_i$ be the subset of $[n-1]$ whose binary expansions contain a $1$ in the $i$-th position.  (We don't need to include $n$ in any of our sets; it's unnecessary, since the union of the $S_i$'s is $[n-1]$, so we can get the singleton $\{n\}$ by complementing.)  So $S_i$ is nonempty precisely when $n-1\ge 2^i$, i.e. $i<\lg n$.  Thus the nonempty $S_i$'s are indexed from $0,\ldots \lceil \lg n\rceil-1$.
It's easy to see how to get any singleton $\{k\}$ from the $S_i$'s: look at the binary expansion of $k$; if the $i$-th bit of $k$ is $1$ then $k\in S_i$, otherwise $k\in \bar{S_i}$.  Intersecting the appropriate sets for each $i$ leaves the singleton $k$.
The fact that this construction is optimal follows immediately from the fact that the free Boolean algebra generated by $m$ elements contains $2^{2^m}$ elements.
In a little more detail: the collection of all subsets of a given set forms a so-called Boolean algebra, under the correspondence $\wedge\leftrightarrow\cup$, $\vee\leftrightarrow\cap$, and $\neg\leftrightarrow\textrm{complement}$. Roughly, the free Boolean algebra $FA(m)$ on $m$ generators is the "largest" Boolean algebra that can be generated from the generators; the elements of $FA(m)$ are all of the non-equivalent Boolean expressions which can be formed from the given $m$ elements.  It is a standard result that $|FA(m)|=2^{2^m}$.  Any Boolean algebra $\mathcal{A}$ which can be generated by $m$ elements is a quotient of $FA(m)$, so in particular $\mathcal{A}$ can't have any more than $2^{2^m}$ elements.
To sum up, if $m$ subsets of $[n]$ can generate all subsets via set operations, then we must have $2^{2^m}\ge 2^n$, i.e. $m\ge \lceil\lg n\rceil$. The given construction achieves this bound.
You can turn this into a nice card trick.  Have someone think of a card, deal the deck into two piles, ask them which pile the card is in, pick up the cards and repeat 5 more times.  Then you can guess their card.  The point is that, at the $i$-th stage, the two piles correspond to the sets $S_i$ and $\bar{S_i}$.

