\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

\psol{1}{February 13, 1997}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1.1 - 8
\problem

Let $p$, $q$, and $r$ be the following propositions:
\begin{center}
\begin{tabular}{cc}
$p:$ & You are a good water-polo player. \\
$q:$ & You are a good swimmer. \\
$r:$ & You are in the water-polo team. \\
\end{tabular}
\end{center}

Write the propositions using $p$, $q$, and $r$ and logical
connectives (e.g.  $\vee$, $\wedge$, $\neg$, $\Rightarrow$).

\begin{problemparts}

\problempart 
{\it To be in the water-polo team, it is sufficient for you to be a good water-polo player.}

We can rephrase this as ``If you are a good water-polo player,  you will be in the water-polo team.''

\( p \Rightarrow r \)


\problempart 
{\it Being a good swimmer and a good water-polo player is necessary
for getting into the water-polo team. }

\( r \Rightarrow p \wedge q \)
\problempart 
{ \it You will get in the water polo team if and only if you 
are a good swimmer or you are a good water-polo player. }

\( r \Leftrightarrow p \vee q \)
\problempart
{ \it You are neither a good swimmer nor a good water-polo player, yet you are in the water-polo team. }

\( \neg p \wedge \neg q \wedge r \)
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1.2 - 25 modified 
\problem Find a compound proposition involving the propositions $p$,
$q$, and $r$ that is false when exactly two of $p$, $q$, and $r$ are
false.  The compound proposition is true otherwise. 
\[ \neg ((\neg p \wedge \neg q \wedge r) \vee (\neg p \wedge q \wedge \neg r) 
\vee (p \wedge \neg q \wedge \neg r)) \]
which is equivalent to
\[ ((p \vee q \vee \neg r ) \wedge (p \vee \neg q \vee r ) \wedge (\neg p \vee q \vee r ))
\]
which is also equivalent to
\[
((p \wedge q) \vee (q \wedge r) \vee (p \wedge r)  \vee (\neg p \wedge \neg q \wedge \neg r))
\]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 
% 1.3 # 8

Let $T(x,y)$ be the statement ``$x$ has proven $y$.''
$x$ ranges over the set of all mathematicians, and $y$ over 
the set of all theorems.

\begin{description}
\item[a)] There is a mathematician who has never proven a theorem. 
\[ \exists x \forall y (\neg T(x,y)) \]

\item[b)] Every mathematician has proven a theorem.
\[ \forall x \exists y T(x,y) \]

\item[c)] Every theorem has been proven by a mathematician.
\[ \forall y \exists x T(x,y) \]

\item[d)] There is a mathematician who has proven the 
{\it Dominated Convergence Theorem} and the {\it Bounded Convergence Theorem}.
\[ \exists x (T(x, Dominated\_Conv.\_Thm) \wedge T(x, Bounded\_Conv.\_Thm)) \]

\item[e)] At least two mathematicians have proven the {\it Hahn-Banach
    Theorem} 
\[ \exists x_1, x_2 ((x_1 \neq x_2) \wedge T(x_1, Hahn-Banach\_Thm) \wedge
 T(x_2, Hahn-Banach\_Thm)) \]

\end{description}



\problem  Define predicates and formulas.

\begin{problemparts}
\problempart 

Let x be in the domain of creatures. \\
$F(x)$: x is a frog \\
$D(x)$: x is a duck \\
$P(x)$: x is poetic \\

\begin{tabular}{ll}
No frogs are poetical & \( \forall x F(x) \rightarrow \neg P(x)  \) \\
Some ducks are unpoetical & \( \exists x D(x) \wedge \neg P(x) \) \\
Thus, some ducks are not frogs & \( \exists x D(x) \wedge \neg F(x)  \) \\
\end{tabular}

The entire argument is stated by the formula
\[( \forall x F(x) \rightarrow \neg P(x)  ) \wedge
 (\exists x D(x) \wedge \neg P(x)) \Rightarrow
 (\exists x D(x) \wedge \neg F(x)). \]

\problempart 
$H(x)$: x is heavy (not light) \\
$S(x)$: x will silence him \\

\begin{tabular}{ll}
Gold is heavy. & \( H(gold) \) \\
Nothing but gold will silence him.  & 
\( \forall x ((x = gold) \leftrightarrow S(x)) \) \\
Thus, nothing light will silence him. & \( \forall x (\neg H(x) \rightarrow 
\neg S(x)) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ H(gold) \wedge 
(\forall x ((x = gold) \leftrightarrow S(x))) \Rightarrow
(\forall x (\neg H(x) \rightarrow \neg S(x))). \]

\problempart 
$L(x)$: x is  a lion \\
$F(x)$: x is fierce \\
$C(x)$: x drinks coffee \\

\begin{tabular}{ll}
All lions are fierce.  & \( \forall x L(x) \rightarrow F(x) \) \\
Some lions do not drink coffee. & \( \exists x L(x) \wedge \neg C(x) \) \\
Thus, some creatures that drink coffee are not fierce. & 
\( \exists x C(x) \wedge \neg F(x) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ (\forall x L(x) \rightarrow F(x))\wedge
   (\exists x L(x) \wedge \neg C(x)) \Rightarrow
   (\exists x C(x) \wedge \neg F(x)).\]

\problempart 
$P(x)$: x is a pillow \\
$K(x)$: x is a poker \\
$S(x)$: x is soft \\

\begin{tabular}{ll}
Some pillows are soft.  & \( \exists x P(x) \wedge S(x) \) \\
No pokers are soft.   & \( \forall x K(x) \rightarrow \neg S(x) \) \\
Thus, some pokers are not pillows. & \( \exists x K(x) \wedge \neg P(x) \) \\
\end{tabular}

The entire argument is stated by the formula
\[ (\exists x P(x) \wedge S(x))\wedge
   (\forall x K(x) \rightarrow \neg S(x)) \Rightarrow
   (\exists x K(x) \wedge \neg P(x))\]


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Prove the correct arguments from the previous problem and
show the incorrect ones are false.

\begin{problemparts}
\problempart 
We prove that the argument 
\[(\forall x F(x) \rightarrow \neg P(x)  ) \wedge
 (\exists x D(x) \wedge \neg P(x)) \Rightarrow
 (\exists x D(x) \wedge \neg F(x))\]
is wrong by exibiting a model in which the formula 
is false. 
The universe of discourse contains a single element
{\em dog} which is both a duck and a frog and 
it is not poetical, i.e., $D(dog)$, $F(dog)$ and $\neg P(dog)$.
The formula $\forall x F(x) \rightarrow \neg P(x)$ is true
because $\neg P(dog)$.
Also  $\exists x D(x) \wedge \neg P(x)$ is  true because
$D(dog)$ and $\neg P(dog)$.
However the conclusion $\exists x D(x) \wedge \neg F(x)$
is false because $F(dog)$, so the argument is not valid.

\problempart 
The argument 
\[ H(gold) \wedge 
( \forall x ((x = gold) \leftrightarrow S(x)))  \Rightarrow
(\forall x (\neg H(x) \rightarrow \neg S(x)))\]
is correct.
Assume $H(gold)$ and
$\forall x ((x = gold) \leftrightarrow S(x))$
are true.
We prove that $\forall x (\neg H(x) \rightarrow \neg S(x))$ is 
false by contradiction: \\
Assume \(\neg (\forall x (\neg H(x) \rightarrow \neg S(x))) \) \\


\begin{tabular}{ll}
\(\neg (\forall x (\neg H(x) \rightarrow \neg S(x))) \) &
  assumption \\
\(\neg ( \neg \exists x \neg (\neg H(x) \rightarrow \neg S(x))) \) &
  \( \forall x Q(x) \leftrightarrow \neg \exists x \neg Q(x) \) \\
\(\exists x \neg (\neg H(x) \rightarrow \neg S(x)) \) & 
  Double negation law \\
\(\exists x \neg (H(x) \vee \neg S(x)) \) & 
  Defintion of $\rightarrow$ \\
\(\exists x \neg H(x) \wedge S(x) \) & 
  DeMorgan's law \\
\(\exists x \neg H(x) \wedge (x=gold)\) & 
  Logical equivalence \\
\end{tabular}

If we split this up into cases, $x=gold$ and $x \neq gold$, we find 
\begin{itemize}
\item case 1:  $x=gold$ \\
\( \neg H(x) \wedge (x = gold) =
\neg H(gold) \wedge (gold = gold) = 
(\neg True) \wedge True = False \wedge True = 
False
\)
  
\item case 2:  $x \neq gold$ \\
\( \neg H(x) \wedge (x = gold) =
\neg H(x \neq gold) \wedge (x = gold) = ? \wedge False = 
False
\)
\end{itemize}

Since neither case proves true, we know that our original assumption, 
\(\neg (\forall x (\neg H(x) \rightarrow \neg S(x))) \), must be 
untrue, so \(\forall x (\neg H(x) \rightarrow \neg S(x))) \).



\problempart 
We prove that the argument
\[ (\forall x L(x) \rightarrow F(x))\wedge
   (\exists x L(x) \wedge \neg C(x)) \Rightarrow
   (\exists x C(x) \wedge \neg F(x))\]
is wrong by exibiting a model in which the formula 
is false.
The universe of discourse contains a single element
{\em loffy}, which satisfies $L(loffy)$, $F(loffy)$ and $\neg C(loffy)$.
We have $\forall x L(x) \rightarrow F(x)$ and
$\exists x L(x) \wedge \neg C(x)$.
However $\exists x C(x) \wedge \neg F(x)$ is false,
so the argument is not valid.

\problempart 
We prove that the argument
\[ (\exists x P(x) \wedge S(x))\wedge
   (\forall x K(x) \rightarrow \neg S(x)) \Rightarrow
   (\exists x K(x) \wedge \neg P(x))\]
is wrong by exibiting a model in which the formula 
is false.
The universe of discourse contains a single element
{\em poft} such that $P(poft)$, $S(poft)$ and 
$\neg K(poft)$.
The formula $\exists x P(x) \wedge S(x)$ is true.
Also  $\forall x K(x) \rightarrow \neg S(x)$ is  true
because there exists no $x$ such that $K(x)$.
For the same reason the conclusion $\exists x K(x) \wedge \neg P(x)$
is false, proving the the argument is not valid.

\end{problemparts}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem 
\begin{problemparts}
\problempart
{\it {\em Theorem:} if $n^2>1$, then $n>1$.  {\em Proof:}
If $n$ is a real number such that $n>1$, then $n^2>1$.  Suppose that
$n^2>1$, then $n>1$. }

Given the propositions
p: $n>1$ and 
q: $n^2>1$, 
the argument says that $p \rightarrow q$, so if q then p.
This is the fallacy of affirming the conclusion.

\problempart
{ \it {\em Theorem:} The number $\log_2 3$ is irrational. {\em Proof:} A number is irrational if it is not the ratio of two integers.
Therefore, since $\log_2 3$ cannot be written in the form $a/b$ where
$a$ and $b$ are integers, it is irrational. }

Fallacy: Circular reasoning

\problempart
{\it {\em Theorem:} If $n^2 \leq 4$ then, $n \leq 2$.  {\em Proof:} Because
if $n$ is a real number with $n>2$, then $n^2 >4$. }

Given the propositions
p:  $n^2 \leq 4$ and
q: $n \leq 2$,
the argument says $\neg q \rightarrow \neg p$, so $p \rightarrow q$.  This is the
correct argument of disjunctive syllogism.

\problempart
{ \it {\em Theorem} If $n\leq 3$, then $n^2\leq 9$. {\em Proof:} Because if $n$ is a real number with $n>3$, then $n^2>9$.}

Given the propositions 
p: $n\leq 3$ and 
q: $n^2\leq 9$,
the argument says $ \neg p \rightarrow \neg q $.  This is the fallacy of denying
the hypothesis.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{ \it Prove by contradiction: the square root of an irrational number 
is irrational. }

Let $x$ be an irrational number.  Prove that \( \sqrt{x} \) is 
irrational.  

Proof by contradiction:

Assume that \( \sqrt{x} \) is rational.  
Then we know that there exist integers $p$ and $q$ such that
\[ \sqrt{x} = \frac{p}{q}. \]   
Squaring both sides we get \[ x = \frac{p^2}{q^2} \]
Since the square of an integer is an integer, $p^2/q^2$ is a ratio of
integers, and therefore a rational number, making x a rational number.  
This, however, contradicts our original assertion that x is an irrational
number, so the theorem must be true.


\problem

Prove that $\sqrt[3]{5}$ is irrational.

Proof by contradiction:

Assume $\sqrt[3]{5}$ is rational.  It can then be represented as a fraction
in lowest terms, $p/q$, where $p$ and $q$ are integers:
\[ \sqrt[3]{5} = \frac{p}{q} \]
Rearranging the equation we get
\[ 5 = \frac{p^3}{q^3} \]
and
$ 5 q^3 = p^3 $	
Since 5 is prime (has no divisors other than 1 and 5) and p is an integer, 
we know that 
$p = 5 c$ 
where c is also an integer.  However, using similar reasoning, we find that 
\[ 5 q^3 = p^3 = 5^3 c^3\]
and therefore $q^3 = 5^2c^3$,
so q can also be represented as $q=5d$ where d is an integer.  Since both
$p$ and $q$ are multiples of 5, the fraction $p/q$ is not in lowest terms,
contradicting our hypothesis.
Thus  $\sqrt[3]{5}$ is irrational.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3.1 - 19
\problem 
Prove by cases that if $x$ and $y$ are real numbers, then 
\[ \max(x,y) = { x + y \over 2} + { |x - y| \over 2 } \]

Split the proof into two cases: $x \geq  y $ where $x$ is the maximum, and
$x < y $ where $y$ is the maximum.

\begin{itemize}
\item Case 1: $x \geq  y $ , x is the maximum

Since $x \geq y$, $x-y \geq 0$, and $|x-y| = x-y$.  So 
\[ { x + y \over 2} + { |x - y| \over 2 } =
{ x + y \over 2} + { x - y \over 2 } =
{ 2 x \over 2} = x = \max(x,y).
\]

\item Case 2: $x < y $ , y is the maximum

Since $x < y$, $x-y < 0$, and $|x-y| = -(x-y) = y-x$.  So 
\[ { x + y \over 2} + { |x - y| \over 2 } =
{ x + y \over 2} + { y - x \over 2 } =
{ 2 y \over 2} = y = \max(x,y).
\]
\end{itemize}
Therefore 
\( \max(x,y) = { x + y \over 2} + { |x - y| \over 2 } \) is true,
because it is true in both cases.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem

Using the axioms and inference rules for equality given in class,
prove that 
\[
(\forall x y z) ((x = y) \wedge (y=z))\rightarrow (x=z)
\]

Recall that the equality rules are 
\begin{description}
\item [E1] $(\forall x) (x=x)$
\item[E2] For any formula $F$ with free variable x,
\[
(\forall xyz\ldots)(x=y \Rightarrow (F \rightarrow F[x/y])
\]
where $F[x/y]$ denotes substituting $y$ for some or all occurrences of
$x$.
\end{description}


Show that 
\(
(\forall x y z) ((x = y) \wedge (y=z))\rightarrow (x=z)
\).

Let $p \leftrightarrow ((x=y) \wedge (y=z))$.

\begin{enumerate}
\item Let F = (x=z) in E2:
\(        \forall xyz. (x=y) \rightarrow (x=z) \rightarrow (y=z)  \)
   in particular 
\( (b=a) \rightarrow (b=c) \rightarrow (a=c) \)
 
\item \((y=x) \rightarrow (x=y) \) [proved in class, see lecture notes 2]
   in particular
        \( (a=b) \rightarrow (b=a) \)
 
\item by transitivity of $ \rightarrow $, from 1) and 2) we get
        \( (a=b) \rightarrow (b=c) \rightarrow (a=c) \)
 
\item $ (a=b)$  and $ (b=c) $ by hypothesis
 
\item modus ponens: \( (b=c) \rightarrow (a=c) \)

\item modus ponens: \( (a=c) \)

\end{enumerate}
 
We proved for fixed $a$,$b$,$c$, so by universal generalization holds for all.
 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Carrol
