How to show that: $(a,b)$ is a member of $\bigcup \{A \times X \mid X \in C\}$ given that $(a,b)$ is a member of $A \times \bigcup C$? I have the following problem and I'm stumped by it. How can I show line 2 assuming line 1?


*

*$(a,b) \in A \times \bigcup C$                  (Assumption)

*SHOW: $(a,b) \in \bigcup \{A \times B \mid B \in C\}$


$(a,b)$ is an ordered pair.
$A \times \bigcup C$ is the cartesian product of $A$ and the union of $C$  
Thanks for your help.
 A: Really there's only one way to check that $(x,y)$ is an element of $X\times Y$. Check that $x\in X$ and $y\in Y$.
Now recall that $\bigcup C=\bigcup\{X\mid X\in C\}$, so if $(a,b)\in A\times\bigcup C$ it means that $a\in A$ and $b\in\bigcup C$. Now recall that $b\in\bigcup C$ if and only if there exists some $X\in C$ such that $b\in X$.
And I'll leave you to finish.
A: Start with what you know about $\;\times\;$ and $\;\bigcup\;$, which presumably are at least their definitions.$
\newcommand{\calc}{\begin{align} \quad &}
\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}
\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }
\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }
\newcommand{\endcalc}{\end{align}}
\newcommand{\ref}[1]{\text{(#1)}}
\newcommand{\then}{\Rightarrow}
\newcommand{\when}{\Leftarrow}
\newcommand{\true}{\text{true}}
\newcommand{\false}{\text{false}}
$ And start with the most complex expression $\ref{2}$, expand the definitions, and then work toward the other expression $\ref{1}$.
That could result in the following calculation: for all $\;a,b,A,C\;$,
$$\calc
    \tag{2}
    (a,b) \in \bigcup \{A \times B \mid B \in C\}
\op=\hint{expand definition of $\;\bigcup\;$ -- really the only thing to do}
    \langle \exists P : P \in \{A \times B \mid B \in C\} : (a,b) \in P \rangle
\op=\hint{expand set builder notation -- the only way to make progress}
    \langle \exists P : \langle \exists B : B \in C : A \times B = P \rangle : (a,b) \in P \rangle
\op=\hint{logic: simplify: merge the quantifications; one-point rule}
    \langle \exists B : B \in C : (a,b) \in A \times B \rangle
\op=\hint{expand definition of $\;\times\;$ -- again, the only thing}
    \langle \exists B : B \in C : a \in A \land b \in B \rangle
\op{\tag{*} =}\hints{logic: move conjunct not containing $\;B\;$ out of $\;\exists B\;$}\hint{-- driven by our desire to simplify}
    a \in A \;\land\; \langle \exists B : B \in C : b \in B \rangle
\op=\hint{definition of $\;\bigcup\;$ -- working towards $\ref{1}$}
    a \in A \;\land\; b \in \bigcup C
\op=\hint{definition of $\;\times\;$}
    (a,b) \in A \times \bigcup C
    \tag{1}
\endcalc$$
(The first three steps would often be combined in one single step, but I decided to write them separately for clarity.)
Note how this shows even more than the required $\;\ref{1} \then \ref{2}\;$.  Also note that the key step is $\ref{*}$: that step is the essence of why this a theorem.
