### This assignment has been graded.

### Questions

1. **Choose one** of the following statements, and show that it is false by exhibiting a counterexample. Justify as completely as possible that what you have is indeed a counterexample. (Precise definitions of "prime" and "divides" can be found in Solow on page 26, but you may assume that the reader understands the meaning of those terms.)

- If $m$ is a positive integer, then $2m^2+11$ is prime.
- If $a$ divides $bc$, then $a$ divides $b$ or $a$ divides $c$.
- If $x+y$ is even, then $x$ and $y$ are even.
- If $x$ is prime, then $x+1$ is not prime.
- If $x$ is a real number, then $\sqrt{x^2}=x$.
- If $x < 5$, then $x^2 < 2^x$.

2. Each of the following statements is equivalent either to "if X, then Y" or to "if Y, then X". **Choose one** of them, and explain as completely as you can which of those it's equivalent to, and why. (Of course, X and Y represent abstract statements.)

- X only if Y.
- X is necessary for Y.
- X is sufficient for Y.
- Whenever X is true, Y must be true.
- X must be true whenever Y is true.
- Given X, we must have Y.

3. Each of the following sentences expresses an implication. However, none of them is written as a simple "if-then" statement. Nevertheless, your job is to **choose one** of the statements and sort out what is the hypothesis and what is the conclusion. (In other words, the directions are the same as to Exercise 1.4.3 in *Chapter Zero*, but the wording of the statements is not as straightforward.)

- $n^2$ is even only if $n$ is even.
- $n^2$ is even if $n$ is even.
- $\det A \not= 0$ is sufficient for $A$ to be invertible.
- $\det A \not= 0$ is necessary for $A$ to be invertible.
- The number $5m$ is even whenever $m$ is even.
- For a polynomial $p$ to have a real root, it is sufficient that the degree of $p$ be odd.

4. Give an example of a *non-mathematical* English sentence that is an implication that is vacuously true.

5. Consider the following two statements.

- (a) "For all x, there exists a y such that P(x,y)."
- (b) "There exists a y such that for all x, P(x,y)."

The difference between (a) and (b) is *the order in which the variables are quantified*. Your job is to show that this matters! Do this by giving an example of a predicate P(x,y) that makes one of (a) and (b) true while making the other false. (For this question, take the universe of discourse to be the real numbers.)

6. Consider the following two statements.

- (a) "For all x, there exists a y such that P(x,y)."
- (b) "There exists an x such that for all y, P(x,y)."

The difference between (a) and (b) is that *the quantifiers have been inverted*. Your job is to show that this matters! Do this by giving an example of a predicate P(x,y) that makes one of (a) and (b) true while making the other false. (For this question, take the universe of discourse to be the real numbers.)

### Team A1

1. A counter example for the statement "If x is prime, then x+1 is not prime" is if x = 2. This shows that the hypothesis is true because 2 is a prime number however, 1 + 2 = 3 is a prime number, which proves this this statement is false.

Fabulous!

2. The statement we chose is "X only if Y." This statement is equivalent to "If Y, then X." This statement is saying that X only happens if Y happens, so in order for x to occur, y must occur.

You know, "only if" is the one that shows up most commonly in mathematical writing… but it's easy to get confused about it. It's saying "X is true only when Y is true" which is to say, "if X is true, then Y had better be true". So it's actually equivalent to "If X, then Y".

Here's an example: "You get married only if you're in love." Is this saying, "If you're in love, then you get married" or "If you get married, then you're in love"? Of course, it's the latter; "X only if Y" is the same as "if X, then Y".

3. Implication: For a polynomial $p$ to have a real root, it is sufficient that the degree of $p$ be odd.

Hypothesis: The degree of polynomial $p$ is odd

Conclusion: Polynomial $p$ has a real root

Great!

4. If New York is in Nebraska, then grapes are fruit. It is a vacuously true statement because the hypothesis is false.

Very good, and you've illustrated that a vacuously true statement

canhave a trueconclusion.

5. (a) For all integers, $x$, there exists an integer $y$ such that $x-y$ is even.

(b) There exists an integer, $y$, such that for all integers, $x$, $x-y$ is even.

The order that a set of free variables are quantified is integral to the meaning and validity of an implication. In the examples above, $a$ is true: If an integer, $x$, is odd one can subtract an odd number and obtain an even number. If an integer, $x$, is even, one can subtract an even number and obtain an even number. In other words, there always a way to make the difference of two integers, $x$ and $y$, even given the quantification order of the first example, $a$. The latter implication, $b$, is false because $y$ would have to be an even and an odd number in order to make the conclusion true. Therefore, by changing the order of quantification, the meaning of the implication is altered.

Very nice. (Just two minor quibbles: What is the "validity" of an implication? And the problem said to take the universe of discourse to be the real numbers.)

6. For all x, there exists a y such that x>y.

There exists an x such that for all y x>y.

In this example, the quantifiers are inverted, and the first statement is true, while the second statement is false. The first statement is true because there will always be a y value for every x you choose. The second statement is false because it's impossible for there to be one x value that's greater than all y values.

Yes, "there will always be a y value for every x you choose" — but why is that? Your explanation of why the first statement is true didn't make any reference to the predicate at all. By contrast, your explanation of why the second statement is true is very good; it says what the problem would be with quantifying that specific predicate in that way.

*Comments:*

### Team A2

1. Statement: If $x<5$, then $x^2<2^x$

Counterexample: $x = 3$ is a counter example. It is true $3< 5$, however, $3^2 = 9$which is NOT less than $2^3 = 8$.

A counterexample is an example which disproves a proposition. This is exactly what x=3 does in the case above since it makes the hypothesis of the statement true and the conclusion false.

This is great; I want to highlight that your sentence "$3^2 = 9$which is NOT less than…" shows very good grammatical integration of the equals sign. I could go into this at length from an educational psychology of mathematics standpoint, but that'd be a digression…

2. The statement: "X is necessary for Y" is equivalent to If Y, then X. "X is necessary for Y" tells us that in order for Y to exist, X must exist. "If Y, then X", tells us if Y is in existence, then X definitely has to exist also. Because both explanations are similar, the two statements are the same.

In order for X to

exist?!Remember that X and Y are predicates, so I think you mean "be true", although the wording of "is necessary for" is kind of awkward, I suppose, in that if you wrote "$x \ge 0$ is necessary for $x = |x|$" then… well, actually, I guess that sounds reasonable.

3. Implication: "The number $5m$ is even whenever m is even."

Hypothesis: "Whenever $m$ is even"

Conclusion: "The number $5m$ is even"

This is good, except that "whenever" is a logical connective, and doesn't belong in the hypothesis. (Remember that the hypothesis and conclusion are each predicates, and a predicate is a type of sentence — does "Whenever $m$ is even" sound like a sentence?)

4. "If dolphins are fish, then Quinnipiac is in Connecticut." Since the hypothesis is false, it makes the statement vacuously true.

Yes! And, again, I like that this is an example where the conclusion is true.

5. If $P(x,y) = x-1 > y + 1$ is the predicate, than statement (a) "For all x, there exists a y such that $P(x,y)$." is true if the universal discourse is real numbers, because for every value of x minus 1 there will still be a value of y plus 1 such that x minus 1 is greater than y plus 1. This predicate will make statement (b) "There exists a y such that for all x, $P(x,y)$." false when the universal discourse is all real numbers, because there does not exists a real number y such that when 1 is added to y it will be less than all values of x when x is subtracted by 1.

I think this explanation is good, although the wording is confusing. (For one thing, I think you mean "universe of discourse" and not "universal discourse", right?) And you mean "there will still be a value of y" rather than "a value of y plus 1" and, at the end, you mean "less than x-1 for all values of x", and not "less than all values of x"?

6. If $P(x,y) = x + y$ is an odd number, is the predicate, then statement (a) "For all x, there exists a y such that $P(x,y)$." is true when the universal discourse is real numbers since an odd number plus an even number is an odd number. As a result when any real number, odd or even, is chosen to represent x for this particular predicate, there can be an even or odd number, respectively, chosen for y that will make statement (a) true. This same predicate will make statement (b) "There exists an x such that for all y, $P(x,y)$." false because there does not exist one value of x such that when any value of y within the universal discourse is added to it will always result in an odd number.

One obvious problem here is that "even" and "odd" are defined only for integers, so the sentence "x+y is an odd number" is not a predicate (since it does not make sense) over the real numbers. Beyond that, the explanation here seems very good, though!

*Comments:*

### Team A3

1. Statement Given: if x+y is even, x and y are even.

Counterexample: x=3, y=5. 3+5=8.

In the counterexample, x+y equals an even number, proving the hypothesis true. However, for this example where x=3 and y=5, both x and y are both odd.

This looks good. If you want a less boring sentence than "x=3, y=5." then you can write "Let x=3 and y=5." Note that you're using the fact that a number that is odd cannot be even, which is actually fun thing to try to prove from the definitions.

2. Whenever x is true, y must be true is equivalent to if x then y because in both statements, the hypothesis involves x and the conclusion involves y. The two statements are the same because they both in each case, x is a certain value that is true making the hypothesis true and y is true for that value of x.

I think you guys picked out the easiest one, and explained it well. Except that last sentence seems a bit confused; remember that X and Y represent predicates, so saying "y is true for that value of x" does not make sense.

3. Implication: $n^2$ is even if n is even

Hypothesis: n is even

Conclusion: $n^2$ is even

Yes!

4. "If the moon is made of Swiss cheese then the King of England is alive." This implication is vacuously true because the hypothesis is false.

Ha — yes!

5. $P(x,y) = x = 2y$. If we were to quantify this predicate using statement (a), it is true because if we choose any $x$, say $x=3$, there is a $y$ that makes this true, specifically $y=1.5$. However, quantifying using statement (b) would be false. This statement says we can take any value of x, and a single value of $y$ to make $P(x,y)$ true, which we cannot. That is to say, if $x$ was $4$ or $6$, there is no single value of $y$ that would work for both of them.

For (a), you definitely have me convinced that there is such a y when x=3, but you didn't explain why in general this should be true for all x. I see there is no single value of y that is going to make the predicate true both for x=4 and x=6, though!

6. $P(x,y) = x-y$ Is an integer. For statement (a) this is true; If we pick any value of $x$, we can pick a value of $y$ that makes the difference an integer. However, there is not a single value such that subtracting any number from it will create an integer, so (b) is false.

Great!

*Comments:*

### Team A4

1. If we let a=10, b=6, and c=5, the hypothesis of the statement, “a divides bc” is true. 6 x 5 = 30, which is divisible by ten, giving you three. However, five and six are not divisible by ten. It will not give an integer as an answer, which makes the conclusion false. Since, the hypothesis is true and the conclusion is false, this is a counterexample.

What do you mean by "It will not give an integer as an answer"? What won't give you an integer? As an answer to what? In any case, I agree that 5 and 6 are not divisible by 10. (Actually proving this is mildly annoying, and boils down to expanding on the "It" that you refer to.)

2. The statement, “x must be true whenever y is true,” is equivalent to “if Y, then X”. X depends on Y. If Y is true, then X must be true. X can only be true, if Y is too.

This was good until the last sentence… To see the problem, suppose Y is false but X is true. Then "if Y, then X" is (vacuously) true. But your statement "X can only be true, if Y is too" is false, as here Y is false but X is true anyway. I admit, it was pretty hard to figure out how to explain that; this is not an easy problem.

3. Implication: detA≠0 is sufficient for A to be invertible.

Hypothesis: A is invertible

Conclusion: det A does not equal 0

I think you've got it the wrong way around; see my comments on Team A6's solution to Question 2.

4. "If Long Island is a U.S. state, then pigs can fly." The hypothesis "Long Island is a U.S. state" is false, so the implication is vacuously true because there is no way to prove the conclusion "pigs can fly" is false when Long Island is a state.

Good example. Nice explanation!

5. If we say the predicate is "x^{2}=y," then statement a is correct because any real number squared will produce another real number. However, statement b is false because any number y cannot equal the square of every real number (which is meant by "for all x"). All numbers do not produce the same quantity when squared.

Hey, this is a short, precise, clear explanation. Excellent!

6. If we keep the same predicate from question 5 (that "x^{2}=y"), then statement a is true for the same reason given in question 5 (because it is the same statement). However, this statement b is also false because y cannot be any number to make the statement true. For example, if y is a negative number, such as -1, then x cannot be in the universe of discourse that is all real numbers because x would be an imaginary number (specifically i).

Oh, snap; way to refer to the same statement in Question 5. I can't argue with that, right? You make a fabulous point about how the universe of discourse matters, and you're actually pointing out something stronger, namely that for y=-1, P(x,y) is false for all x. So not only is there no x that works for all y (i.e., the statement (b) is false) but in fact there is no x that works

for even that one valueof y. Super!

*Comments:*

### Team A5

1. If m is a positive integer, then 2m^{2}+11 is prime.

Counterexample:25=m is a positive integer however, when you do the problem it comes out to 1261 which is not a prime number.

What is "the problem"? What problem? Do you have a problem here? I mean, really, what is your problem?

Maybe you mean that 2(25)^2 + 11 = 1261, which is not prime? How do you expect me to see that it's not prime? Why not show me it's not prime, maybe by giving me a factorization? You don't expect me to factor that huge number all by myself, do you? Okay, fine. 1261 = (13)(97). There. (Okay, I admit, I used a computer to do that.)

2. Given X, we must have Y. This is equivalent to If X, then Y. The reason they are equivalent is, the statement given x, we must have y means that we are give x which means we must have x and the second means obviously that we must have y as well. Likewise, if x, then y. Means exactly what it looks like, if we have x then we must have y as well. You could mix the two statements and still have the same meaning, "If we are given x, then we must have y."

Okay, I buy this, and I love your observation about mixing the two!

3.Implication: detA≠0 is necessary for A to be invertible.

Hypothesis: detA≠0.

Conclusion: A is invertible.

Statement: If detA≠0 then A is invertible.

I think this is the wrong way around; saying "detA≠0 is necessary" is saying that "detA≠0"

needs to be truein order for "A is invertible" to be true. That is, whenever "A is invertible" is true, "detA≠0" needs to be true too. Put another way, if "A is invertible" is true, then "detA≠0" is true.

4. To make an implication vacuously true the hypothesis must be false. For example, "If bananas are vegetables, then Robert Downey Jr. is Iron Man."

Wait — but

isRobert Downey Jr. Iron Man… or not?? Since the hypothesis is false, this implication won't help any 18-month-old kids decide.

5. If we say that the statement P(x,y) is x=y, Then for all x there is a y such that x=y. So whichever number you put as x there is always a y to match. The second statement, "There exists a y such that for all x, x=y" is not correct. If you choose y to be 3 and x to be 9, 11, 8, 1234662, it does not work. Therefore the order in which the variables are quantified matters significantly pertaining to the truth value of the statement.

Yeah, very nice; the very essence of the problem is that, as you say in your 4th sentence, with the other quantification, you would have to choose the y first. However, you explain why this would be a problem if you the choice were y=3, but not what in general will be the problem

no matter what value you choosefor y.One thing I like about this example: Because the predicate "x=y" is symmetric in x and y, you can tell that it's

onlythe order of quantification that is making the difference, and not somehow that x and y play different roles in the predicate.

6. The reason that having the quantifiers inverted matters is because for example if we have a predicate, P(x,y) = x/y is an integer:

(a) For all x, there exists a y such that P(x,y) = x/y gives an unlimited amount of numbers and a y that goes along with them to get an integer as quotient.

(b) There exists an x such that for all y, P(x,y) = x/y. If we gave actual values to x and y if x=1 we automatically do not have an integer.

This shows that it does matter how the quantifiers are placed in the sentence.

I like this predicate! I agree that (a) is true, but your explanation that this is because it "gives an unlimited amount of numbers and a y that goes along with them to get an integer as quotient" is very confusing. You just need to suppose that you have a real number x and show that you can pick a y that makes P(x,y) true. So maybe: "For any real number x, taking y=x makes x/y=1, which is an integer, making P(x,y) true."

I also cannot make sense of this: "If we gave actual values to x and y if x=1 we automatically do not have an integer." What? Are you saying that if x=1, we cannot have x/y be an integer? Why not? What if y=0.25? Then x/y = 4. (My guess is that taking the time to phrase it more carefully would have made the flaw in your analysis of (b) clear for you to see.)

In any case, for (b) consider this: There does exist an integer x, namely x=0, such that x/y is an integer, namely 0, for

almostall y. So (b) is very close to being true. The real reason it's false is that no matter what value x has, x/y is undefined for y=0, and so P(x,y) will never be true for all y, regardless of what value is given to x.This was a tricky predicate that you took on, but I like it, because I think it illustrates a lot.

*Comments:*

### Team A6

1.) * Given "If x is a real number, then $\sqrt{x^2}=x$"

- Let x equal -2, $\sqrt{-2^2}=2$
- Letting x be -2 makes the hypothesis true, but the conclusion false since the square root of -2 squared is 2 and the statement is set equal to -2. We end up with 2 = -2 for the conclusion which is clearly false.

I think you mean $(-2)^2$ in the radical. (It's important to remember the order of operations.) But otherwise, this counterexample is presented nicely.

2.) X is sufficient for y represents "If Y, then X" because the term sufficient alludes to the idea that some X is an answer, solution, or result of Y in some way. It's as if the problem is suggesting that if X is sufficient for Y, we can say X is a conclusion of Y which of course must be written in the form "If Y, then X" where Y is the hypothesis and X is a conclusion. We can also say that if Y is the hypothesis then X is not only a conclusion, but it represents a conclusion which has not yet been tested and proved as true or false.

What's written above sounds pretty confusing, and I'd guess that attempting to rewrite it all more clearly would have let you see you've actually got things the wrong way around…

I agree it comes down to understanding the term "sufficient". Maybe it helps to consider an English example. How about this: "Having a passport is sufficient for getting into the country" — Isn't the meaning here closest to, "If you have a passport, you can get into the country?" Maybe that helps illustrate the problem.Another way to think of it is that "X is sufficient for Y" is saying that if you want to know that Y is true, it's enough (i.e., sufficient) to know that X is true. That is, if you know X is true, then you know Y is true. So… "If X, then Y" is more like it.

3.) Implication: $n^2$ is even only if $n$ is even.

Hypothesis: $n$ is even.

Conclusion: $n^2$ is even.

No, I think you have this backwards. Think about it this way: The sentence "X if Y" is obviously the same as "if Y, then X". The statement "X only if Y" is the other way around. It's saying that X is true

only ifY is true. The only way that's false is if X is true without Y being true — just like the statement, "If X, then Y."Wow, I do think it's just naturally confusing to think about, though. See also my comments on Team A1's answer to Question 2.

4.) If the Earth is in the sun, then dogs are cats. The hypothesis is false, thus this implication is vacuously true.

Good!

5.) x+y=0

The order of the variables are quantified matters because if you apply (a) to the statement it will be true. For each individual x value that you plug in there will be a unique y value that exists to make this statement true. However, (b) would be false because when you switch the quantification of the variables the meaning is changed. In this case the statement is saying that there would be one individual y value which satisfies all x values to make the statement true, which of course is false. Therefore (a) is true and (b) is false

Okay, fine. It is "of course" false, as you say. However, I think your explanation could be better, simply because nothing you wrote made any reference at all to the specific predicate "x+y=0" that you chose!

6.)x=y+1

The order of the quantifiers matters, (a) is true because for each individual x value there exists a unique y value that makes x=y+1 true. On the other hand (b) is false because when you switch the order of the quantifiers there is no single x value unique for all y values which makes the statement x=y+1 true. Therefore (a) is true and (b) is false.

Sounds good to me! I guess if you pick the right sort of predicate, Question 5 and Question 6 here become very similar, don't they? Interesting…