### This assignment has been graded.

### Questions

1. Give an example of a predicate P(x) that makes the statement "For all x, P(x)" true when the universe of acceptable values for the variable x is the positive integers.

2. Give an example of a predicate P(x) that makes the statement "For all x, P(x)" true when the universe of acceptable values for the variable x is the positive integers, but false when the universe of acceptable values is *all* integers.

3. Suppose that the universe of acceptable values for our variables is the positive integers. Give an example of a predicate P(x) such that the statement "For all x, P(x)" is false, but the statement "There exists an x such that P(x)" is true.

4. **Choose one** of the following predicates in the variables x and y. Explain whether the statement "For all x, there exists a y such that P(x,y)" is true or false. Then explain whether the statement "There exists an x such that for all y, P(x,y)" is true or false. Assume that the universe of acceptable values for x and y is the positive integers.

- P(x,y) := $x+y=y$
- P(x,y) := $xy=y$
- P(x,y) := $x^2 = y$
- P(x,y) := $x = -y$
- P(x,y) := $y = x/2$
- P(x,y) := $x \not= y$

5. **Choose one** of the following statements. If it's an implication, rephrase it as a universally quantified statement. (This universally quantified statement should indicate explicitly the universe for its variables — that is to say, it should not begin with "For all x" but rather with, e.g., "For all blorgs x", if you wanted the universe of acceptable values for x to be all blorgs.) If, on the other hand, it is already a universally quantified statement, rephrase it as an implication. (In this case, the statement will indicate explicitly its universe of acceptable values.)

- If n is a positive integer, then $n^2+n = n(n+1)$.
- For all real numbers x, $x^2 > x$.
- If x is a real number between 0 and 1, then $x^2 < x$.
- For all negative numbers x, $-x > x$.
- If p and q are powers of 2, then pq is a power of two.
- For all positive integers n, gcd(n,n+1)=1.

### Team A1

1. $P(x) = x > 0$. This predicate shows "For all x, P(x)" is true when the universe of acceptable values for the variable $x$ is positive integers.

Okay, definitely! And a good, complete explanation.

2. $P(x) = x > 0$. This predicate works when $x$ is the positive integers but false when the universe of acceptable values is all integers because it does not work for negative integers.

Yes — sounds good. I think you mean "when $x$ is

a positive integer" since of course $x$ does not represent all the positive integers at once. (Maybe that's kind of a subtle distinction.)

3. $P(x) = x^2$ = an even number. This is a false statement because for example, $7^2= 49$ which is an odd number yet there exists an $x$ such as $4$ that makes P(x) true. $4^2 = 16$.

This is very good, although you should be careful about using a word like "this" since it can easily introduce some ambiguity. For example, by "this" it sounds like you're referring to "$P(x) = x^2$ = an even number", even though that's not what you're saying is false.

4. The expression “For all $x$, there exists a $y$ such that $P(x,y)$" is false for all positive integers when $P(x,y)= x+y=y$. If $x=1$ and $y=2$ then $P(x,y) = 3$. In this case, $P(x,y)$ states that $3=2$, which is false. This accounts for all positive integer values for $x$ and $y$.

The expression "There exists an $x$ such that for all $y$, $P(x,y)$" is false for all positive integers when $P(x,y)= x+y=y$. If $x=5$ and $y=6$ then $P(x,y) = 11$. In this case, $P(x,y)$ states that $11=6$, which is false. There is no case in the domain of positive integer values that make the statement true.

I agree that "For all x, there exists a y such that P(x,y)" is false when P(x,y) is "x+y=y", since x+y=y implies that x=0, and P(x,y) cannot be true when x and y are positive integers. I also agree that "There exists an x such that, for all y, P(x,y)" is false, since for any positive integer x, if we take y=1, we will have x+y > y.

Unfortunately, your explanation has some serious problems. For example, "P(x,y)=3" is nonsense; P(x,y) is a statement — how can it be equal to three? I do agree that if x=1 and y=2, then P(x,y) states that 3=2, which is false. That is definitely enough to show that "For all x and y, P(x,y)" is a false statement, but that's not the quantification for x and y that you're looking at.

5. Original Statement (Implication): If $x$ is a real number between 0 and 1, then $x^2<x$

Quantified Statement: For all $x$ between 0 and 1, x^{2}<x.

Excellent!

*Comments:*

### Team A2

1. P(x)= x^{2} ≥ x. This predicate makes the statement "For all x, P(x)" true when the universe of acceptable values for the variable x is the positive integers.

No question this is right, and well-presented.

2. P(x)= x^{0} ≤ x. This predicate makes the statement "For all x, P(x)" true when the universe of acceptable values for the variable x is the positive integers. However, this predicate makes the statement false when the universe of acceptable values is ALL integers.

Whoa… x

^{0}. Craziness. Props for not just re-using your predicate from (1), although of course you could have. (In fact, given that you didn't, I suppose another team could have used it, too.)

3. Note that the universe of acceptable values for our variables is the positive integers. The predicate, "P(x)= x is a prime number" makes the statement "For all x, P(x)" false but it makes the statement "There exists an x such that P(x)" true.

Excellent. I suppose I should whine about how you didn't actually point out a value for x that would make P(x) true or something. But that would be excessive. Even for me.

4. In our case, let P(x,y) := x≠y. Note that the universe of acceptable values for x and y is the positive integers. The statement "For all x, there exists a y such that P(x,y)" is true because for every positive integer x, there will always be a different positive integer. Example, 1≠ 2, 2≠3, 3≠4 and so on.

The statement "There exists an x such that for all y, P(x,y)" is also true because if it is true for all positive integers x, there must exist at least one x that makes the predicate true.

The explanation here for the first part is excellent, and makes perfect sense. For the second part, I don't think that that statement is also true, and I'm totally unsure of what you mean by "it" when you say "if it is true for all positive integers x". In any case, the statement "There exists an x such that for all y, P(x,y)" here is false — it's saying that there is some positive integer x such that every positive integer y is different from it.

Reference chart/table on page 17 in Chapter Zero: Section 1.5.

5. Original (quantified statement): For all real numbers x, X^{2} > x.

Implication: For all x, X^{2} >x.

I'm not sure if there's some confusion about what's meant by "implication", but here you need something written in an "if-then" form.

*Comments:*

### Team A3

1. $P(x) =$ “$x$ has a real square root.” Since the question says that the universe here is positive integers, we know that $x$ won't be negative, so we're not going to have any weird imaginary roots popping up.

Good point; positive numbers have real square roots, so it sounds true enough. It's true that those square roots need not be integers (positive or otherwise) but that is not a problem.

2. $P(x) = |x-1|< x$ So when we have a positive number like 5, $5-1=4$, and $4<5$. But for a negative $x$, like $-5$, $-5-1=-6$, and $6>5$.

This is blowing my mind… subtracting 1 makes the absolute value smaller — but only if the number you start with is positive! Awesome!

3. $P(x) =$$3x = 6$. Obviously, this won't work for all $x$, but there is, indeed an $x$ that makes this statement true. (It's 2!)

Where by "work" you mean "be true"? And yes, there is a

value forx which makes it true. Very nice.

4. In our case, let $P(x,y): = xy=y$. The statement, "For all $x$, there exists a $y$ such that $P(x,y)$ is false because for that statement to be true, $x$ can only equal one value, which is $1$. The statement, "There exists an $x$ such that for all $y$, $P(x,y)$ is true because this statement allows for $x$ to equal one which will always make the statement true.

I think you should be more clear what you mean by "that statement", since you don't mean the

wholestatement you just wrote, but rather only the part "there exists a y such that P(x,y)". But yeah, excellent work explaining both of your assertions here.

5. Original: (quantified statement): for all negative numbers $x$, $-x>x$.

Implication: If $x$ is a negative number, then $-x > x$

Great!

*Comments:*

### Team A4

1. "For all x, $x \geq 1$." This statement is true based on the prerequisite that this is in the universe of positive integers.

Yes. Be careful about using words like "this", since they tend to introduce ambiguity that can be dangerous. Here by "this" I think you mean x, but in a different context it might make things confusing. Also, since the question asked specifically for a predicate P(x), you need to make it explicit what sentence you are taking as P(x), since it's not the entire sentence you quoted above. (This last comment applies to what you wrote for the next two questions as well.)

2. "For all x, $x^3 \geq 0$." This statement is true when it is in the universe of positive integers. However, it is false when it could be any integer because negative integers make it less than zero.

Sounds good to me. In your first, sentence, though, by "it is in the universe of positive integers" I don't think you mean to say that

the statementis in that universe. So be careful to be precise in how you put things — I think you really mean that "it is to be interpreted with the universe of discourse taken as the positive integers", although there's probably a more succinct way to put it.

3. "For all x, $\sqrt {x} = 1$." This statement is false because the square root of 2 or any other integer does not equal one. However, if we modify the statement to say, "There exists an x such that the $\sqrt {x} = 1$," then the statement becomes true if x = 1.

I like this, and it's very well-explained. I should point out that the statement "the square root of 2 or any other integer does not equal one" is false, however, since (as you point out) the square root of 1 is in fact 1. Your first (universally quantified) statement is false because there is at least one integer, like 2, that could be assigned to x which would make the predicate false.

4. "For all x, there exists a y such that P(x,y) := x=−y" is false. Even if we alter the equation to say, "There exists an x such that for all y, x=-y," that would still be false. If x and y are always positive integers then there does not exist a value of x or y to fulfill the answer to the equation.

Yeah! Any time x and y are positive integers, x=-y is false! So, great point — it doesn't even matter how x and y are quantified; since our domain is the positive integers, the predicate "x=-y" itself can

neverbe true.By the way, when you write "fulfill the answer to the equation", I want to urge you to be precise with your language. I think you mean "there do not exist values of x and y that make the equation true".

5. Implication: If n is a positive integer, then $n^2 + n = n (n + 1)$.

Quantified Statement: For all positive integers n, then $n^2 + n = n (n + 1)$.

This is perfect, except that you don't want the word "then" in the quantified statement. (There's no "if", after all.)

*Comments:*

### Team A5

1) The predicate P(x) = x^{2} ≥ x makes the statement, For all positive integers x, x^{2} ≥ x , true.

I think you mean it makes the statement "For all positive integers x, P(x)" true. (Since a choice for P(x) only does something for a statement that actually has P(x) in it…) But good choice of predicate.

2) The predicate P(x) = x^{3} ≥ 0 makes the statement, For all positive integers x, x^{3} ≥ 0, true. However makes the statement, For all integers x, x^{3} ≥ 0, false.

Same issue here as before. Although it is a very tiny issue. Nice predicate!

3) The predicate , x+2=5 makes the statement , For all x, x+2=5 , false. However makes the statement , There exists and x such that x+2=5 , true.

Okay, this predicate looks good, although your explanation doesn't do more than restate the problem.

4) When P(x)=x^{2}=y, for all x there exists a y such that x^{2}=y. This is true because if you take any positive integer and square it there will be a y to match. For example. 5 squared is 25 and if y is equal to 25 it makes that statement true. Likewise, "There exists an x that for all y…" is also true. Take any number to be y and square it to find x. For example, take y to equal 16. There does exist an x that would make y equal to 16 and that x is a 4.

Your first sentence here reads a little strangely. However, the quantified statement is indeed true, and your explanation is great. You're saying, "Given any positive integer x, take y=x^2. Then x and y will both be positive integers and P(x,y) will be true." Oh, and there's even an example! (For x=5?)

For the second statement, with the quantifiers in the other order, I'm pretty sure the statement actually is false. It's saying that there is some value you can pick for x such that no matter what value you pick for y, you will have x

^{2}=y. And that's not so.

5) For all negative numbers x, -x>x. is a quantified statement. If it were to say for all x, -x>x then it would be a implicated.

For an implication, you need a statement with an "if-then" form, like, say, "If x is a negative number, then -x > x." (And: "a implicated"?)

*Comments:*

### Team A6

1) For all positive integers x, 4x ˃ x This predicate shows that "For all x, P(x)" is true when the values given for x are positive integers

Yes, if we take "4x > x" as P(x), then it does make "For all x, P(x)" a true statement. You need to be clear about what you're choosing as P(x), however. In particular, you are not choosing P(x) to be "For all positive integers x, 4x > x", but rather to be "4x > x".

2) For all positive integers x, x ˂ x^{3} This predicate shows that "For all x, P(x)" is true when the values give for x are positive integers and not both negative and positive integers

"For all positive integers x, x < x

^{3}" is a false statement; as a counterexample, let x=1. Then x is a positive integer, however x is not less than x^{3}, since x^{3}= 1 = x. Also, as for the question above, it's not made explicit precisely what you meant to take as your predicate P(x).

3)For all x, x^{2}=2x.

This predicate looks promising, but I don't see any account of what the reasoning was behind choosing it.

4)For the predicate P(x,y) := x+y=y the statement “For all x, there exists a y such that P(x,y)” is false. For any value of x other than 0, there is no value of y that would make P(x,y) true. The statement “There exists an x such that for all y, P(x,y)” is true. If the value of x is equal to 0, the statement will be true for any value of y.

The bad news is that Team A1 had already taken "x+y=y". On the other hand, this explanation seems quite a bit more clear. I even like the second part of your explanation, despite that it overlooks that our domain is the

positiveintegers, and hence the value 0 is excluded for x.

5)

Implication to Quantified Statement:

If x is a real number between 0 and 1, then x^{2} < x

For all real numbers x between 0 and 1, x^{2} < x

Quantified statement to Implication:

For all real numbers x, x^{2} > x

If x is a real number, then x^{2} > x

Unfortunately, both of these statements had already been addressed by other teams, so see my comments elsewhere.