# Expressing a Set in an Indexed Collection by Intersections

I am struggling to prove the following question in basic set theory involving expressing a set in an indexed collection through intersections of sets and their complements. In particular,

Let $A_{1},...,A_{n}$ be subsets of a universal set $U$. Write $A_{i}^{1} = A_{i}$ and $A_{i}^{0}= \overline{A_{i}}$. Show that each $A_{i}$ is uniquely expressible in the form $$\bigcup_{i=1}^{2^{n-1}} A_{1}^{\delta_{i}^{1}} \cap A_{2}^{\delta_{i}^{2}} \cap \cdot \cdot \cdot \cap A_{n}^{\delta_{i}^{n}}$$ where $\delta_{i}^{j}$ is $0$ or $1$.

Any ideas on how I can prove this? I have no ideas for where to start and am not too sure what the upper bound $2^{n-1}$ on the union is derived from. I don't have any intuition on this question for why it is true either.

-

I’ll sketch an argument pretty fully but leave you to fill in some details and pretty it up a bit. The basic idea is that if you were to make a Venn diagram for the sets $A_1,\dots,A_n$, they’d chop the universe into $2^n$ pieces, each of which is an intersection of the form $A_1^{\delta_1}\cap\ldots\cap A_n^{\delta_n}$, and just $2^{n-1}$ of those pieces are in any given $A_k$. You might even want to stop reading here for a bit to see whether that’s enough of a hint.

Let’s look at $A_1$. Pick a point $x\in A_1$. For each $k\in\{1,\dots,n\}$ let

$$\delta_k(x)=\begin{cases} 1,&\text{if }x\in A_k\\ 0,&\text{if }x\notin A_k\;. \end{cases}$$

Show that $$x\in\bigcap_{k=1}^nA_k^{\delta_k(x)}\tag{1}\;.$$

Note that the expression in $(1)$ has the right form to be one of the terms in your big union.

Now $\delta_1(x)=1$ for every $x\in A_1$, so we can rewrite $(1)$ as

$$A_1\cap\bigcap_{k=2}^nA_k^{\delta_k(x)}\;.\tag{2}$$

If we take the union of a bunch of terms like $(2)$, that union will certainly be a subset of $A_1$. And if we have such a term for every $x\in A_1$, that union will pick up every $x\in A_1$ and will therefore have to be $A_1$:

$$A_1=\bigcup_{x\in A_1}\bigcap_{k=2}^nA_k^{\delta_k(x)}\;.\tag{3}$$

This isn’t quite what you want, because I’m taking the union of one term for each $x\in A_1$. However, if $x,y\in A_1$ happen to be in exactly the same $A_k$’s, i.e., if $\delta_k(x)=\delta_k(y)$ for $k=1,\dots,n$, then the $x$ and $y$ terms in $(3)$ will be identical. We’re taking a union, so there’s no need to keep multiple copies of the same term. Thus, $(3)$ reduces to a union of all of the different intersections

$$\bigcap_{k=2}^nA_k^{\delta_k(x)}\;.$$

There’s one of these for every possible combination of values of $\delta_2(x),\dots,\delta_n(x)$. Each $\delta_k(x)$ has two possible values, $0$ and $1$, and there are $n-1$ of them, so there are $2^{n-1}$ possible combinations of values.

Finally, there’s nothing special about $A_1$: you can make a similar argument for any $A_k$.

-