Definition 2.5.1. Even Integer.
A number \(n\) is said to be even if it is a multiple of 2. That is, if there exists an integer \(k\) such that \(n = 2k\text{,}\) then \(n\) is even.
Section 2.5 An introduction to proofs
In this section we’ll combine everything we’ve done so far in the book to introduce the idea of mathematical proof. We will take statements about numbers, functions, or sets, decompose them into quantified statements and reason using argumentation and rules of logic to draw conclusions. We will do this by writing complete English and mathematical sentences that take us from beginning to end, telling the story of the argument.
Subsection
Before we start, we need to formally define some basic concepts of numbers.
Example 2.5.2.
- 6 is even since \(6 = 2\cdot 3\)
- 0 is even, since \(0 = 2\cdot 0\)
- -8 is even, since \(-8 = 2 \cdot (-4)\)
- 9 is not even, since there is no integer \(k\) such that \(9=2k\)
Definition 2.5.3. Odd Integer.
A number \(n\) is said to be odd if it is not a multiple of 2. That is, if there exists an integer \(k\) such that \(n = 2k + 1\text{,}\) then \(n\) is odd.
Example 2.5.4.
- 7 is odd since \(7 = 2\cdot 3 + 1\)
- -1 is odd, since \(-1 = 2\cdot (-1) + 1\)
- 8 is not odd, since there is no integer \(k\) such that \(8=2k+1\)
Definition 2.5.5. Rational Number.
A number \(n\) is said to be rational if there exist integers \(a, b\) with \(b \not=0 \) such that \(n = \dfrac{a}{b}\text{.}\) If a number is not rational, we say that it is is irrational.
Example 2.5.6.
- 7 is rational since \(7 = \frac71\)
- \(\frac12\) is rational, since both 1 and 2 are integers
Note that every integer is a rational number, since if \(n\) is an integer, then we can write \(\frac{n}{1}\) which is a rational number. Not every rational number is an integer, for example, \(\frac{1}{2}\) is not an integer.
There are also numbers which are not integers and also not rational. We’ll give an example later in this section.
Subsection Basic concepts of proof
Definition 2.5.7. Statement Terminology.
- A theorem is a statement can be shown to be true. We generally reserve the word theorem for an important statement.
- A proposition is a “less important” theorem.
- The tools we use to prove a theorem are axioms (or postulates) which are basic assumptions we make, as well as other theorems we’ve already proven.
- A less important theorem that will be helpful in proving others is called a lemma.
- A corollary is a theorem that follows directly from a theorem just proved.
- A conjecture is a statement that we think may be true (our intuition suggests it)
Example 2.5.8.
Here’s a proposition: “If \(n\) is an odd integer, then \(n^2\) is odd.”
This statement means for the universe of discourse of all integers:
\begin{equation*}
\forall n ((n \text{ is odd } ) \to (n^2 \text{ is odd }))
\end{equation*}
The universe of discourse was implied in the general statement above. Mathematical propositions will almost always omit the words “for all.”
Subsection Direct Proof
A direct proof is used when proving a proposition of the form \(p \to q\text{.}\) The goal is to show \(q\) is true when we assume \(p\) is true. Here’s the model:
Proof.
Assume \(p\) is true.
... use logical equivalences (and/or mathematics) ...
Therefore \(q\) is true.
Example 2.5.9.
Prove that the sum of two odd numbers is even.
Example 2.5.10.
Prove that if \(n\) is even, then \(n^2\) is even.
Example 2.5.11.
Prove that if \(m+n\) and \(n + p\) are even integers, then \(m+p\) is even.
Subsection Indirect Proofs
We still want to show a statement is true, but perhaps that’s difficult to approach directly. There are several different indirect proofs. The most frequent indirect approaches are proofs by contraposition and proofs by contradiction.
Subsubsection Proof by Contraposition
. A proof by contraposition is a direct proof of \(\neg q \to \neg p\text{.}\) Here’s the model:
Proof.
Assume \(\neg q\) is true.
... use logical equivalences (and/or mathematics) ...
Show \(\neg p\) is true. Therefore, \(p \to q\) is true by contraposition.
Remember that \(\neg q \to \neg p \equiv p \to q\text{,}\) so this is a valid argument.
Example 2.5.12.
Show that if \(n\) is an integer and \(n^3 + 5\) is odd, then \(n\) is even.
Example 2.5.13.
Prove that if \(n^2\) is even, then \(n\) is even.
Subsubsection Proof by Contradiction
A proof by contradiction allows us to prove a statement \(p\) which is not necessarily conditional. We accomplish this by assuming \(\neg p\) is true, and finding a contradiction. This works because
\begin{equation*}
\neg p \to (q \wedge \neg q) \equiv p
\end{equation*}
as we showed in example. Here’s the model:
Proof.
Assume, to the contrary, that \(p\) is false, that is \(\neg p\) is true.
... use logical equivalences (and/or mathematics) ...
Arrive at a logical contradiction. Some impossibility. Therefore, \(p\) is true by contradiction.
Example 2.5.14.
Prove that \(\sqrt{2}\) is irrational
Subsection Proofs of equivalence
For statements which are “if an only if:” \(p \iff q\) we need to prove both \(p \to q\) and its converse \(q \to p\text{.}\)
Example 2.5.15.
Prove that \(n\) is even if and only if \(n^2\) is even.
Solution.
We actually did this in the two previous subsections. The forward direction and the converse.
Example 2.5.16.
Prove that \(n\) is even if and only if \(7n+4\) is even.
Example 2.5.17.
Prove the following are equivalent:
- \(\displaystyle a\lt b\)
- The average of \(a\) and \(b\) is greater than \(a\)
- The average of \(a\) and \(b\) is less than \(b\)
Subsection Proof by cases
Split an argument into completely separate pieces. In the example below we have two cases. Either \(x \ge y\) or \(x \lt y\text{:}\)
Example 2.5.18.
Show that if \(x\) and \(y\) are real numbers, then:
- max(\(x,y\)) = \(\dfrac{x+y + |x-y|}{2}\)
- min(\(x,y\)) = \(\dfrac{x+y - |x-y|}{2}\)
Note 2.5.19.
We need to prove each claim separately for each case!
Example 2.5.20.
Prove that \(5x + 5y\) is an odd integer when \(x\) and \(y\) are integers of opposite parity (not both even, not both odd).
Subsection Existence Proofs
The claim of an existence theorem is that there is some object that has a property. A constructive proof is one which, during the argumentation, tells the reader specifically how to come up with the object in question. A nonconstructive proof merely confirms the existence of an object, but doesn’t give any detail as to how to find it.
Example 2.5.21.
Prove that either \(2 \cdot 10^{500} + 15\) or \(2 \cdot 10^{500} + 16\) is not a perfect square.
Hint.
Let me get you started on it, and we can discuss below. Notice that the two numbers are one apart from eachother. They’re massive, so we don’t necessarily know whether they’re square, but we need only show that not more than one of them is square.
Let’s imagine that I have a square number, namely \(n^2\text{.}\) Is it possible that \(n^2 - 1\) or \(n^2 + 1\) is also a square number? What condition on \(n\) is required?
Example 2.5.22.
Show that between any two rational numbers is another rational number.
Hint.
If we have two rational numbers \(a/b\) and \(c/d\) with \(a, b, c, d \in \Z\) and \(b, d \ne 0\text{,}\) then we can construct \(\frac{a+c}{b+d}\text{.}\) Show that this is a rational number which is contained between the two original numbers.
Subsection Uniqueness proofs
The claim of a uniqueness theorem is that there exists an element that has a desired property, and that no other element has this property. The outline of our proof is often:
- Prove the existence of \(x\text{,}\) some element that has the property we want.
- Assume that a second element, \(y\) also has that property.
- Conclude that \(x = y\)
Example 2.5.23.
Show that if \(a, b, c\) are real numbers with \(a\ne 0\text{,}\) then there is a unique solution to the algebraic equation \(ax+b=c\text{.}\)
Hint.
You know how to solve an algebraic equation. Now assume there’s a second solution. Show that the two solutions are equal.
Example 2.5.24.
Show that if \(n\) is an odd integer, then there exists a unique integer \(k\) such that \(n = (k-2) + (k+3)\)
Hint.
Similar to above, show that \(k\) satisfies this equation, and then show that if you have another number, say \(l\) that also does, it must be the case that \(k = l\text{.}\)
Subsection Vacuous and Trivial Proofs
Definition 2.5.25. Vacuous Statements.
A vacuous statement is one that is true because the hypothesis is false. You can “prove” a statement is true immediately.
Example 2.5.26.
If I play in the Super Bowl, I will throw the game winning touchdown.
Solution.
Since I won’t ever play in the Super Bowl, it doesn’t matter what the truth value of the touchdown statement is. \(F\to T \equiv T\) and \(F \to F \equiv T\) just the same.
Definition 2.5.27. Trivial Statements.
If we know that the conclusion of a statement is true, then the statement has a trivial proof.
Example 2.5.28.
Let \(P(x)\) be the statement “If \(x\in \mathbb{R}\) and \(x \gt 0\) , then \(x^2 + 1 \ge 0\)”.
Solution.
Since we know that \(x^2 \ge 0\) for any real number, \(x^2 + 1 \ge x^2 \ge 0\text{.}\) We didn’t need the hypothesis \(x \gt 0\text{.}\) This is a trivial proof.
Subsection Counterexamples Revisited
Recall in math propositions, the universal quantifier is implied and is usually omitted. To show a statement is false, we need only find a single counterexample.
Example 2.5.29.
Each of the following statements is false. Find a specific counterexample and explain why the statement is false.
- If \(n\) is a real number, then \((n+4)^2 = n^2 + 16\text{.}\)
- Every integer is the sum of the squares of two integers.
- \(\forall x \forall y (x^2 = y^2 \to x = y)\) where the domain of all variables is the set of all integers.
- The product of two irrational numbers is irrational.
- The sum of two irrational numbers is irrational.
Solution.
- For example, \(n = 1\) works, since \((1+4)^2 = 25 \ne 17 = 1+16\text{.}\)
- The number 7 isn’t the sum of two squares. The only squares smaller than 7 are 1 and 4. They don’t add to 7.
- Choosing \(x= -1 \and y = 1\) we have \((-1)^2 = (1)^2\) but certainly \(-1 \ne 1\text{.}\)
- We know (from above) that \(\sqrt{2}\) is irrational. Multiply it by itself. You get \(2\) which is rational.
- Consider \(a = \sqrt{2}\) and \(b=-\sqrt{2}\text{.}\) Then their sum, \(a+b = 0\text{,}\) which is rational.
Exercises Exercises
1.
Consider the statement “for all integers \(a\) and \(b\text{,}\) if \(a + b\) is even, then \(a\) and \(b\) are even”
- Write the contrapositive of the statement.
- Write the converse of the statement.
- Write the negation of the statement.
- Is the original statement true or false? Prove your answer.
- Is the contrapositive of the original statement true or false? Prove your answer.
- Is the converse of the original statement true or false? Prove your answer.
- Is the negation of the original statement true or false? Prove your answer.
Solution.
- For all integers \(a\) and \(b\text{,}\) if \(a\) or \(b\) is not even, then \(a+b\) is not even.
- For all integers \(a\) and \(b\text{,}\) if \(a\) and \(b\) are even, then \(a+b\) is even.
- There are numbers \(a\) and \(b\) such that \(a+b\) is even but \(a\) and \(b\) are not both even.
- False. For example, \(a = 3\) and \(b = 5\text{.}\) \(a+b = 8\text{,}\) but neither \(a\) nor \(b\) are even.
- False, since it is equivalent to the original statement.
- True. Let \(a\) and \(b\) be integers. Assume both are even. Then \(a = 2k\) and \(b = 2j\) for some integers \(k\) and \(j\text{.}\) But then \(a+b = 2k + 2j = 2(k+j)\) which is even.
- True, since the statement is false.
2.
Consider the statement: for all integers \(n\text{,}\) if \(n\) is even then \(8n\) is even.
- Prove the statement. What sort of proof are you using?
- Is the converse true? Prove or disprove.
Solution.
- Direct proof.
Proof.
Let \(n\) be an integer. Assume \(n\) is even. Then \(n = 2k\) for some integer \(k\text{.}\) Thus \(8n = 16k = 2(8k)\text{.}\) Therefore \(8n\) is even. - The converse is false. That is, there is an integer \(n\) such that \(8n\) is even but \(n\) is odd. For example, consider \(n = 3\text{.}\) Then \(8n = 24\) which is even but \(n = 3\) is odd.
3.
Your “friend” has shown you a “proof” he wrote to show that \(1 = 3\text{.}\) Here is the proof:
Proof.
I claim that \(1 = 3\text{.}\) Of course we can do anything to one side of an equation as long as we also do it to the other side. So subtract 2 from both sides. This gives \(-1 = 1\text{.}\) Now square both sides, to get \(1 = 1\text{.}\) And we all agree this is true.
What is going on here? Is your friend’s argument valid? Is the argument a proof of the claim \(1=3\text{?}\) Carefully explain using what we know about logic.
Hint.
Hint: What implication follows from the given proof?
4.
Suppose that you would like to prove the following implication:
For all numbers \(n\text{,}\) if \(n\) is prime then \(n\) is solitary.
Write out the beginning and end of the argument if you were to prove the statement,
- Directly
- By contrapositive
- By contradiction
You do not need to provide details for the proofs (since you do not know what solitary means). However, make sure that you provide the first few and last few lines of the proofs so that we can see that logical structure you would follow.
Solution.
- Assume that \(n\) is a prime number. \(\dots\) Therefore \(n\) is solitary.
- Assume that \(n\) is not solitary. \(\dots\) Therefore \(n\) is a prime number by contraposition.
- Assume that \(n\) is a prime number and is not solitary. \(\dots\) This contradicts our assumption. Thus if \(n\) is a prime number, \(n\) is solitary.
5.
For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Pretend bonus points for filling in the middle.
- There are no integers \(x\) and \(y\) such that \(x\) is a prime greater than 5 and \(x = 6y + 3\text{.}\)
- For all integers \(n\text{,}\) if \(n\) is a multiple of 3, then \(n\) can be written as the sum of consecutive integers.
- For all integers \(a\) and \(b\text{,}\) if \(a^2 + b^2\) is odd, then \(a\) or \(b\) is odd.
Solution.
- Proof by contradiction. Start of proof: Assume, for the sake of contradiction, that there are integers \(x\) and \(y\) such that \(x\) is a prime greater than 5 and \(x = 6y + 3\text{.}\) End of proof: … this is a contradiction, so there are no such integers.
- Direct proof. Start of proof: Let \(n\) be an integer. Assume \(n\) is a multiple of 3. End of proof: Therefore \(n\) can be written as the sum of consecutive integers.
- Proof by contrapositive. Start of proof: Let \(a\) and \(b\) be integers. Assume that \(a\) and \(b\) are even. End of proof: Therefore \(a^2 + b^2\) is even.
6.
Prove that if \(n^2\) is multiple of three, then \(n\) is a multiple of three where \(n\) is an integer.
Hint.
Solution.
If a number isn’t a multiple of three, then it’s either 1 more than a multiple of three or 2 more than a multiple of three, that is, you’ll have two cases, either \(n=3k+1\) or \(3k+2\text{.}\)
Proof.
Proof by contraposition: Assume that \(n\) is not a multiple of three. Then:
Case 1: There exists an integer \(k\) such that \(n =
3k+1\text{.}\) Consider:
\begin{align*}
n^2 \amp= (3k+1)^2 \\
\amp= 9k^2 + 6k + 1\\
\amp= 3(3k^2 + 2k) + 1
\end{align*}
Hence \(n^2\) is not a multiple of three.
Case 1: There exists an integer \(l\) such that \(n =
3l+2\text{.}\) Consider:
\begin{align*}
n^2 \amp= (3l+2)^2 \\
\amp= 9l^2 + 12l + 4\\
\amp= 9l^2 + 12l + 3 + 1\\
\amp= 3(3l^2 + 4l + 1) + 1
\end{align*}
Hence \(n^2\) is not a multiple of three.
Thus, we have proven that if \(n^2\) is a multiple of three, then \(n\) is a multiple of three by contraposition.
7.
Prove that \(\sqrt 3\) is irrational.
Solution.
Proof.
Suppose \(\sqrt{3}\) were rational. Then \(\sqrt{3} = \frac{a}{b}\) for some integers \(a\) and \(b \ne 0\text{.}\) Without loss of generality, assume \(\frac{a}{b}\) is reduced. Now
\begin{equation*}
3 = \frac{a^2}{b^2}
\end{equation*}
\begin{equation*}
3b^2 = a^2
\end{equation*}
So \(a^2\) is a multiple of 3. This can only happen if \(a\) is a multiple of 3, so \(a = 3k\) for some integer \(k\text{.}\) Then we have
\begin{equation*}
3b^2 = 9k^2
\end{equation*}
\begin{equation*}
b^2 = 3k^2
\end{equation*}
So \(b^2\) is a multiple of 3, making \(b\) a multiple of 3 as well. But this contradicts our assumption that \(\frac{a}{b}\) is in lowest terms.
Therefore, \(\sqrt{3}\) is irrational.
8.
Consider the statement: for all integers \(a\) and \(b\text{,}\) if \(a\) is even and \(b\) is a multiple of 3, then \(ab\) is a multiple of 6.
- Prove the statement. What sort of proof are you using?
- State the converse. Is it true? Prove or disprove.
Solution.
Proof.
(this is a direct proof): Assume that \(a\) is even \(b\) is a multiple of three. Then there exist integers \(k\) and \(l\) such that \(a=2k\) and \(b=3l\text{.}\) Then \(ab = (2k)(3l) = 6kl\text{.}\) Thus \(ab\) is a multiple of six.-
The converse is “If \(ab\) is a multiple of six, then \(a\) is even and \(b\) is a multiple of three.”This is false. For example, \(ab = 6\) where \(a = 6\) and \(b=1\text{.}\)
9.
Prove the statement: For all integers \(n\text{,}\) if \(5n\) is odd, then \(n\) is odd. Clearly state the style of proof you are using.
Solution.
We will prove the contrapositive: if \(n\) is even, then \(5n\) is even.
Proof.
Let \(n\) be an arbitrary integer, and suppose \(n\) is even. Then \(n = 2k\) for some integer \(k\text{.}\) Thus \(5n = 5\cdot 2k = 10k = 2(5k)\text{.}\) Since \(5k\) is an integer, we see that \(5n\) must be even. This completes the proof.
10.
Prove: \(x=y\) if and only if \(xy=\dfrac{(x+y)^2}{4}\text{.}\) Note, you will need to prove two “directions” here: the “if” and the “only if” part.
Solution.
Proof.
“\(\to\)” Assume that \(x = y\text{,}\) and consider:
\begin{align*}
\dfrac{(x+y)^2}{4} \amp= \dfrac{(x+x)^2}{4} \\
\amp= \dfrac{(2x)^2}{4} \\
\amp= x^2 \\
\amp= xy
\end{align*}
This shows that if \(x=y\) then \(xy=\dfrac{(x+y)^2}{4}\text{.}\)
“\(\leftarrow\)” Assume that \(\dfrac{(x+y)^2}{4} = xy\) Then:
\begin{align*}
\dfrac{(x+y)^2}{4} \amp= xy \\
(x+y)^2 \amp= 4xy \\
x^2 + 2xy + y^2 \amp= 4xy \\
x^2 - 2xy + y^2 \amp= 0 \\
(x-y)^2 \amp= 0 \\
x \amp = y
\end{align*}
This shows that if \(xy=\dfrac{(x+y)^2}{4}\text{,}\) then \(x=y\text{.}\)
11.
Prove that \(\log(7)\) is irrational.
Solution.
We give a proof by contradiction.
Proof.
Suppose, contrary to stipulation that \(\log(7)\) is rational. Then \(\log(7) = \frac{a}{b}\) with \(a\) and \(b \ne 0\) integers. By properties of logarithms, this implies
\begin{equation*}
7 = 10^{\frac{a}{b}}
\end{equation*}
Equivalently,
\begin{equation*}
7^b = 10^a
\end{equation*}
But this is impossible as any power of 7 will be odd while any power of 10 will be even. Therefore, \(\log(7)\) is irrational.
12.
Let’s say you are presented with a conditional statement \(p \to q\) that you want to prove by contradiction. This exercise has you structure a model for contradiction of conditional statements like we saw in the model.
- What is your assumption?
- What is your conclusion?
Solution.
- Assume, to the contrary that \(p\to q\) is false, that is, we assume that \(\neg p\to q\) or \(p \land \neg q\text{.}\)
- Therefore, \(p\to q\) is true by contradiction.
13.
Prove that for all integers \(a\text{,}\) \(b\text{,}\) and \(c\text{,}\) if \(a^2 + b^2 = c^2\text{,}\) then \(a\) or \(b\) is even.
Hint.
Solution.
Try a proof by contradiction.
The negation of the statement is \(a^2 + b^2 = c^2\) and both \(a\) and \(b\) are odd.
Proof.
Assume that \(a\) and \(b\) are both odd and that \(a^2 +b^2 = c^2\text{.}\) Then there exist integers \(k\) and \(l\) such that \(a=2k+1\) and \(b=2k+1\text{.}\)
First, we observe that
\begin{align*}
a^2 + b^2 \amp= (2k+1)^2 + (2l+1)^2 \\
\amp = 4k^2 + 4k + 1 + 4l^2 + 4l + 1 \\
\amp = 4k^2 + 4k + 4l^2 + 4l + 2
\end{align*}
so that \(c^2\) and hence \(c\) is even. Let \(c=2m\) where \(m\) is some integer. Then:
\begin{align*}
c^2 \amp = a^2 + b^2 \\
(2k)^2 \amp = 4k^2 + 4k + 4l^2 + 4l + 2 \\
4k^2 \amp = 4(k^2 + k + l^2 + l) + 2
\end{align*}
This is a contradiction as we have a multiple of four being equal to something which is not a multiple of four. Thus, our original assumption was incorrect and therefore if \(a^2 + b^2 = c^2\text{,}\) we conclude that one of \(a\) or \(b\) is even.
14.
Prove that there are no integer solutions to the equation \(x^2 = 4y + 3\text{.}\)
Solution.
Proof.
Assume, to the contrary, that there is an integer solution, \((a, b)\text{,}\) to the equation \(x^2 = 4y + 3\) We’ll split this into four cases:
Since we’ve exhausted every possible combination of integer solutions, we conclude that there is no integer solution to the equation \(x^2 = 4y+3\text{.}\)
Case 1: \(x\) is odd and \(y\) is even. Then there exist integers \(k\) and \(l\) such that \(x=2k+1\) and \(y = 2l\text{.}\) Plugging this into the equation, we have:
\begin{align*}
x^2 \amp= 4y +3 \\
(2k+1)^2 \amp= 4(2l) +3 \\
4k^2 + 4k + 1 \amp= 8l +3 \\
4k^2 + 4k - 8l \amp= 2\\
4(k^2 + k - 2l) \amp= 2
\end{align*}
This is not possible, as 2 is not a multiple of 4.
Case 2: \(x\) is even and \(y\) is odd. Then there exist integers \(k\) and \(l\) such that \(x=2k\) and \(y = 2l+1\text{.}\) Plugging this into the equation, we have:
\begin{align*}
x^2 \amp= 4y +3 \\
(2k)^2 \amp= 4(2l+1) +3 \\
4k^2 \amp= 8l +4 +3 \\
4k^2 - 8l \amp= 7\\
4(k^2 - 2l) \amp= 7
\end{align*}
This is not possible, as 7 is not a multiple of 4.
Case 3: \(x\) and \(y\) are both even. Then there exist integers \(k\) and \(l\) such that \(x=2k\) and \(y = 2l\text{.}\) Plugging this into the equation, we have:
\begin{align*}
x^2 \amp= 4y +3 \\
(2k)^2 \amp= 4(2l) +3 \\
4k^2 \amp= 8l +3 \\
4k^2 - 8l \amp= 3\\
4(k^2 - 2l) \amp= 3
\end{align*}
This is not possible, as 3 is not a multiple of 4.
Case 4: \(x\) and \(y\) are both odd. Then there exist integers \(k\) and \(l\) such that \(x=2k\) and \(y = 2l\text{.}\) Plugging this into the equation, we have:
\begin{align*}
x^2 \amp= 4y +3 \\
(2k+1)^2 \amp= 4(2l+1) +3 \\
4k^2 +4k + 1\amp= 8l + 4 +3 \\
4k^2 +4k - 8l \amp= 6\\
4(k^2 +k - 2l) \amp= 6
\end{align*}
This is also not possible, as 6 is not a multiple of 4.
