\documentclass[12pt]{article}
\pagestyle{empty} 
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[tagged, flatstructure]{accessibility}
\usepackage[pdftex,
            pdfauthor={Jeff Johannes},
            pdftitle={239 Problem Set 1 Solutions},
            pdfsubject={Solutions},
            pdfkeywords={all the problems, and extras!},
            pdfproducer={Latex with hyperref},
            pdfcreator={pdflatex},
            pdflang={English}]{hyperref}
\topmargin=0pt
\textheight=9in
\oddsidemargin=0pt
\textwidth=6.5in



\begin{document}
Mathmatics 239 solutions to Homework for Chapter 1


\bigskip

To the Student.1.  How many different times can be displayed on a digital watch that shows hours, minutes, and seconds and that distinguishes between A.M. and P.M.? 

This is an elementary counting problem.  There are twelve choices for hours (1 - 12), sixty choices for minutes (0 - 59), sixty choices for seconds (0 - 59) and two choices for half of day 
(AM and PM).  Therefore there are $12 \times 60 \times 60 \times 2 = 86,400$ possible different times on this watch.  Another perspective on this question is to find the number of (different) seconds in a day, 
which is also 86,400. 

\bigskip

3.2.This is the book's main definition of divisible (by the way, the one will be using regularly):  
\begin{quote}
Let $a$ and $b$ be integers.  We say that $a$ is divisible by $b$ provided there is an integer $c$ so that $bc = a$.
\end{quote}
Here is an alternative definition: 
 \begin{quote}
We say that $a$ is divisible by $b$ provided $\frac{a}{b}$ is an integer.
\end{quote}
Explain why these two definitions are different. 

   
According to the first definition 0 is divisible by 0 (because $0 \times 7 = 0$ and 7 is an integer), 
but according to the alternative definition zero is not divisible by zero because $\frac{0}{0}$
 is not an integer 
(in fact, it is meaningless).  


Another example is that according to the alternative definition $\frac{3}{2}$ 
 is divisible by $\frac{1}{2}$
 (because $\frac{\frac{3}{2}}{\frac{1}{2}} = 3$, an integer), but according to the first definition 
$\frac{3}{2}$ 
 is not divisible by $\frac{1}{2}$
 because they are not 
integers.  Because these definitions have different examples, they define different concepts and they 
are different definitions.  There may be other differing examples than these. 

\bigskip

3.6  Define what it means for an integer to be a square.  

An integer $x$ is called square provided there exists an integer $r$ such that $r^2 = x$.

\bigskip

[extra] 3.8  This is a little tricky, because we're not quite sure how a polygon has been defined (and defining a polygon is very tricky, if you think about it).  Here is a polygon definition (the first reasonable one I could find) ``A closed plane figure bounded by three or more line segments."  (This definition still has problems, some undefined terms and so on, but it's a workable start.)  If that is our definition, then the perimeter of a polygon is the sum of the lengths of its (bounding) line segments.  Your definition should be something like that, at least {\em not} be the distance ``around", since that is not defined.  Beyond that, this is not a particularly challenging question.  Consider 3.10 and 3.6 nearby for others.  

\bigskip

[extra] 3.10  A point on a line segment is the midpoint if it is equidistant to both endpoints. {\em or}  The point $C$ is the midpoint of line segment $AB$ if $C$ is on segment $AB$ and the distance from $A$ to $C$ is equal to the distance from $B$ to $C$.  Most importantly:  make sure that $C$ is {\em on} the segment.  Instead of emphasising {\em on}, it does suffice to say that $C$ is {\em between} $A$ and $B$.  Some effort should also be make to keep the writing clear and uncluttered.  

\pagebreak
 
4.3. Find two conditions A and B such that ``(a) If A then B." is true but ``(b) if B then A." is false.  
\begin{quote}
Consider A:  It is $300^o$ F and B: Water is boiling.
\end{quote}
It is true that ``If it is $300^o$ F then water is boiling."  It is false that ``If water is boiling then it is $300^o$ F" as it could be many other temperatures.  Of course, there are many possible examples 
here.  

\bigskip

4.10. Is the claim ``If you pick a guinea pig up by its tail, then its eyes will pop out." true? 

Based on the photo in the hints, it looks as if you cannot pick up a guinea pig by its tail.  Therefore, the hypothesis is vacuous (always false) and so the statement is true.  

\bigskip

5.2. Prove that the sum of an odd integer and an even integer is odd. 

This can be restated as 

\begin{quote}
If $a$ is an odd integer and $b$ is an even integer then $a + b$ is odd.
\end{quote}

Suppose that $a$ is an odd integer.  By definition of odd, $a = 2x + 1$ for some integer $x$. Suppose that $b$ is an even integer.  By definition of even, $b$ is divisible by 2.  By definition 
of divisible, $b = 2c$ for some integer $c$. Consider $a + b = (2x + 1) + (2c) = 2x + 2c + 1 = 2(x + c) + 1$.  (This uses substitution, 
associativity, commutativity, and distribution, all items assumed from Appendix D.)  We also know that the integers are closed under addition, so if $x$ and $c$ are integers, then $x + c$ is also an integer.  Then, $x 
+ c$ is the desired integer, $y$, such that $a + b = 2y + 1$.  Therefore, by definition of odd, $a + b$ is odd, as desired. 

\bigskip

5.12. Suppose $a, b, c$, and $d$ are integers.  Prove that if $a \mid b$ and $c \mid d$, then $(ac) \mid(bd)$.  

Suppose that $a \mid b$.  By definition of $\mid$, there is an integer $m$ such that $b = am$.
 
Suppose that  $c\mid d$.  By definition of $\mid$, there is an integer $n$ such that $d = cn$.
  
Therefore, $bd = (am)(cn) = ac(mn)$ by substition, commutativity, and associativity.  Because the integers are closed under multiplication, $mn$ is an integer and therefore satisfies the 
definition of divisibility so that $ac \mid bd$, as desired.

\bigskip
  
5.15.  Let $x$ be an integer.  Prove that $0 \mid x$ if and only if x = 0.
 
In two directions - prove 
\begin{quote}
if $0 \mid x$ then $x = 0$, and if $x = 0$ then $0 \mid x$.
\end{quote}

If $0 \mid x$ then there is an integer $c$ such that $0(c) = x$.  But then by multiplication, $x = 0$, as desired. 

Suppose $x = 0$.  $0 \mid 0$ because 0 (83456) = 0.  We may substitute $x$ for 0 to get $0 \mid x$.  

\bigskip

[extra] 5.21  Prove that the difference between distinct, nonconsecutive perfect squares is composite.  This can be restated as 

\begin{quote}
If $x$ and $y$ are distinct and nonconsecutive integers, then $x^2-y^2$ is composite.
\end{quote}

Suppose that $x$ and $y$ are distinct and nonconsecutive integers .  Since they are distinct, one must be larger.  Because the variables are meaningless before hand, suppose $x>y$.  Because they are nonconsecutive, in fact, we may further suppose $x > y+1$.  To show $x^2-y^2$ is composite, by definition, we must show that there is an integer $b$ such that $1 < b < x^2-y^2$ and $b|x^2-y^2$.  Notice that $x^2-y^2 = (x-y)(x+y)$, so $(x-y)|(x^2-y^2)$.  We need only show that one of the factors is the appropriate size.  Since I think it will be easier, let's focus on $x-y$.  

We supposed that $x>y+1$.  By subtracting $y$ we get $x-y > 1$, and we're half done.  We also supposed that $x > y$.  By subtracting 1 we also get $x-1 > y-1$.  Multiplying these two produces $x^2-x > y^2-y$, and subtracting $y^2$ and adding $x$ to both sides yields $x^2 - y^2 > x-y$, as desired.  We've now shown that $(x-y)|(x^2-y^2)$ and $1 < x-y < x^2-y^2$, therefore by definition $x^2-y^2$ is composite, as claimed.  

\bigskip





5.23. Suppose you are asked to prove a statement of the form ÒIf A or B, then C.Ó  Explain why you need to prove (a) ÒIf A, then C.Ó and also prove (b) ÒIf B, then C.Ó  Why is it 
not enough to prove only one of (a) or (b)?
 
Consider the statement ÒIf I am alive or dead, then I am alive.Ó  Well, it is true that ÒIf I am alive, then I am aliveÓ, trivially.  However, the original statement is not true.  This shows that it is 
not enough to prove only one, but not quite why.  To see why, examine the original statement ÒIf A or B, then CÓ.  This says that if one of A or B is true, C must also be true as well.  In either the 
case that A is true or that B is true, C must follow to be true.  If we only check the A is true case, we have not attended to the B is true case.  This case is also necessary for proving the statement ÒIf 
A or B, then C.Ó 

\bigskip

6.2. Disprove:  If $a$ and $b$ are nonnegative integers with $a\mid b$, then $a \leq b$.

2 and 0 are nonnegative integers, $2 \mid 0$ (because $0 = 2 \times 0$), but it is false that $2 \leq 0$. 

\bigskip

6.4 Exponentiation (or involution) is not associative.  Those parenthesis matter.  $2^{(3^2)} = 2^9 = 512$, while $(2^3)^2 = 8^2=64$.  These are all positive integers, but the results are not equal.  

\bigskip

[extra] 6.7  This isn't too bad for your calculator to handle.  $2^{2^5}+1 = 4294967297 = 641(6700417)$.  Clearly $1< 641 < 4294967297$, and so $2^{2^n}+1$ is not prime for $n=5$.  [Of historical note:  Pierre de Fermat thought all numbers $2^{2^n}+1$ were prime, mostly because the numbers grew too big to compute.]  

\bigskip

 
[extra] 6.9  Consider $n^2 + n + 41$.  Calculate the value of this polynomial for $n = 1, 2, 3, \dots, 10$.  
\begin{quote}
43, 47, 53, 61, 71, 83, 97, 113, 131, 151
\end{quote}
Notice that all the numbers you computed are prime (yep they are).  
\begin{quote}
Disprove:  If $n$ is a positive integer, then $n^2 + n + 41$ is prime.
\end{quote}

Doing this by blind computation is inconvenient (turns out they all are for quite a while).  But some thought reminds us that clearly if $n = 41$ then $41^2 + 41 + 41$ can't be prime, 41 is a factor.  It takes a little more insight to see that $n = 40$ doesn't work either, $40^2 + 40 + 41 = 40(40) + 40 + 41 = 40(40 + 1) + 41 = 40(41) + 41$ also has 41 as a factor.  It's a nifty fact that up to 40, you always do get primes.  This is one of the nicest examples of "just because it works for lots of examples doesn't mean it's always true".  

\bigskip

6.11 Disprove:  An integer $x$ is positive if and only if $x + 1$ is positive.  

Consider $x = 0$.  This statement says Ò0 is positive if $\dots$ 1 is positive.Ó However, 1 is positive, but 0 is not.  

\bigskip

[extra] 6.12  A triangle with legs 2 and 2 has area 2.  So does a triangle with legs 1 and 4.  The hypotenuse of the first triangle has length $2\sqrt2$, and the hypotenuse of the second triangle is $\sqrt{17}$.  Since $2\sqrt2 < 4 < \sqrt{17}$, we have that $2\sqrt2 \ne \sqrt{17}$.  This direction of counterexample seems easier to me than the converse.  
	
	To attempt the converse we seek two noncongruent triangles with congruent hypotenuses.  Using similar numbers to the first example, A triangle with legs 1 and 2 has hypotenuse $\sqrt{5}$, so does one with legs $\sqrt2$ and $\sqrt3$.  The first one has area 1.  The second one has area $\frac{\sqrt6}{2}$, which may be a somewhat mysterious number, but is surely not equal to one.  

\bigskip

7.8.Prove:  $(x \vee y) \rightarrow z$ is logically equivalent to $(x \rightarrow z) \wedge (y \rightarrow z)$.

\begin{center}
\begin{tabular} {|c|c| c || c | c |}
\hline
$x$ & $y$ & $z$ & $x \vee y$ & $(x \vee y) \rightarrow z $\\ 
\hline
T&T&T&T&T\\ 
T&T&F&T&F\\ 
T&F&T&T&T\\
T&F&F&T&F\\ 
F&T&T&T&T\\
F&T&F&T&F\\ 
F&F&T&F&T\\ 
F&F&F&F&T\\
\hline
\end{tabular}
\end{center}

 
\begin{center}
\begin{tabular} {| c | c | c || c | c | c |}
\hline
$x$& $y$ & $z$ & $x \rightarrow z$ & $y \rightarrow z$ & $(x \rightarrow z) \wedge (y \rightarrow z)$\\ \hline 
T&T&T&T&T&T\\ 
T&T&F&F&F&F\\ 
T&F&T&T&T&T\\ 
T&F&F&F&T&F\\ 
F&T&T&T&T&T\\ 
F&T&F&T&F&F\\ 
F&F&T&T&T&T\\ 
F&F&F&T&T&T\\ \hline
\end{tabular}
\end{center}

Notice the two statements are true and false under identical conditions. 

\bigskip

7.11  Explain how to use a truth table to prove that a Boolean expression is a tautology. 

Show that under all conditions the expression evaluates to TRUE. 


Prove the following are tautologies: 

(a) $(x \vee y) \vee (x \vee \neg y)$ 
\begin{center}
\begin{tabular} {| c | c || c | c | c | c |}
\hline
$x$ & $y$ & $x  \vee y$ &  $\neg y$ & $x \vee \neg y$ & $(x \vee y) \vee (x \vee \neg y)$ \\ \hline
T & T& T& F&T&T\\ 
T&F&T&T&T&T\\ 
F&T&T&F&F&T\\ 
F&F&F&T&T&T\\ \hline
\end{tabular}
\end{center}

(b) $(x \wedge (x \rightarrow y)) \rightarrow y$ 
\begin{center}
\begin{tabular} {| c | c || c |  c | c |}
\hline
$x$ & $y$ & $x \rightarrow y$ & $x \wedge (x \rightarrow y)$ & $(x \wedge (x \rightarrow y)) \rightarrow y$\\ \hline 
T&T&T&T&T\\ 
T&F&F&F&T\\ 
F&T&T&F&T\\ 
F&F&T&F&T\\ \hline
\end{tabular}
\end{center}
 
(c) $(\neg (\neg x)) \leftrightarrow x$ 
\begin{center}
\begin{tabular} {| c ||  c |  c | c |}
\hline
$x$&$\neg x$&$\neg (\neg x)$&$(\neg (\neg x)) \leftrightarrow x$ \\ \hline
T&F&T&T\\ 
F&T&F&T\\ \hline
\end{tabular}
\end{center}
 
(d) $x \rightarrow x $
\begin{center}
\begin{tabular} {| c || c | }
\hline
$x$&$x \rightarrow x$ \\ \hline 
T&T\\ 
F&T\\ \hline
\end{tabular}
\end{center}
 
(e) $((x \rightarrow y) \wedge (y \rightarrow z)) \rightarrow (x \rightarrow z)$
\begin{center}
\begin{tabular} {| c | c | c ||  c | c |c|c|c|}
\hline
$x$&$y$&$z$&$x \rightarrow y$&$y \rightarrow z$&$(x \rightarrow y) \wedge (y \rightarrow z)$&$x \rightarrow z$&$((x \rightarrow y) \wedge (y \rightarrow z)) \rightarrow (x \rightarrow z)$\\ \hline 
T&T&T&T&T&T&T&T\\ 
T&T&F&T&F&F&F&T\\ 
T&F&T&F&T&F&T&T\\ 
T&F&F&F&T&F&F&T\\ 
F&T&T&T&T&T&T&T\\ 
F&T&F&T&F&F&T&T\\ 
F&F&T&T&T&T&T&T\\ 
F&F&F&T&T&T&T&T\\ \hline
\end{tabular}
\end{center}
 
(f) $FALSE \rightarrow x$
\begin{center}
\begin{tabular} {| c || c | }
\hline
$x$ & $FALSE \rightarrow x$\\  \hline
T&T\\ 
F&T\\ \hline
\end{tabular}
\end{center}

(g) $(x \rightarrow $FALSE$) \rightarrow \neg x$
\begin{center}
\begin{tabular} {| c || c | c|c|}
\hline
$x$ & $x \rightarrow $FALSE&$\neg x$&$(x \rightarrow $FALSE$) \rightarrow \neg x$\\  \hline
T&F&F&T\\ 
F&T&T&T\\ \hline
\end{tabular}
\end{center}

(h) $((x \rightarrow y) \wedge (x \rightarrow \neg y)) \rightarrow \neg x$.
\begin{center}
\begin{tabular} {| c | c || c |  c | c |c | c| c|}
\hline
$x$ & $y$ &$\neg x$ &$\neg y$& $x \rightarrow y$ & $x \rightarrow \neg y$& $(x \rightarrow y) \wedge (x \rightarrow \neg y)$ & $((x \rightarrow y) \wedge (x \rightarrow \neg y)) \rightarrow \neg x$\\ \hline 
T&T&F&F&T&F&F&T\\ 
T&F&F&T&F&T&F&T\\ 
F&T&T&F&T&T&F&T\\ 
F&F&T&T&T&T&F&T\\ \hline
\end{tabular}
\end{center}

\pagebreak

Here are some more extras:  

\bigskip

1.  Define a perfect number - be as precise as you can - probably use summation notation.

A positive integer is called {\em perfect} if the sum of all its positive factors which are not itself are equal to itself.  
\begin{quote}
A number $p$ is called {\em perfect} if $\sum_{1 \leq d < p, d \mid p} d = p$.
\end{quote}

\bigskip

2.  Find a counterexample to the following:  If $f$ is continuous and differentiable on $(a, b)$ and $f(a) = f(b)$, then there exists a real number $c$ in $(a, b)$ such that $f'(c) = 0$.

This is almost Rolle's theorem.  Except Rolle's theorem requires continuous on $[a, b]$.  So, to make a counterexample, we'll need something discountinous on $[a, b]$, but continuous on $(a, b)$.  Let's take $a = 0, b= 1$, and make $f(x) =  \begin{cases} 
x & \text{if } 0 \leq x < 1\\
0 & \text{if } x = 1
\end{cases}$.


\bigskip



3.  Prove and extend or disprove and salvage:  The product of any three consecutive integers is a multiple of 3.

One of the three consecutive numbers will be a multiple of three - because every third integer is a multiple of three.  The product of any multiple of three with other numbers remains a multiple of three.  This can at least be extended to the product of any three consecutive integers is a multiple of 6, because every other number is also a multiple of two.  We can extend this further in this direction to the fact that the product of any $n$ consecutive integers is a multiple of $n!$ (if we have four numbers, one of them is divisible by 4).  We need to be careful, though, once the number includes non-primes.  There's some subtlety at that point in the argument.  

\bigskip

4.  Prove (using the givens in the appendix):  A negative integer multiplied by a negative integer yields a positive integer.

Ok, this is a little silly, as this fact is stated in the appendix.  Pointing this out will earn full credit.  If it weren't in the appendix, what would constitute a proof?  

It suffices to prove $(-1) \times (-1) = 1$ (because $(-a) \times (-b) = (-1) \times (-1) \times a \times b)$.

There are two needed related thing to prove.  First $0a = a0 = 0$.  Here's a proof of that:  $a0 + a0 = a(0 + 0) = a0 = 0 + a0$.  From there subtract $a0$ from both sides to get $a0 = 0$.  The same is true for $0a$. Second, we need that $-(-1) = 1$.  $1 + (-1) = 0$ because $(-1)$ is defined as the inverse of 1.  But, this may be reinterpreted that 1 is the inverse of $(-1)$.  In symbols this is $1 = -(-1)$, as desired.    

Finally we show $(-1)(-1) = 1$.  To do this we will show that $(-1)(-1) + (-1) = 0$, and thus by uniqueness of additive inverses, $(-1)(-1)$ is the inverse for $-1$ and therefore $(-1)(-1) = 1$.  $(-1)(-1) + (-1) = (-1)(-1 + 1) = (-1)0 = 0$.  We have now proven $(-1)(-1) = 1$ and hence a negative integer multiplied by a negative integer yields a positive integer.  

\end{document}