Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.