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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A_0,\dots,A_{n-1}$ be sets for some whole $n>0$.

Take $A'_{0, i} = A_i$ and $A'_{1, i} = \bigcup ( \{ A_0, \ldots A_{n - 1} \} \setminus \{A_i\})$ for $i=0,\dots,n-1$.

Prove (or disprove) $$ \bigcup_{i=0}^{n-1} ( A_i \times A_i) = \bigcap_{i=0}^{n-1} \left( (A'_{0, i} \times A'_{0, i}) \cup ( A'_{1, i} \times A'_{1, i}) \right) . $$

share|cite|improve this question
By $$\bigcup\left(\{A_{0},\ldots, A_{n-1}\}\setminus A_{i}\right),$$ do you mean this: $$\bigcup_{j\neq i}A_{j}.$$ Or do you mean this:$$\left(\bigcup_{j=0}^{n-1}A_{j}\right)\setminus A_{i}.$$ – Unwisdom Mar 13 '14 at 17:44
@Unwisdom: I mean $\bigcup_{j\neq i}A_{j}$. (It can't mean something different.) – porton Mar 13 '14 at 17:46
Your notation is incorrect, then, if that is your meaning: $B\setminus A_i$ is the set of elements of $B$ not in $A_i$. If $B=\{A_1,\dots,A_{n-1}\}$, then $B\setminus A_i$ is the set of $A_j$ that do not belong to $A_i$. In particular, since $A_i\notin A_i$ under standard axioms, we have that $A_i$ is in this difference. – Andrés Caicedo Mar 16 '14 at 3:16
@AndresCaicedo: Thanks, corrected. – porton Mar 16 '14 at 12:58
up vote 2 down vote accepted

Thanks for the clarification. The result is false in general.

Suppose that $n=4$ and we have the following sets: \begin{eqnarray} A_0&=&\{a,x\}\\ A_1&=&\{b,y\}\\ A_2&=&\{c,x\}\\ A_3&=&\{d,y\}. \end{eqnarray}

Then \begin{eqnarray} A'_{1,0}&=&\{b,c,d,x,y\}\\ A'_{1,1}&=&\{a,c,d,x,y\}\\ A'_{1,2}&=&\{a,b,d,x,y\}\\ A'_{1,3}&=&\{a,b,c,x,y\}. \end{eqnarray}

Now, $\{x,y\}\subseteq\bigcap_{i=0}^{3}A'_{1,i}$, so trivially $$\langle x,y\rangle\in \bigcap_{i=0}^{3}\left( (A'_{0,i}\times A'_{0,i})\cup (A'_{1,i}\times A'_{1,i}) \right).$$

However, no single $A_{i}$ has both $x$ and $y$ as an element, so $$\langle x,y\rangle \not\in\bigcup_{i=0}^{3}(A_{i}\times A_{i}).$$

Thus $$\bigcup_{i=0}^{3}(A_{i}\times A_{i})\not\supseteq\bigcap_{i=0}^{3}\left( (A'_{0,i}\times A'_{0,i})\cup (A'_{1,i}\times A'_{1,i}) \right).$$

For what it's worth, the reverse inclusion is fine. It suffices to show that
$$(A_{i}\times A_{i})\subseteq(A'_{0,j}\times A'_{0,j})\cup (A'_{1,j}\times A'_{1,j})$$ for an arbitrary $i,j$. This is trivial for $i=j$ since $A_i=A'_{0,i}$. For $i\neq j$, it follows from the fact that $A_{i}\subseteq A'_{1,j}$.

share|cite|improve this answer

Your Answer


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.