### This assignment has been graded.

### Questions

1. **Choose one** of the following statements and write its negation. Express the new statement in positive terms to the extent possible. (This means that you should avoid using words like "not" or "no" wherever possible.)

- For every real number x, there is a real number y such that $x^y=1$.
- There is a real number x such that for every real number y, $x^y=1$.
- There exists an $n \in \mathbb Z^+$, such that $m \ge n$ for all $m \in \mathbb Z$.
- There exists a $p \in \mathbb Z^+$ such that p is prime and p is even.
- For all positive real numbers x, x^2-x is nonnegative.
- There is a movie that everyone has seen.

2. **Choose one** of the following statements and write its negation. Express the new statement in positive terms to the extent possible.

- If x > y and y > z, then x > z.
- For all integers $m$, whenever $m$ is a square, $m^2=n^4$ for some integer $n$.
- For all $x \in \mathbb R$, $x^2 > 0$ implies $x > 0$.
- If $n$ is prime, then $2^n-1$ is prime.
- If $A \cap B = \emptyset$, then $A \not= B$.
- If A is a set, then every relation on A that is symmetric and transitive is also reflexive.

3. Let A={1,2,3}. **Choose one** of the following relations on A, and determine which of the properties of Definition 4.1.8 the relation has.

- {(1,1), (2,2), (3,3)}
- {(1,2), (2,3)}
- {(1,1), (2,3), (1,3)}
- {(1,1), (2,2), (1,3), (3,1)}
- {(2,3), (2,3), (1,2), (2,1)}
- $\emptyset$

4. Let A={1,2,3}. Give an example of a relation on A (list out its elements) that is neither reflexive nor symmetric, but is transitive.

5. Let A={1,2,3}. Give an example of a relation on A (list out its elements) that is reflexive and symmetric, but not transitive.

6. Suppose m and n are positive integers. **Choose one** of the following statements and write the beginning of a proof by contradiction of the statement. (You only need to write the part of the proof that establishes the initial assumptions! If you want to go beyond that, I'll award bonus points, but I won't read past any line that doesn't make sense. If you do decide to write more of the proof, it's okay to use facts such as that the sum of an odd integer and an even integer is always odd, or that every integer is either even or odd but not both, etc.)

- If mn is odd, then m and n are both odd.
- If m is odd, then m-1 is even.
- If m divides n, then m is less than or equal to n.
- If m-n is odd, then m+n is odd.
- If m+n is even, then m and n are both even or m and n are both odd.
- If m^2 is odd, then m is odd.

### Team C1

1. Statement:There exists a $p\in\mathbb Z^+$ such that $p$ is prime and $p$ is even.

Negation: For all $p\in\mathbb Z^+$, $p$ is composite or $p$ is odd.

Excellent!

2. Statement: For all integers $m$, whenever $m$ is a square, $m^2=n^4$ for some integer $n$.

Negation: There exists an integer $m$ such that $m$ is a square and $m^2 ≠ n^4$ for some integer $n$.

This looks good, except that the last quantifier is existential. So if it's not true that "$m^2=n^4$ for some integer $n$" then it must be true that "$m^2 ≠ n^4$ for

allintegers $n$", right?

3. {(1,1), (2,2), (1,3), (3,1)} is reflexive and symmetric.

Good. The relation is also transitive, however.

4. A relation on A that is neither reflexive nor symmetric, but is transitive is, {(3,1), (1,2), (3,2)}.

Good!

5.A relation on A that is reflexive and symmetric, but not transitive is, {(3.3), (3,1), (1,3)}.

This doesn't seem to be reflexive. Maybe have a look at the definition of "reflexive" in Definition 4.1.8?

6. If mn is odd, then m and n are both odd.

Proof:

P1: Assume $m$ and $n$ are positive integers.

P2: Let $m$ and $n$ be even.

P3: By definition $m=2k$ and $n=2l$ for some $k$ and $l$ ∈ $\mathbb Z^+$

P4: Let $mn$ be odd.

P5: By definition $mn=2x+1$ for some $x ∈ \mathbb Z^+$.

P6: By algebra $mn = (2k)(2l) = 2x+1$ so $2(2kl) = 2x+1$.

P7: Let $2kl = y$ for some $y$ ∈ $\mathbb Z^+$.

P8: By algebra $2y = 2x+1$

P9: Since y and x are integers $2y$ will never equal $2x+1$.

P10: By definition $2y$ is even and $2x+1$ is odd; an odd integer is never equal to an even integer.

P11: Therefore, if $mn$ is odd then $m$ and $n$ are both odd. QED

This is actually quite well executed here… The only problem is that your assumptions do not amount to the negation of the statement to prove. That is, what would it mean for it to

notbe true that "If mn is odd, then m and n are both odd" — it would mean that there are some integers m and n such that mn is odd buteitherm is evenorn is even. So that's what you would have to assume. (Making such an assumption and using it properly is tricky; I think this was the trickiest of the statements to choose from for this problem.)

*Comments:*

### Team C2

1. Statement: For every real number x, there is a real number y such that $x^y$=1.

Negation: There is a real number x for every real number y such that $x^y$<1 or $x^y$>1.

This is very good. There is, however, a subtle difference in meaning between saying "There is a BLAH for every BLORG such that…" and saying "There is a BLAH such that for every BLORG…" Consider the following example:

"There is a movie for every person such that the person will enjoy watching the movie."

-vs-

"There is a movie such that for every person the person will enjoy watching the movie."The lesson here is that the placement of the "such that" is something you need to think about.

2. Statement: If n is prime, then $2^n$-1 is prime.

Negation: If n is prime, then $2^n$-1 is composite.

Here there's definitely a problem. What does it mean for the statement "If X, then Y" to be false? It means that X is true and yet Y false. Note that this last statement is not an implication! This is a general phenomenon, that what it means for an "if-then" statement to be false cannot usually be expressed as an "if-then" statement.

In the context of this particular example, knowing that the original statement is false would mean knowing that there is a prime number $n$ such that $2^n$-1 is composite.

3. {(2,3), (2,3), (1,2), (2,1)} is symmetric because whenever x is related to y, y is related to x. The set contains both the elements (1,2) and (2,1) which show the symmetric property.

Good!

4.A relation on A that is neither reflexive nor symmetric, but is transitive is {(1,3), (3,2), (1,2)}.

Good!

5. An example of a relation on A that is reflexive and symmetric, but not transitive is {(1,1), (2,2), (3,3), (2,3), (3,2), (1,3), (3,1)}.

Great!

6. "If $m^2$ is odd, then m is odd."

P1: Assume m is in the positive integers.

P2: Assume $m^2$ is odd and m is even.

P3: This means that $m^2$=2k+1 for some integer k and m=2j for some integer j.

P4: So, if $m^2$=2k+1 and m=2k, then $(2j)^2$=2k+1

<=> $4j^2$=2k+1

<=> 2$(2j^2)$=2k+1

P5: Let $(2j)^2$ be a positive integer.

P6: This means that 2$(2j)^2$ is even by definition.

P7: Since 2k+1 is odd by definition, $(2j)^2$ cannot equal 2k+1 because an even number cannot equal an odd number.

P8: Therefore, if $m^2$ is odd, then m must be odd.

QED

I think "2k" should be "2j" in P4, right? Also in P4, there is no need to say "if" $m^2$=2k+1, when you have by P3 that this is in fact so. Those are just tiny little points, however — overall, excellent job!!

*Comments:*

### Team C3

1.) Statement:There exists an $n \in \mathbb Z^+$, such that $m \ge n$ for all $m \in \mathbb Z$.

Negation: For all $n \in \mathbb Z^+$, there exists $m \in \mathbb Z$ such that $m \le n$

Very nice; this was made tricky by the fact that the last quantifier was placed at the

endof the original statement, but you guys handled this wrinkle successfully.

2.)Statement: If A is a set, then every relation on A that is symmetric and transitive is also reflexive.

Negation: There exists a set A such that a relation on A that is symmetric and transitive is not reflexive.

This is nearly perfect, however it would have been better to say "such that

somerelation on A" instead of "such thatarelation on A" because often the indefinite article is used to express a universal statement, e.g. "a positive number has a positive cube root" will be interpreted (albeit somewhat informally) as saying that "everypositive number has a positive cube root", see?

3.)* {(1,1), (2,3), (1,3)} This Set is antisymmetric.

Yes; I think that is the only property of the four that this relation has.

4.) If A={1,2,3} then an example of a relation that is neither reflexive or symmetric but is transitive is {(2,3), (3,1), (2,1)}

Yep.

5.) If A={1,2,3} then an example of a relation that is reflexive and symmetric but not transitive is {(3,3), (2,2), (1,1)}

This relation is transitive, unfortunately, because the statement "x ~ y and y ~ z" is true only when x=y=z, and in that case x~z holds.

6.) Theorem: If $m-n$ is odd, $m+n$ is odd.

P1. Assume $m-n$ is odd, but $m+n$ is even.

P2. This means $m-n = 2k + 1$ for some $k\in\mathbb Z^+$ and $m+n=2j$ for some $j\in\mathbb Z^+$

P3. Then $m = 2k +1 + n$

P4. So $2k +1 + n +n=2j$

P5. So $2n = 2j - 2k -1$ which is equivalent to $n = j - k - \frac{1}{2}$

P6. So $n$ is not an integer.

P7. Since a number cannot simultaneously be and not be an integer, this contradiction leads us to understand that $m-n$ is odd, $m+n$ is odd.

Your assumption that $k\in\mathbb Z^+$ in P2 doesn't make sense; just because m and n are positive doesn't imply that m-n will be, right? Removing the "+" there wouldn't alter your proof in any way, of course.

No, this is very nice! It's so nicely written that I hesitate to point out that I would have let you use the fact that the sum of two odd numbers is always odd and that therefore if m-n and m+n are odd, then necessarily (m-n)+(m+n)=2m is odd, which will give you a contradiction in the obvious way. But I actually like this proof better, since it doesn't rely on any other results, but just the definitions of even and odd. Well done!

*Comments:*

I spent some time thinking about number two a little too literally (its negation being the conjunction of the hypothesis and negation of its conclusion) but I realized that saying "such that" works as "and" in this case.

For number 3, I don't believe the relation is reflexive or transitive. According to definition 4.1.8, a relation is only reflexive is for *every* element $x m$ in A, $x \sim x$. This doensn't appear to be the case here.

### Team C4

1. Statement: For all positive real numbers x, x^2-x is nonnegative.

Negation: There exist a positive real number x such that x^2-x is negative.

Looks pretty good!

2. Statement: If x > y and y > z, then x > z.

Negation: If x is greater than y and y is greater than z, then z is greater than x.

This has two problems. The first is that (see, e.g. Team 3's answer for this question) the negation of "if X, then Y" is not "if X, then not Y". The second is that the negation of "x > y", for instance, is "x ≤ y" and not "x > y".

3.{(1,1), (2,2), (3,3)}

This is reflexive because every element in A is related to itself.

Good. However, the relation is also transitive. It's also symmetric. It's also antisymmetric.

4. A relation on A that is neither reflexive nor symmetric, but is transitive is {(1,2), (2,3), (1,3)}.

Yeah… there was essentially only one choice for this, up to how the elements of A are ordered. Fortunately, there are six different ways to order them!!

5. An example of a relation on A that is reflexive and symmetric, but not transitive is {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}.

Looks good!

6. If m is odd, then m-1 is even.

P1: Assume m is a positive integer and odd and suppose m-1 is odd.

P2: This means there exists integers k and j such that m=2k+1 and m-1=2j+1 (which can be written as m=2j+2)

P3: If m=2k+1 and m=2j+2, then 2k+1=2j+2

<=> 2k = 2j-1

<=> 2k-2j=-1

<=> 2(k-j)=-1

<=> k-j=-1/2

QED

P4: Since k and j are integers there is no possible way for k-j to equal a fraction (which is not an integer).

P5: Therefore if m is odd, m-1 cannot be odd so it must be even.

I think there is a "sign error" in the middle of P3; the -1 should be a +1. But otherwise this looks great!

*Comments:*

### Team C5

1) Statement: There is a movie that everyone has seen.

Negation: For every movie, there exist someone who is to lazy to see it.

(this negation implies that for every movie there is someone who has not seen it using positive terms)

How do you know the problem is laziness?!? There is a good reason I haven't seen

Alvin and the Chipmunks: Chipwrecked, for example, and it's not because I was too lazy. Also, I think you mean "too" lazy. So there.

2) Statement: For all $x \in R$ , $x^2 > 0$ implies $x > 0$

Negation: There is a $x \in R$ where $x^2 > 0$

I think you mean "There is

an$x \in \mathbb R$", but in any case it's not clear how you attempted to handle the "implies" part of the original statement.

3) ∅

This relation only has the property of reflexive from Definition 4.1.8 since it is reflexive of itself by definition.

The definition of reflexive is that "For all x in A, x is related to x." Since nothing is related to anything else in this case, the relation here is definitely not reflexive. Moreover, since the other three properties are all defined by implications that will be vacuously true when applied to this relation, $\emptyset$ as a relation on A in fact

issymmetric, antisymmetric and transitive.(Also, what is "it is reflexive of itself" supposed to mean?)

4) A = {1,2,3}

~={(3,2), (2,1), (3,1)}

Nice.

5) A = {1,2,3}

~={(3,3)}

This will not be reflexive on A, although it is symmetric and transitive.

6) If $n | m$, then $m \le n$.

Proof:

P1: Assume $m \in Z^+$ and $n \in Z^+$.

P2: Assume $n | m$.

P3: By definition, $m$ divides $n$ when there exist an integer $a$ such that $n = ma$.

P4: Thus, $m \le n$. QED

I don't think $n=ma$ implies that $m \le n$ without the assumption that $a \ge 1$. Of course, if you wanted to, you could deduce that $a \ge 1$ from the fact that m and n are

positive. But this is all missing the point of the problem, which was to set up a proof by contradiction. As the instructions indicate, anything beyond "the part of the proof that establishes the initial assumptions" here is just extra credit, beyond what the question is actually asking for. There doesn't seem to be any attempt at a proof by contradiction here.

*Comments:*

- For number 3 wouldn't the empty set be reflexive (ie wouldnt the empty set be related to itself). Not 100% sure on this, but wanted to make sure that this possibility had been considered.

### Team C6

1.) Original: There is a real number x such that for every real number y, xy=1.

Negation: For all x, there exists a real number y such that xy ≠ 1.

You could have won some style points (as opposed to wiki points) by saying "xy > 0 or xy < 0", in order to state it more in positive terms, as opposed to using the "NOT equal to" symbol. But otherwise this looks good; the quantifiers were handled well.

2.) Original: If $A \cap B = \emptyset$, then $A \not= B$.

Negation: If $A \cap B = \emptyset$, then $A = B$.

As noted in earlier solutions to this problem, the negation of "If X, then Y" is not "If X, then not Y". (See the top of page 27 in

Chapter Zero, for example.)

3.) {(1,2), (2,3)} this relation has no properties of definition 4.1.8.

This relation is antisymmetric, since the statement "if x ~ y and y ~ x, then y=x" is vacuously true for every x and y in A. I agree that the relation does not have any of the other three properties, however!

4.) Let A = {1,2,3}. A relation that is not reflexive or symmetric, but is transitive is: ~ = {(2,3), (1,3), (2,1)}.

Great!

5.) Let A = {1,2,3}. A relation that is reflexive and symmetric, but is not transitive is: ~ = {(2,2), (3,3), (2,3), (3,2)}.

Again, this is not reflexive on A. And it

istransitive. It is, at least, symmetric, however.

6.) **If m+n is even, then m and n are both even or m and n are both odd.
Proof:**

P1: Assume $n \in \mathbb Z^+$ and $m \in \mathbb Z^+$.

P2: Assume n is even.

P3: Then by definition, there exists an integer k such that n = 2k.

P4: Assume m is odd.

P5: Then by definition there exists an integer j such that m = 2j+1.

P6: Then m+n = (2k) + (2j +1) = 2(j+k) + 1.

P7: Let h = j+k.

P8: Then m+n = 2h + 1.

P9: Thus, the sum of m and n is odd.

QED

This is a pretty good proof, except that you forgot to assume that m+n is even at the beginning. You want to assume that m+n is even

butn is even and m is oddorthat n is odd and m is even. By symmetry, just considering one of those two latter cases is enough, and that's what you've done here, and it looks like you did so successfully. Nice work.