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

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

(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\;$.

share|improve this answer

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.