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.

Show that $\bigcup_i f(A_i) = f(\bigcup_i A_i)$, where $A_i$ are subsets of $X$ and $f: X\to Y$. It seems intuitively obvious but yet I cannot prove it....

share|improve this question
    
Suppose $x$ is in the $\cup_i f(A_i)$. Then $x$ is in $f(A_j)$ for some $j$ (by the definition of union). So there is a $y$ in $A_j$ such that $f(y) = x$ (by the definition of a function). This $y$ is in $\cup_i A_i$ (by the definition of union). So $f(y) = $x$ is in the right-hand side. –  Jonah Sinick Oct 30 '12 at 16:20
1  
The suspense is killing me... I just have to know! What have you tried? –  rschwieb Oct 30 '12 at 16:20

3 Answers 3

up vote 4 down vote accepted

This is easily proved by ‘element-chasing’: assume that $x$ is an element of the lefthand side and chase through the definition of union to show that $x$ is an element of the righthand side, then do the opposite. I’ll do one direction and let you try the other.

Suppose that $x\in\bigcup_{i\in I}f[A_i]$. By the definition of union this means that there is at least one $i_0\in I$ such that $x\in f[A_i]$. Since $x\in f[A_{i_0}]$, there is some $y\in A_{i_0}$ such that $x=f(y)$. That’s about as much as we can get directly from the hypothesis, so let’s see where we’re trying to go: we want to show that $x\in f\left[\bigcup_{i\in I}A_i\right]$.

Okay, we know that $x=f(y)$; is $y\in\bigcup_{i\in I}A_i$? If it is, then certainly $x=f(y)\in f\left[\bigcup_{i\in I}A_i\right]$, and we’re home free. And the answer is yes: $y\in A_{i_0}\subseteq\bigcup_{i\in I}A_i$, so $y\in\bigcup_{i\in I}A_i$, and therefore $x\in f\left[\bigcup_{i\in I}A_i\right]$. Since $x$ was an arbitrary element of $\bigcup_{i\in I}f[A_i]$, we’ve shown that $$\bigcup_{i\in I}f[A_i]\subseteq f\left[\bigcup_{i\in I}A_i\right]\;.$$

Now you try the same approach to prove that $$f\left[\bigcup_{i\in I}A_i\right]\subseteq\bigcup_{i\in I}f[A_i]\;;$$ once you’ve done that, you can conclude that $$\bigcup_{i\in I}f[A_i]=f\left[\bigcup_{i\in I}A_i\right]\;.$$

share|improve this answer

Let $y\in\cup_i f(A_i)$. Then $y\in f(A_j)$ for some $j$. Then $y=f(t)$ for some $t\in A_j$. But $t\in \cup_i A_i$ so that $y\in f\left(\cup_i A_i\right)$.

Let $y\in f\left(\cup_i A_i\right)$. Then $y=f(s)$ for some $s\in\cup_i A_i$. But $s\in A_l$ for some $l$ so that $y\in f(A_l)$. Hence $y\in\cup_i f(A_i)$.

share|improve this answer

Expanding the definitions and using predicate logic leads to a very simple and direct proof: with $\;i\;$ implicitly ranging over some index set, we calculate for all $\;y\;$,

\begin{align} & y \in \langle \cup i :: f\left[ A_i \right] \rangle \rangle \\ \equiv & \qquad \text{"definition of $\;\cup\;$ quantification"} \\ & \langle \exists i :: y \in f\left[ A_i \right] \rangle \rangle \\ \equiv & \qquad \text{"definition of $\;\cdot\left[\cdot\right]\;$"} \\ & \langle \exists i :: \langle \exists x : f(x) = y : x \in A_i \rangle \rangle \\ (*) \quad \equiv & \qquad \text{"logic: exchange $\;\exists\;$ quantifications -- really the only thing to do"} \\ & \langle \exists x : f(x) = y : \langle \exists i :: x \in A_i \rangle \rangle \\ \equiv & \qquad \text{"definition of $\;\cup\;$ quantification"} \\ & \langle \exists x : f(x) = y : x \in \langle \cup i :: A_i \rangle \rangle \\ \equiv & \qquad \text{"definition of $\;\cdot\left[\cdot\right]\;$"} \\ & y \in f\left[ \langle \cup i :: A_i \rangle \right] \\ \end{align} which (by set extensionality) proves $\;\langle \cup i :: f\left[ A_i \right] \rangle \rangle = f\left[ \langle \cup i :: A_i \rangle \right]\;$ as required.

Note how the key step is $(*)$.

Note also how we did not have to have separate $\;\Rightarrow\;$ and $\;\Leftarrow\;$ proofs: we proved both directions at the same time.

Finally, note that a similar proof would not work for $\;\cap\;$ instead of $\;\cup\;$: most we could prove there would be $\;\langle \cap i :: f\left[ A_i \right] \rangle \rangle \supseteq f\left[ \langle \cap i :: A_i \rangle \right]\;$, using $\;\exists\forall \Rightarrow \forall\exists\;$.

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.