Some extra problems for MAT 200

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.
   2. This function has no inverse, and it is not continuous.
   3. In any triangle, the sum of the measure of the angles is less than $\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$.
   5. Every natural number has a unique 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.

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

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

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

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.
   2. State carefully, in common English, the meaning of axiom K2.
   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)$?
   4. What is the meaning, in common English, of the assertion $\forall x \exists y G(x,y)$?
   5. Prove 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$.)