# 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 be the statement it rains'', be I will wear a coat'', and be I'll stay home''. Thus, the negation of the statement is

An implication is false (that is, negated) exactly when the hypothesis is true and the conclusion is false,1 so we get , or equivalently, . 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 , which is negated as , 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 .

Solution: Here we have a statement of the form ; the negation of such a statement is of the form . Thus, we get

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

4. For every , there is a so that whenever .

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

Moving the negation in, we get

and negating the implication gives

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

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

and so the negation would be

But I didn't write it that way, and I can't expect you to see the implicit quantifier on . 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 does not have a unique inverse, either it doesn't have an inverse at all, or it has more than one.2 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 by

As usual, we say is negative if , and is positive if .

1. For every integer and every integer , is positive and is negative.

Solution: This is false. Consider and . Then , which is positive, but , 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 and exist, as consequences of axioms V.8 and V.9, and the fact that follows immediately from axiom V.8. But, we have not shown that is positive, nor have we shown that .

One way to see that is to use axiom VI.1 ( ), but perhaps this is a bit of a cheat, because we didn't define positive'' in that way.

Suppose not. Then either or . But contradicts axiom V.12.
If , then (see the Lemma below). Then applying axiom V.12 (with , , and ), we get . But this says , contradicting the earlier statement. Hence, , that is, is a positive number.

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

Finally, we need the following.

Lemma. For all , .
Proof.    Suppose . Then by axiom V.16, , and applying axiom V.8 to the right and V.10 to the left, we get .
Similarly, if , we have , so .

Whew! More than I bargained for here.

2. There are integers and so that is positive and is negative.

Solution: True. Since we need merely demonstrate existence of such and , let and . Then is positive (we just did this), and is negative (again, see the previous part.)

3. For every integer , there is an integer so that is positive and is negative.

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

Case I: . Let . First, notice that , since and so by axiom V.16, . By transitivity of (axiom V.14), we have . Thus, again by V.16, . Thus (by transitivity again) , so is positive.

We also need show that is negative. Note that (distributive law, commutivity), and so . (using associativity, additive identity). But is negative, from before.

Case II: . Now let . Then , and is positive. To see that , we have . Using the fact that and , together with transitivity and axioms V.14 and V.16, we get .

Case III: . Easiest of all. Let , so , which is positive, and , negative.

4. There is an integer so that, for every integer , is positive and is negative.

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

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

and its negation is

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)
(K2)

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 , there is a unique person and a unique person so that and are parents of , is male, and 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 to mean . What is the common English meaning of ?

Solution: means

is a grandfather of
since is a parent of and is 's father.

4. What is the meaning, in common English, of the assertion ?

Solution:

Everybody has a grandfather.

5. Prove that .

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

4. Prove that that for any natural number , is divisible by . (Hint: use induction on .)

Solution: We want to establish that , where is the statement  is divisible by . Using induction as suggested, we first check :
Is divisible by ? Since , yes it is.

Now we show that , that is, we want to show is divisible by if we know that is.

If is divisible by 3, then there is an so that . Consequently, . So, we have

We have shown that can be expressed as 3 times an integer (), so it is divisible by 3.

#### Footnotes

... false,1
If you don't like that explanation, you can instead use the tautology that is equivalent to , then negate the latter to get .
... one.2
I am pretty sure we went over this in class, but in case you forgot, here's why. is an abbreviation for . Thus, is . That is, either there is no such that holds, or there is more than one.

Scott Sutherland 2002-10-11