Write clear, readable proofs.
Using proof by contradiction, prove that, if n is an integer where n3 + 5 is odd, then n is even.
The proof is by contradiction.
¬(p → q) ≡ (p ∧ ¬q). So the negation of the claim is: n3 + 5 is odd and n is odd. Assume that n3 + 5 is odd and n is odd.
Since n is odd, n = 2k + 1 for some k. So
| n3 + 5 | = | (2k + 1)3 + 5 |
| = | 8k3 + 3(4k2) + 3(2k) + 1 + 5 | |
| = | 2(4k3 + 3k2 + 3k + 3) |
which implies that n3 + 5 is even. That contradicts the assumption that n3 + 5 is odd.
Prove the following by contradiction: There does not exist a rational number r such that r3+r+1=0. (Hint. Suppose that r=a/b where a and b are integers and fraction a/b is in lowest terms. Multiply both sides of equation r3+r+1=0 by b3. Then consider whether a and b are each even or odd.)
The proof is by contradiction.
Suppose that there exists a rational number r where r3 + r + 1 = 0.
Choose integers a and b so that r = a/b and fraction a/b is in lowest terms. Then
Multiplying both sides of that equation by b3 gives
Now consider whether each of a and b is even or odd.
a and b cannot both be even, since fraction a/b is in lowest terms.
a and b cannot both be odd. If a and b are both odd then a3, ab2 and b3 are all odd. Since the sum of three odd numbers is odd, a3 + ab2 + b3 must be odd, and cannot be 0.
It is not possible for a to be even and b to be odd. If that is true, then a3 is even, ab2 is even and b3 is odd. So a3 + ab2 + b3 is the sum of two even numbers and an odd number, which is odd, and cannot be 0.
It is not possible for a to be odd and b to be even. If that is true, then a3 is odd, ab2 is even and b3 is even. Again, a3 + ab2 + b3 is the sum of two even numbers and an odd number, which is odd, and cannot be 0.
Prove that ∃x∀yP(x,y) → ∀y∃xP(x,y) is valid. That is, prove that it is true no matter what the definition of P(x, y) is.
This was intended to be easy, but it apparently is not. I will take it step by step.
We are asked to prove an implication. Let's do a direct proof. So assume ∃x∀yP(x,y). We will prove ∀y∃xP(x,y).
Now we have existential knowledge, because we know ∃x∀yP(x,y). When you know that something exists that has property A, select a value that satisfies property A, and give that value a name.
Note that ∃x∀yP(x,y) is the same as ∃x(∀yP(x,y)). Select r so that ∀yP(r,y) is true.
We know that P(r,y) is true for every y. So, for every y, there is an x that makes P(x, y) true, namely, x = r.
Writing that in logic, we know that ∀y∃xP(x,y) is true.
Prove that for every nonzero real number x there exists a real number y such that xy=1. What algorithm does your proof use?
This was intended to be trivial. You know how to solve equation xy = 1 when x ≠ 0. The solution is y = 1/x.
Choose y = 1/x. The algorithm is the algorithm that takes the reciprocal of a real number.
Prove that, for every nonnegative real number x there is a real number y such that y2 − x = 0. What algorithm does your proof use?
You know how to solve equation y2 − x = 0 for y. Choose y to be the square root of x. The algorithm is the algorithm that computes the square root of a real number.