\problemdata
{S00 ps1}
{logic}

\begin{problem} Consider the following incorrect theorem:  
\[\text{If } \forall x \in A \; (x \ne 0) \text{ and }A \subseteq B \text{ then
}\forall x \in B \; (x \ne 0)\text{.}\] 

\vspace{-3ex}
\begin{problemparts}
\problempart What is wrong with the following proof of the theorem? Let $x$
be an arbitrary element of $A$.  Since $\forall x \in A \; (x \ne 0)$ we can
conclude $x \ne 0$.  Also, since $A \subseteq B$ we have $x \in B$.
Since $x \in B$, $x \ne 0$, and $x $ was arbitrary, we can conclude
(by universal generalization) that $\forall x \in B \; (x \ne 0)$.

\solution{
Universal generalization requires that the generalized variable be
arbitrarily chosen \emph{from the set over which we are
generalizing}. We selected $x$ arbitrarily from set $A$ but are
generalizing over a different (larger) set $B$, 
which is not a valid inference rule.   To use universal generalization,
we should imagine an adversary picking the worst possible element from
the set over which we are generalizing.  The proof must work even for that
worst case.
}

\problempart Give a counterexample to the theorem.
\solution{
Let $A = \mathbb{N^+}$ and $B = \mathbb{Z}$. 
}
\end{problemparts}
\end{problem}

