Solutions to Problem Set 5

1. We wish to negate the following statement: "If m and n are integers and p is a prime such that p divides mn, then p divides m or p divides n."

First, reinterpret this statement as a "for every / for all" statement: "For all integers m and n and all primes p such that p divides mn, it must be that p divides m or p divides n." (The "it must be" was just something I threw in to make the sentence a little less awkward; there's nothing mathematically important about it.)

Now, the negation of this statement will be a "there exists" statement, stating that there is a counterexample to the above theorem (or "policy" if you like). "There exist integers m and n and a prime p such that p divides mn, but p does not divide m and p does not divide n." Note that the negation of the statement "p divides m or p divides n" contains an "and" instead of an "or": "p does not divide m and p does not divide n."

2. Truth tables. Most students got these correct, but I'll put the answers here. Instead of going to the trouble of figuring out how to make a table in HTML (yes, yes, I know it's possible and probably quite easy), I'll just list the answers.

First truth table. The five statements, in the order in which I have given the truth values, are P, Q, R, (P implies Q) implies R, and P implies (Q implies R).

T T T T T
T T F F F
T F T T T
T F F T T
F T T T T
F T F F T
F F T T T
F F F F T

Second truth table. The three statements are P, Q, and NOT(P OR NOT(Q)) OR Q.

T T T
T F F
F T T
F F F

In particular, note that NOT(P OR NOT(Q)) OR Q simplifies to:

(NOT(P) AND NOT(NOT(Q))) OR Q
= (NOT(P) AND Q) OR Q
= Q

since the statement (NOT(P) AND Q) implies Q anyway.

3. In English, the first statement is "For every integer x, x^2 = x." This sentence states a theorem or a "policy" (albeit a false one); the negation should then state that there is a counterexample to this policy. "There exists an integer x such that x^2 is not equal to x."

The second statement is "There exists an integer x such that |x| = x." This sentence states that there is an integer with a certain property; the negation should state that there are no integers with that property. That is, every integer fails to have the property. "For every integer x, |x| is not equal to x."

4. Most students got these right or made only minor errors. Here are the answers. (The symbol "<=" means less than or equal to; ">=" means greater than or equal to.)

Converse of first statement: "If x + z < y + z, then x < y."
Contrapositive of first statement: "If x + z >= y + z, then x >= y."
Converse of second statement: "If either x > 3 or x < -3, then |x| > 3."
Contrapositive of second statement: "If x <= 3 and x >= -3, then |x| <= 3."

5. We wish to negate the statement "A subset E of the real line is connected if and only if it has the following property: if x is in E and y is in E and x < z < y, then z is in E."

First let's break this up a bit: "If a subset E of the real line is connected, then it has the following property: [property], and if a subset E of the real line has the following property: [property], then it is connected."

So the negation of this statement should state that one (or both) of these "if-then" statements is false.

The negation of the first "if-then" statement is "There exists a subset E of the real line that is connected, but does not have the following property: [property]." That is, "There exists a subset E of the real line that is connected, but such that there exist an x in E and a y in E and a z such that x < z < y, but z is not in E."

The negation of the second "if-then" statement is quite a bit easier: "There exists a subset E of the real line that has the following property: [property], but is not connected."

So the negation of the entire statement (the "if and only if") is the statement "[First negation] or [Second negation]." Your challenge is to fill in all the brackets and write the sentence in English. See if you can find a way to write it down so that it isn't terribly awkward.