# 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!

• Any "elementary" set operation would be allowed, I edited to clarify this. – Roland May 9 '15 at 14:57
• To clarify, by "complement", do you mean the operation taking a set $S$ to $\{1,\ldots,n\}\setminus S$? – Tad May 10 '15 at 0:50
• Isn't it just $\lceil\log_2n\rceil$? I.e. working with subsets of $\{0,\dots,n-1\},$ let $S_k$ be the set of numbers whose $k$-th binary digit (from the right) is a $1$? – bof May 10 '15 at 1:14
• Ah, of course! It is indeed logarithmic in n. I did not see this -- then the problem is quite easy. Thanks! – Roland May 10 '15 at 7:42

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

• Very nice! This logarithmic behavior will be very important for me. In retrospect it now seems obvious, but doesn't it always :) – Roland May 10 '15 at 7:44

We may use Sperner's Theorem to show the bound $${n}\choose{\lfloor n/2\rfloor}$$

• Thanks! The related post on mathoverflow was very helpful. – Roland May 10 '15 at 7:45