Solutions to MAT 200 extra problems

1. Write the negation of each of the following statements (in English, not symbolically).
   1. If it rains, then either I will wear a coat or I'll stay home.

      Solution: You needn't translate this to symbols to do this problem, but let me do so to clarify the reasoning. First, let $R$ be the statement ``it rains'', $C$ be ``I will wear a coat'', and $H$ be ``I'll stay home''. Thus, the negation of the statement is
      

      $$\sim\negthinspace \left( R  \Rightarrow C\vee H \right).$$
      
      
      An implication is false (that is, negated) exactly when the hypothesis is true and the conclusion is false,¹ so we get $R \wedge \sim\negthinspace (C \vee H)$, or equivalently, $R \wedge \sim\negthinspace C \wedge \sim\negthinspace H$. Translating back to English, we get

      When it rains, I won't wear a coat and I won't stay home.

      or perhaps you might say

      I will go out in the rain without a coat.

      
      

   2. This function has no inverse, and it is not continuous.

      Solution: This is of the form $\sim\negthinspace P \wedge \sim\negthinspace Q$, which is negated as $P \vee Q$, so we get

      This function is invertible or it is continuous.

      I suppose if you wanted to write this as an implication, you could write

      If this function has no inverse, then it is continuous.

      which is equivalent.

      
      

   3. In any triangle, the sum of the measure of the angles is less than $\pi$.

      Solution: Here we have a statement of the form $\forall t P$; the negation of such a statement is of the form $\exists t \sim\negthinspace P$. Thus, we get

      There is a triangle where the sum of the measure of its angles is at least $\pi$.

      
      

   4. For every $\epsilon>0$, there is a $\delta>0$ so that $\vert f(x)-f(y)\vert < \epsilon$ whenever $0 <\vert x-y\vert < \delta$.

      Solution: This statement is nearly already in symbolic form. The negation is
      

      $$\sim\negthinspace \left( \forall \epsilon >0 \exists \delta... ...\delta  \Rightarrow \vert f(x) - f(y)\vert < \epsilon ) \right)$$
      
      
      Moving the negation in, we get
      
      $$\exists \epsilon >0 \forall \delta >0 \sim\negthinspace \... ... \delta  \Rightarrow \vert f(x) - f(y)\vert < \epsilon \right)$$
      
      
      and negating the implication gives
      
      $$\exists \epsilon >0 \forall \delta >0 \left( 0 < \vert x... ...rt < \delta \wedge \vert f(x) - f(y)\vert \ge \epsilon \right)$$
      
      

      You may recall from calculus that the original statement is the definition of ``The function $f$ is continuous at the point $x$'', so the latter is ``$f$ is not continous at $x$''.

      There is an implied quantifier on the $y$ in the statement, that is, it really should say
      

      $$\forall \epsilon >0 \exists \delta >0 \forall y ( 0 < ... ...vert < \delta  \Rightarrow \vert f(x) - f(y)\vert < \epsilon )$$
      
      
      and so the negation would be
      
      $$\exists \epsilon >0 \forall \delta >0 \exists y ( 0 <... ...y\vert < \delta \wedge \vert f(x) - f(y)\vert \ge \epsilon )$$
      
      
      But I didn't write it that way, and I can't expect you to see the implicit quantifier on $y$. Anyway, this course isn't MAT 319 or MAT 320, so let's not worry about it.

      
      

   5. Every natural number has a unique additive inverse.

      Solution: The negation is clearly

      Not every natural number has a unique additive inverse.

      or

      There is a natural number which does not have a unique additive inverse.

      But we can elaborate further. If a number $n$ does not have a unique inverse, either it doesn't have an inverse at all, or it has more than one.² So, we have

      There is a natural number which has no additive inverse, or there is a natural number with more than one additive inverse.

      
      

2. Prove or disprove each of the following statements, using only the axioms in Appendix 1. Define the set of integers ${\mathbb{Z}}$ by
   
   $$n\in{\mathbb{Z}} \mbox{if} ( n\in{\mathbb{N}} \mbox{or} -n\in{\mathbb{N}} \mbox{or} n=0 )$$
   
   
   As usual, we say $n$ is negative if $n<0$, and $n$ is positive if $n>0$.
   1. For every integer $a$ and every integer $b$, $a+b$ is positive and $a-b$ is negative.

      Solution: This is false. Consider $a=1$ and $b=0$. Then $1+0=1$, which is positive, but $1-0=1$, which is not negative.

      
      Since we are insisting that everything be proven with reference to axioms, we probably should work a little harder to fully justify all of our statements. (On an exam, I probably would give nearly full credit for the above counterexample alone. But this isn't an exam, so I should be complete.)

      First we know that $1$ and $0$ exist, as consequences of axioms V.8 and V.9, and the fact that $1+0=1$ follows immediately from axiom V.8. But, we have not shown that $1$ is positive, nor have we shown that $-0=0$.

      One way to see that $1>0$ is to use axiom VI.1 ( $1\in{\mathbb{N}}$), but perhaps this is a bit of a cheat, because we didn't define ``positive'' in that way.

      So let's prove $1>0$ by contradiction.
      Suppose not. Then either $1<0$ or $1=0$. But $1=0$ contradicts axiom V.12.
      If $1<0$, then $-1 > 0$ (see the Lemma below). Then applying axiom V.12 (with $x=1$, $y=0$, and $z=-1$), we get $1\cdot(-1) < 0\cdot(-1)$. But this says $-1<0$, contradicting the earlier statement. Hence, $1>0$, that is, $1$ is a positive number.

      
      To see that $-0=0$, let's suppose that there is number $x$ which is the additive inverse of $0$. Then $0+x=0$ by axiom V.10, and $0+x=x$ by axiom V.8 (and V.5). Thus, $x=0$, so $0$ is its own additive inverse.

      
      Finally, we need the following.

      Lemma. For all $x\in{\mathbb{R}}$, $x>0  \Leftrightarrow -x<0$.
      Proof.    Suppose $0<x$. Then by axiom V.16, $0 + (-x) < x + (-x)$, and applying axiom V.8 to the right and V.10 to the left, we get $-x < 0$.
      Similarly, if $-x < 0$, we have $(-x) + x < 0 + x$, so $0<x$.

      
      Whew! More than I bargained for here.

      
      

   2. There are integers $a$ and $b$ so that $a+b$ is positive and $a-b$ is negative.

      Solution: True. Since we need merely demonstrate existence of such $a$ and $b$, let $a=0$ and $b=1$. Then $0+1=1$ is positive (we just did this), and $0-1=-1$ is negative (again, see the previous part.)

      
      

   3. For every integer $a$, there is an integer $b$ so that $a+b$ is positive and $a-b$ is negative.

      Solution: This is true. We must show that given a specific integer $a$, we can find an integer $b$ that meets our needs. Let's break the problem up into three possibilities: $a>0$, $a<0$, and $a=0$.

      Case I: $a>0$. Let $b=1+a$. First, notice that $a<1+a$, since $0<1$ and so by axiom V.16, $0+a < 1+a$. By transitivity of $<$ (axiom V.14), we have $0<1+a$. Thus, again by V.16, $a+0<a+(1+a)$. Thus (by transitivity again) $0<a+1+a$, so $a+b$ is positive.

      We also need show that $a-b$ is negative. Note that $a-b = a-(1+a) = a-a-1$ (distributive law, commutivity), and so $a-b = 0 -1 = -1$. (using associativity, additive identity). But $-1$ is negative, from before.

      Case II: $a<0$. Now let $b=1-a$. Then $a +b = a+1-a = 1$, and $1$ is positive. To see that $a-b<0$, we have $a-b = a -(1-a) = a+a-1$. Using the fact that $-1<0$ and $a<0$, together with transitivity and axioms V.14 and V.16, we get $a+a-1<0$.

      Case III: $a=0$. Easiest of all. Let $b=1$, so $a+b = 0+1 = 1$, which is positive, and $a-b = 0 -1 = -1$, negative.

      
      

   4. There is an integer $a$ so that, for every integer $b$, $a+b$ is positive and $a-b$ is negative.

      Solution: This is false. This says that we can find this $a$, and write it down somewhere. Now for this $a$ and any possible $b$, $a+b$ must be positive and $a-b$ negative. What about the choice $b=-a$? It is supposed to be positive, but $a+b = a+(-a)=0$, which isn't positive.

      Another way to see this is to write it in symbols. This statement is
      

      $$\exists a \forall b (a+b>0) \wedge (a-b<0)$$
      
      
      and its negation is
      
      $$\forall a \exists b (a+b\le0) \vee (a-b\ge0)$$
      
      

      But this follows from the previous part. Since the negation is true, the statement can't be.

      
      

3. Consider the following symbolic description of ``kinship''. Our domain is a set of people, and we have the predicates
   • m(x) means ``x is male''.
   • f(x) means ``x is female''.
   • P(x,y) means ``x is the parent of y''.
   We have two axioms:

   (K1)

   $\forall x\left( ( m(x) \vee f(x)) \strut\wedge \sim\negthinspace ( m(x) \wedge f(x)) \right)$

   (K2)

   $\forall x \exists!y \exists!z \left( P(y,x) \wedge P(z,x) \wedge m(y) \wedge f(z) \strut\right)$

   1. State carefully, in common English, the meaning of axiom K1.

      Solution: Axiom K1 says

      For every person, either the person is male or female, but that person cannot be both male and female.

      This is better said as

      Every person is either male or female, but not both.

      
      

   2. State carefully, in common English, the meaning of axiom K2.

      Solution:

      For every person $x$, there is a unique person $y$ and a unique person $z$ so that $y$ and $z$ are parents of $x$, $y$ is male, and $z$ is female.

      This is a very stilted way to say

      Everybody has exactly one father and exactly one mother.

      provided that we know that ``father'' means ``male parent'' and ``mother'' means ``female parent''.

      
      

   3. Define the predicate $G(x,y)$ to mean $\exists z ( P(y,z) \wedge P(z,x) \wedge m(y) )$. What is the common English meaning of $G(x,y)$?

      Solution: $G(x,y)$ means

      $y$ is a grandfather of $x$

      since $z$ is a parent of $x$ and $y$ is $z$'s father.

      
      

   4. What is the meaning, in common English, of the assertion $\forall x \exists y G(x,y)$?

      Solution:

      Everybody has a grandfather.

      
      

   5. Prove that $\forall x \exists y G(x,y)$.

      Solution: Let $x$ be an arbitrary person. Then by axiom $K2$, $x$ has a father, that is, there is some $z$ for which $P(z,x)$ and $m(z)$. Now apply axiom $K2$ again to this new $z$ to get $z$'s father, who we shall denote $y$. Since $x$'s father's father is his/her grandfather, we have $G(x,y)$. (Of course, there is also the maternal grandfater). We have shown that for this $x$, $\exists y G(x,y)$. Since $x$ was arbitrary, we apply UG to conclude that $\forall x \exists y G(x,y)$.

      
      

4. Prove that that for any natural number $n$, $4^n - 1$ is divisible by $3$. (Hint: use induction on $n$.)

   Solution: We want to establish that $\forall n\in{\mathbb{N}}\,P(n)$, where $P(n)$ is the statement ``$4^n - 1$ is divisible by $3$. Using induction as suggested, we first check $P(1)$:
   Is $4^1 - 1$ divisible by $3$? Since $4^1 -1 = 3$, yes it is.

   Now we show that $P(n)~\Rightarrow~P(n+1)$, that is, we want to show $4^{n+1} -1$ is divisible by $3$ if we know that $4^n - 1$ is.

   If $4^n - 1$ is divisible by 3, then there is an $m$ so that $4^n-1=3m$. Consequently, $4^n = 3m+1$. So, we have
   

   $$4^{n+1} - 1 = 4\cdot4^n -1 = 4\cdot(3m +1) -1 = 4\cdot 3m +4 -1 = 3\cdot 4m +3 = 3(4m+1).$$
   
   
   We have shown that $4^{n+1} -1$ can be expressed as 3 times an integer ($4m+1$), so it is divisible by 3.

   
   

Footnotes

... false,¹

If you don't like that explanation, you can instead use the tautology that $P \Rightarrow Q$ is equivalent to $\sim\negthinspace P \vee Q$, then negate the latter to get $P \wedge \sim\negthinspace Q$.

... one.²

I am pretty sure we went over this in class, but in case you forgot, here's why. $\exists! x P(x)$ is an abbreviation for $\exists x (P(x) \wedge ( \exists y P(y)  \Rightarrow y=x ))$. Thus, $\sim\negthinspace \exists! x P(x)$ is $\forall x (\sim\negthinspace P(x) \vee ( \exists y P(y) \wedge y \ne x ))$. That is, either there is no such $x$ that $P(x)$ holds, or there is more than one.