\problemdata
{S00 ps1}
{predicate}
{logic}

\begin{problem} \mbox{}
\begin{problemparts} 

\problempart
Show that $\forall x P(x) \lor \forall x Q(x)$ is not logically
equivalent to $\forall x (P(x) \lor Q(x))$.

\solution{
The universal quantifier does not distribute over OR.  
Even if $\forall x (P(x) \lor Q(x))$, 
there may be two elements, $c_1$ and $c_2$, such that 
$P(c_1) \land \neg Q(c_1) \land \neg P(c_2) \land Q(c_2)$, 
and thus, $\neg (\forall x P(x) \lor \forall x Q(x))$. 

For example, suppose the universe of discourse is $\mathbb{N}$,
$P(x)$ is the proposition ``$x$ is even,'' and $Q(x)$ is the
proposition ``$x$ is odd.''  
It is not true that every natural number is even 
(i.e., $\neg \forall x P(x)$), 
nor is it true that every natural number is odd 
(i.e., $\neg \forall x Q(x)$). 
However, every natural number is either even or odd 
(i.e., $\forall x (P(x) \lor Q(x))$). 
}

\problempart 
Show that $\exists x (P(x) \implies Q(x))$ is logically equivalent to
$\forall x P(x) \implies \exists x Q(x)$.

\solution{
First we show that the existential quantifier does distribute over OR:

\textbf{Lemma:} 
$\exists x (P(x) \lor Q(x))
                \Longleftrightarrow \exists x P(x) \lor \exists x Q(x)$. 

\textit{Proof:} 
In class, we showed one direction, 
that $\exists x (P(x) \lor Q(x))
                \Longrightarrow \exists x P(x) \lor \exists x Q(x)$. 
To see the other direction, 
suppose $\exists x P(x) \lor \exists x Q(x)$. 
We proceed by cases:
\begin{description}

\item[Case 1 ($\exists x P(x)$): ]
By existential instantiation, 
$P(c)$ for some $c \in U$. 
Therefore $P(c) \lor Q(c)$, 
and by existential generalization, 
$\exists x (P(x) \lor Q(x))$. 

\item[Case 2 ($\exists x Q(x)$): ]
This is exactly analogous to the previous case. 

\item[Exhaustive cases: ]
Since we have covered both disjuncts of our supposition, the two cases above are exhaustive.
\qed

\end{description}

We use this lemma in the following proof:
\begin{align*}
\exists x (P(x) \implies Q(x)) 
        & \Longleftrightarrow \exists x (\neg P(x) \lor Q(x)) 
                & \text{(truth table of $\implies$)} \\
        &\Longleftrightarrow \exists x \neg P(x) \lor \exists x Q(x) 
                & \text{(above lemma)} \\
        &\Longleftrightarrow \neg \forall x P(x) \lor \exists x Q(x) 
                & \text{(negation of $\forall$)} \\
        &\Longleftrightarrow \forall x P(x) \implies \exists x Q(x) 
                & \text{(truth table of $\implies$)} \\
\end{align*}
}
\end{problemparts}
\end{problem}
