# Index Set Notation Proof

I can reason this out intuitively (it seems obvious), but I can't seem to formalize a proof.

Prove $\left(\bigcup_{\alpha\in J} A_{\alpha}\right)^c = \left(\bigcap_{\alpha\in J} A^c_\alpha\right)$

Any thoughts?

-
The notion is just throwing me off on where to begin. I can see its a short proof, but its not like the other set proofs that I'm used to and thus, I've hit a roadblock. – Peej Gerard Jan 24 '13 at 20:09

If $A$ and $B$ are two sets and you want to prove that $A=B$, then the standard way to do this is to show that $A\subset B$ and $B\subset A$. In order to show $A\subset B$, you need to show that $x\in A$ implies $x\in B$. Similarly for $B\subset A$ you need to show that $x\in B$ implies $x\in A$. I will help you to get started with the first implication.

Start by choosing $x\in (\bigcup_{\alpha\in J} A_{\alpha})^{c}$ and try to conclude that $x\in\bigcap_{\alpha\in J}A_{\alpha}^{c}$. Since $x\in (\bigcup_{\alpha\in J} A_{\alpha})^{c}$ then $x\notin \bigcup_{\alpha\in J} A_{\alpha}$ by definition of complement, so $x\notin A_{\alpha}$ for every $\alpha\in J$. Because if on the contrary there would exist $\alpha\in J$ so that $x\in A_{\alpha}$, then what would this say about the assumption $x\notin \bigcup_{\alpha\in J}A_{\alpha}$? Can you continue from here?

Remember that in general $x\in \bigcup_{i}A_{i}$ means that there exists $i$ so that $x\in A_{i}$ and $x\in\bigcap_{i}A_{i}$ means that $x\in A_{i}$ for all $i$.

-
I follow your conclusion that $x\notin A_{\alpha}$ for every $\alpha\in J$. Isn't this equivalent to right hand side, $x\in\bigcap_{\alpha\in J}A_{\alpha}^{c}$? If $x\notin A_{\alpha}$ for every $\alpha\in J$, that is the same as, $x\in A^{c}_{\alpha}$ for every $\alpha\in J$. Which is what the righthand side says. – Peej Gerard Jan 24 '13 at 20:33
Exactly. Can you show the other implication? – T. Eskin Jan 24 '13 at 20:34
I assume we just reverse it. Sorry to be lazy with latex, but essentially we prove the subset in the other direction? – Peej Gerard Jan 24 '13 at 20:38
If $x\in\bigcap_{\alpha\in J}A_{\alpha}^{c}$, then $x$ is in the intersection of all the sets $A^{c}_{\alpha}$. Can this imply that (applying the complement), $x$ is not the union of $A_{\alpha}$? This statement would seem to imply the lefthand side. – Peej Gerard Jan 24 '13 at 20:41
True. You got it. – T. Eskin Jan 24 '13 at 20:44

Hint: Recall that the definition of $x\in\bigcup_{i\in I} X_i$ is that for some $i \in I$, $x\in X_i$. Use the similar definition for intersection and complement and show two-sided inclusions.

-
So if I let $x\in\bigcup_{\alpha\in J} A_\alpha$, that means that for some $\alpha \in J$, there exists an $x \in A_\alpha$? What does the complement of this entail? – Peej Gerard Jan 24 '13 at 20:15
It means that $x$ is not in the union. What is the negation of "there exists ..."? – Asaf Karagila Jan 24 '13 at 20:32
There does not exist...I think I see, so it essentially says that $x$ is in the intersection of the sets $A^{c}_{\alpha}$. Seems like all that was done was apply the definition of complements? – Peej Gerard Jan 24 '13 at 20:37
Give and take. :-) – Asaf Karagila Jan 24 '13 at 20:38
haha i'm sorry, you're saying that I'm correct, that is all we did essentially? – Peej Gerard Jan 24 '13 at 20:42