# Problem with proving equation. (Sets.)

I would like to ask you for helping me out with this problem. I had to prove this equation.

$$\left(\bigcap_i A_i\cap\bigcup_{i\text{ odd}}A_i\right)\triangle\bigcap_{i\text{ odd}}A_i=\left(\bigcap_i A_i\triangle\bigcap_{i\text{ odd}}A_i\right)\cap\bigcup_i A_i$$

I did following:

\begin{align*} \left(\bigcap_i A_i\cap\bigcup_{i\text{ odd}}A_i\right)&=\bigcap_i A_i\\ \left(X\cap\bigcup_i A_i\right)&=X \end{align*}

$X\subseteq\bigcup A_i$

And after this I modified the main equation. But I didn't prove that, that 2 equations are true in common. Is it a valid? Or I have to prove that? If yes, how to prove that?

Sorry for my english. Thanks

-
What does $\Delta$ mean? Also, is $i$ ranging over integers? – Braindead Nov 21 '12 at 20:02
I'd guess $\Delta$ is the symmetric difference, but definitely would be nice to see clarification on that – Thomas Andrews Nov 21 '12 at 20:03
Yea sorry for that, Δ is symmetric difference, and i is over integers. – Noturab Nov 21 '12 at 20:07
@Noturno - The first equality you wrote (just after "I did the following:") is false. ($A_1 \cap A_2 \cup A_1 \ne A_1 \cap A_2$) – Braindead Nov 21 '12 at 20:08
@Braindead - It's (($A_1$ $\cap$ $A_2$) $\cap$ $A_1$)= $A_1$ $\cap$ $A_2$ – Noturab Nov 21 '12 at 20:12

As $\ \bigcap_i A_i\subset \bigcup_{i\ {\rm odd}} A_i$ we have $$LHS=\bigcap_i A_i\ \triangle \ \bigcap_{i\ {\rm odd}} A_i\ .$$ On the other hand, since every $x$ in the considered universe belongs to $\bigcup_i A_i$ the $RHS$ is equal to its large parenthesis, i.e., equal to $LHS$.

Note that $\ \bigcap_i A_i\subset \bigcap_{i\ {\rm odd}} A_i\$. Therefore both sides of the stated equality describe the set of all $x$ which belong to all $A_i$ with $i$ odd, but not to all $A_i$ with $i$ even.

-

Suppose $A,B$ and $C$ are arbitrary sets such that $A\subseteq C\subseteq B$. Then $(A\cap B)\triangle C = A\triangle C$ holds because $A\subseteq B$ and $A\triangle C\subseteq B$ holds because $A,C\subseteq B$. But this implies $(A\triangle C)\cap B = A\triangle C$. Taking $A = \bigcap_i A_i, B=\bigcup_{i\text{ odd}}A_i$ and $C=\bigcap_{i\text{ odd}}A_i$, the proof is complete.

-

(This answer may look complex, but it really is simple in structure. I'm just going through things in baby steps.)

$\newcommand{\odd}[1]{#1\text{ is odd}} \newcommand{\even}[1]{#1\text{ is even}}$Using slightly different notations (from Dijkstra/Scholten and Gries/Schneider), we are asked to prove that $$\left( \langle \cap i :: A_i \rangle \;\cap\; \langle \cup i : \odd i : A_i \rangle \right) \;\triangle\; \langle \cap i : \odd i : A_i \rangle$$ and $$\left( \langle \cap i :: A_i \rangle \;\triangle\; \langle \cap i : \odd i : A_i \rangle \right) \;\cap\; \langle \cup i :: A_i \rangle$$ are the same sets.

For situations like these, for me the simplest and most mechanical route is to expand the definitions and apply the rules of predicate logic to simplify the resulting expressions. Which $\;x\;$ are in the first set?

\begin{align} & x \in \left( \langle \cap i :: A_i \rangle \;\cap\; \langle \cup i : \odd i : A_i \rangle \right) \;\triangle\; \langle \cap i : \odd i : A_i \rangle \\ \equiv & \;\;\;\;\;\text{"definitions of $\;\cap,\triangle\;$"} \\ & \left( x \in \langle \cap i :: A_i \rangle \;\land\; x \in \langle \cup i : \odd i : A_i \rangle \right) \;\not\equiv\; x \in \langle \cap i : \odd i : A_i \rangle \\ \equiv & \;\;\;\;\;\text{"definitions of $\;\cap,\cup\;$ quantifications"} \\ & \left( \langle \forall i :: x \in A_i \rangle \;\land\; \langle \exists i : \odd i : x \in A_i \rangle \right) \;\not\equiv\; \langle \forall i : \odd i: x \in A_i \rangle \\ \equiv & \;\;\;\;\;\text{"logic: $\;\forall \Rightarrow \exists\;$ in left hand side of $\;\not\equiv\;$, assuming an odd $i$ exists"} \\ & \langle \forall i :: x \in A_i \rangle \;\not\equiv\; \langle \forall i : \odd i : x \in A_i \rangle \\ \equiv & \;\;\;\;\;\text{"logic: rewrite as detailed below"} \\ (*) \phantom\equiv & \langle \forall i : \odd i : x \in A_i \rangle \;\land\; \lnot \langle \forall i : \even i : x \in A_i \rangle \\ \end{align}

Here we used the following logical rewriting step:

\begin{align} & \langle \forall z :: P \rangle \;\not\equiv\; \langle \forall z : Q : P \rangle \\ \equiv & \;\;\;\;\;\text{"split range of left quantification -- to bring out the structural similarity"} \\ & \langle \forall z : Q : P \rangle \land \langle \forall z : \lnot Q : P \rangle \;\not\equiv\; \langle \forall z : Q : P \rangle \\ \equiv & \;\;\;\;\;\text{"bring $\;\lnot\;$ to outside"} \\ & \lnot \left( \langle \forall z : Q : P \rangle \land \langle \forall z : \lnot Q : P \rangle \;\equiv\; \langle \forall z : Q : P \rangle \right) \\ \equiv & \;\;\;\;\;\text{"$\;p \equiv p \land q\;$ is one way to write $\;p \Rightarrow q\;$"} \\ & \lnot \left( \langle \forall z : Q : P \rangle \;\Rightarrow\; \langle \forall z : \lnot Q : P \rangle \right) \\ \equiv & \;\;\;\;\;\text{"$\;\lnot p \lor q\;$ is another way to write $\;\Rightarrow\;$; DeMorgan"} \\ & \langle \forall z : Q : P \rangle \;\land\; \lnot \langle \forall z : \lnot Q : P \rangle \\ \end{align}

And similarly for the second set, we have for all $\;x\;$,

\begin{align} & x \in \left( \langle \cap i :: A_i \rangle \;\triangle\; \langle \cap i : \odd i : A_i \rangle \right) \;\cap\; \langle \cup i :: A_i \rangle \\ \equiv & \;\;\;\;\;\text{"definitions of $\;\triangle,\cap\;$"} \\ & \left( x \in \langle \cap i :: A_i \rangle \;\not\equiv\; x \in \langle \cap i : \odd i : A_i \rangle \right) \;\land\; x \in \langle \cup i :: A_i \rangle \\ \equiv & \;\;\;\;\;\text{"definitions of $\;\cap,\cup\;$ quantifications"} \\ & \left( \langle \forall i :: x \in A_i \rangle \;\not\equiv\; \langle \forall i : \odd i : x \in A_i \rangle \right) \;\land\; \langle \exists i :: x \in A_i \rangle \\ \equiv & \;\;\;\;\;\text{"logic: rewrite as detailed above"} \\ & \langle \forall i : \odd i : x \in A_i \rangle \;\land\; \lnot \langle \forall i : \even i : x \in A_i \rangle \;\land\; \langle \exists i :: x \in A_i \rangle \\ \equiv & \;\;\;\;\;\text{"logic: leftmost $\;\forall \Rightarrow \exists\;$, assuming an odd $i$ exists"} \\ (**) \phantom\equiv & \langle \forall i : \odd i : x \in A_i \rangle \;\land\; \lnot \langle \forall i : \even i : x \in A_i \rangle \\ \end{align}

Since $(*)$ and $(**)$ are identical, both sets have the same elements $\;x\;$, and therefore they are equal.

Note that we needed to assume that the index set of $\;i\;$ does not contain only even numbers. For example, if $\;i\;$ ranges over $\;\{4\}\;$, then the first set is 'the universe' and the second is $\;A_4\;$.

-