3.2. Mathematical Proof#
Understandably, mathematicians are very picky about getting their proofs right. It’s how they construct their world. Students sometimes object that mathematicians are too picky about proving things that are ‘obvious’. But the fact that something is obvious in the real world counts for very little in the constructed world of mathematics. Too many obvious things have turned out to be dead wrong. (For that matter, even things in the real world that seem ‘obviously’ true are not necessarily true at all.)
Example
For example, consider the quantity \(f(n) = n^2 + n + 41\). When \(n=0\), \(f(n)=41\) which is prime; when \(n=1\), \(f(n) = 43\) which is prime; when \(n=2\), \(f(n) = 47\), which is prime. By the time you had calculated \(f(3), f(4), ... , f(10)\) and found that they were all prime, you might conclude that it is ‘obvious’ that \(f(n)\) is prime for all \(n\geq 0\). But this is not in fact the case! (See exercises.)
As we saw in Section 2.5, a formal proof consists of a sequence of statements where each statement is either an assumption or follows by a rule of logic from previous statements. The examples in that section all worked with unspecified generic propositions (\(p\), \(q\), etc). Let us now look at how one might use the same techniques to prove a specific proposition about the mathematical world. We will prove that for all integers \(n\), if \(n\) is even then \(n^2\) is even. (Definition: an integer \(n\) is even iff \(n=2k\) for some integer \(k\). For example, 2 is even since \(2=2\cdot 1\); 66 is even since \(66=2\cdot 33\); 0 is even since \(0=2\cdot 0\).)
Proof. This is a proposition of the form \(\forall n (P(n) \rightarrow Q(n))\) where \(P(n)\) is ‘’\(n\) is even’’ and \(Q(n)\) is ‘’\(n^2\) is even.’’ We need to show that \(P(n) \rightarrow Q(n)\) is true for all values of \(n\). Or alternatively we can phrase it as: \(\forall n(E(n) \to E(n^2))\) where \(E(x)\) is ‘\(x\) is even’.
In the language of Section 2.5, we need to show that for any \(n\), \(E(n)\) logically implies \(E(n^2)\); or, equivalently, that \(E(n^2)\) can be logically deduced from \(E(n)\); or, equivalently, that
\(n\) is even |
\(\therefore\) \(n^2\) is even |
is a valid argument.
Here is a formal proof that
\(n\) is even |
\(\therefore\) \(n^2\) is even |
is in fact a valid argument for any value of \(n\):
Let \(n\) be an arbitrary integer.
1. |
\(n\) is even |
premise |
2. |
if \(n\) is even, then \(n=2k\) |
|
for some integer \(k\) |
definition of even |
|
3. |
\(n=2k\) for some integer \(k\) |
from 1, 2 (modus ponens) |
4. |
if \(n=2k\) for some integer \(k\), |
|
then \(n^2=4k^2\) for that integer \(k\) |
basic algebra |
|
5. |
\(n^2 = 4k^2\) for some integer \(k\) |
from 3, 4 (modus ponens) |
6. |
if \(n^2=4k^2\) for some integer \(k\), |
|
then \(n^2=2(2k^2)\) for that \(k\) |
basic algebra |
|
7. |
\(n^2=2(2k^2)\) for some integer \(k\) |
from 5, 6 (modus ponens) |
8. |
if \(n^2 = 2(2k^2)\) for some integer \(k\), |
|
then \(n^2 = 2k'\) for some integer \(k'\) |
basic fact about integers |
|
9. |
\(n^2 = 2k'\) for some integer \(k'\) |
from 7, 8 (modus ponens) |
10. |
if \(n^2 = 2k'\) for some integer \(k'\), |
|
then \(n^2\) is even |
definition of even |
|
11. |
\(n^2\) is even |
from 9, 10 (modus ponens) |
(The ‘’basic fact about integers’’ referred to above is that the product of integers is again an integer.) Since \(n\) could be replaced by any integer throughout this argument, we have proved the statement ‘’if \(n\) is even then \(n^2\) is even’’ is true for all integers \(n\). (You might worry that the argument is only valid for even \(n\); see the disclaimer about Feyenoord’s football ability on this section, or remind yourself that \(P(n) \rightarrow Q(n)\) is automatically true if \(P(n)\) is false.)
Mathematical proofs are rarely presented with this degree of detail and formality. A slightly less formal proof of our proposition might leave out the explicit implications and instances of modus ponens and appear as follows:
Proof. Let \(n\) be an arbitrary integer.
1. |
\(n\) is even |
premise |
2. |
\(n=2k\) for some integer \(k\) |
definition of even |
3. |
\(n^2=4k^2\) for that integer \(k\) |
basic algebra |
4. |
\(n^2=2(2k^2)\) for that \(k\) |
basic algebra |
5. |
\(n^2 = 2k'\) for some integer \(k'\) |
substituting \(k'=2k^2\) |
6. |
\(n^2\) is even |
definition of even |
Since \(n\) was an arbitrary integer, the statement is true for all integers.
A more typical proof would take the argument above and present it in prose rather than list form:
Proof. Let \(n\) be an arbitrary integer and assume \(n\) is even. Then \(n=2k\) for some integer \(k\) by the definition of even, and \(n^2=4k^2=2(2k^2)\). Since the product of integers is an integer, we have \(n^2=2k'\) for some integer \(k'\). Therefore \(n^2\) is even. Since \(n\) was an arbitrary integer, the statement is true for all integers.
Typically, in a ‘formal’ proof, it is this kind of (relatively) informal discussion that is given, with enough details to convince the reader that a complete, formal proof could be constructed. Of course, how many details the reader can be expected to fill in depends on the reader, and reading proofs is a skill that must be developed and practiced.
Warning
In the course Reasoning & Logic you are learning to write proper formal proofs, and as a part of that we also need to evaluate your performance. To this end we ask you to write proofs similar to the second example given above (the list form rather than the prose form) as this shows more clearly that you are aware of the formalisms required in a proof.
Writing a proof is even more difficult than reading a proof. Every proof involves a creative act of discovery, in which a chain of logic that leads from assumptions to conclusion is discovered. It also involves a creative act of expression, in which that logic is presented in a clear and convincing way. There is no algorithm for producing correct, coherent proofs. There are, however, some general guidelines for discovering and writing proofs. Let’s look at some of these next.
3.2.1. How to write a proof#
One of the most important pieces of advice to keep in mind is: ‘’Use the definition’’. In the world of mathematics, terms mean exactly what they are defined to mean and nothing more. Definitions allow very complex ideas to be summarized as single terms. When you are trying to prove things about those terms, you generally need to ‘unwind’ the definitions. In our example above, we used the definition of even to write \(n=2k\), and then we worked with that equation. When you are trying to prove something about equivalence relations in Section 4, you can be pretty sure that you will need to use the fact that equivalence relations, by definition, are symmetric, reflexive, and transitive. (And, of course, you’ll need to know how the term ‘relation’ is defined in the first place! We mean something quite different than the idea that ‘relations’ are something like your aunt and uncle.)
More advice along the same line is to check whether you are using the assumptions of the theorem. An assumption that is made in a theorem is called an hypothesis. The hypotheses of the theorem state conditions whose truth will guarantee the conclusion of the theorem. To prove the theorem means to assume that the hypotheses are true, and to show, under that assumption, that the conclusion must be true. It’s likely (though not guaranteed) that you will need to use the hypotheses explicitly at some point in the proof, as we did in our example above.[1] Also, you should keep in mind that any result that has already been proved is available to be used in your proof.
A proof is a logical argument, based on the rules of logic. Since there are really not all that many basic rules of logic, the same patterns keep showing up over and over. Let’s look at some of the patterns.
The most common pattern arises in the attempt to prove that something is true ‘for all’ or ‘for every’ or ‘for any’ entity in a given category. In terms of logic, the statement you are trying to prove is of the form \(\forall x\,P(x)\). In this case, the most likely way to begin the proof is by saying something like, ‘’Let \(x\) be an arbitrary entity in the domain of discourse. We want to show that \(P(x)\).’’ We call this a proof by generalisation. In the rest of the proof, \(x\) refers to some unspecified but definite entity in the domain of discourse. Since \(x\) is arbitrary, proving \(P(x)\) amounts to proving \(\forall x\,P(x)\). You only have to be careful that you don’t use any facts about \(x\) beyond what you have assumed. For example, in our proof above, we cannot make any assumptions about the integer \(n\) except that it is even; if we for instance also assume \(x=6\) or that \(x\) is divisible by \(3\), then the proof would have been incorrect, or at least incomplete.
Sometimes, you have to prove that an entity exists that satisfies
certain stated properties. Such a proof is called an
existence proof. In this case, you are attempting to
prove a statement of the form \(\exists x\,P(x)\). The way to
do this is to find an example, that is, to find a specific
entity \(a\) for which \(P(a)\) is true. One way to prove
the statement ‘’There is an even prime number’’ is to find
a specific number that satisfies this description.
The same statement could also
be expressed ‘’Not every prime number is odd.’’ This statement
has the form \(\lnot(\forall x\,P(x))\), which is equivalent
to the statement \(\exists x\,(\lnot P(x))\).
An example that proves the statement \(\exists x\,(\lnot P(x))\)
also proves \(\lnot(\forall x\,P(x))\). Such an example is
called a counterexample to the statement \(\forall x\,P(x)\):
A counterexample proves that the statement \(\forall x\,P(x)\) is false.
The number 2 is a counterexample to the statement ‘’All prime numbers
are odd.’’ In fact, 2 is the only counterexample to this
statement; by contrast, many statements have multiple counterexamples.
Note that we have now discussed how to prove and disprove universally quantified statements, and how to prove existentially quantified statements. How do you disprove \(\exists x\,P(x)\)? Recall that \(\lnot \exists x\,P(x)\) is logically equivalent to \(\forall x\,(\lnot P(x))\), so to disprove \(\exists x\,P(x)\) you need to prove \(\forall x\,(\lnot P(x))\).
Many statements, like that in our example above, have the logical form of an implication, \(p\rightarrow q\). (More accurately, they are of the form ‘’\(\forall x\, (P(x) \rightarrow Q(x))\)”, but as discussed above the strategy for proving such a statement is to prove \(P(x) \rightarrow Q(x)\) for an arbitrary element \(x\) of the domain of discourse.) The statement might be ‘’For all natural numbers \(n\), if \(n\) is even then \(n^2\) is even,’’ or ‘’For all strings \(x\), if \(x\) is in the language \(L\) then \(x\) is generated by the grammar \(G\),’’[2] or ‘’For all elements \(s\), if \(s \in A\) then \(s \in B\).’’ Sometimes the implication is implicit rather than explicit: for example, ‘’The sum of two rationals is rational’’ is really short for ‘’For any numbers \(x\) and \(y\), if \(x\) and \(y\) are rational then \(x+y\) is rational.’’ A proof of such a statement often begins something like this: ‘’Assume that \(p\). We want to show that \(q\).’’ In the rest of the proof, \(p\) is treated as an assumption that is known to be true. As discussed above, the logical reasoning behind this is that you are essentially proving that
\(p\) |
\(\therefore\) \(q\) |
is a valid argument. Another way of thinking about it is to remember that \(p\rightarrow q\) is automatically true in the case where \(p\) is false, so there is no need to handle that case explicitly. In the remaining case, when \(p\) is true, we can show that \(p\rightarrow q\) is true by showing that the truth of \(q\) follows from the truth of \(p\). So remember that proving an implication you should assume the antecedent and prove the consequent (you can refresh your memory of what those words mean on this section).
A statement of the form \(p\wedge q\) can be proven by proving \(p\) and \(q\) separately. A statement of the form \(p\vee q\) can be proved by proving the logically equivalent statement \((\lnot p)\rightarrow q\): to prove \(p\vee q\), you can assume that \(p\) is false and prove, under that assumption, that \(q\) is true. For example, the statement ‘’Every integer is even or odd’’ is equivalent to the statement ‘’Every integer that is not even is odd’’.
Since \(p\leftrightarrow q\) is equivalent to \((p\rightarrow q)\wedge(q\rightarrow p)\), a statement of the form \(p\leftrightarrow q\) is often proved by giving two proofs, one of \(p\rightarrow q\) and one of \(q\rightarrow p\). In English, \(p\leftrightarrow q\) can be stated in several forms such as ‘’\(p\) if and only if \(q\)’’, ‘’if \(p\) then \(q\) and conversely,’’ and ‘’\(p\) is necessary and sufficient for \(q\)’’. The phrase ‘if and only if’ is so common in mathematics that it is often abbreviated iff.
You should also keep in mind that you can prove \(p\rightarrow q\) by displaying a chain of valid implications \(p\rightarrow r\rightarrow s\rightarrow \cdots\rightarrow q\). Similarly, \(p\leftrightarrow q\) can be proved with a chain of valid biconditionals \(p\leftrightarrow r\leftrightarrow s\leftrightarrow \cdots\leftrightarrow q\).
3.2.2. Some terminology#
Before we look at some sample proofs, here is some terminology that we will use throughout our sample proofs and the rest of the course of Reasoning & Logic.
The natural numbers (denoted \(\mathbb{N}\)) are the numbers \(0,1,2,... \). Note that the sum and product of natural numbers are natural numbers.
The integers (denoted \(\mathbb{Z}\)) are the numbers \(0, -1, 1, -2, 2, -3, 3, ... \). Note that the sum, product, and difference of integers are integers.
The rational numbers (denoted \(\mathbb{Q}\)) are all numbers that can be written in the form \(\frac{m}{n}\) where \(m\) and \(n\) are integers and \(n\not=0\). So \(\frac{1}{3}\) and \(\frac{-65}{7}\) are rationals; so, less obviously, are 6 and \(\frac{\sqrt{27}}{\sqrt{12}}\) since \(6=\frac{6}{1}\) (or, for that matter, \(6=\frac{-12}{-2}\)), and \(\frac{\sqrt{27}}{\sqrt{12}} = \sqrt{\frac{27}{12}} = \sqrt{\frac{9}{4}} = \frac{3}{2}\). Note the restriction that the number in the denominator cannot be 0: \(\frac{3}{0}\) is not a number at all, rational or otherwise; it is an undefined quantity. Note also that the sum, product, difference, and quotient of rational numbers are rational numbers (provided you don’t attempt to divide by 0).
The real numbers (denoted \(\mathbb{R}\)) are numbers that can be written in decimal form, possibly with an infinite number of digits after the decimal point. Note that the sum, product, difference, and quotient of real numbers are real numbers (provided you don’t attempt to divide by 0).
The irrational numbers are real numbers that are not rational, i.e., that cannot be written as a ratio of integers. Such numbers include \(\sqrt{3}\) (which we will prove is not rational) and \(\pi\) (if anyone ever told you that \(\pi = \frac{22}{7}\), remember that \(\frac{22}{7}\) is only an approximation of the value of \(\pi\)). Later you will learn that we can describe this set of irrational numbers as \(\mathbb{R} - \mathbb{Q}\), that is: it is all the numbers that are in \(\mathbb{R}\) but are not in \(\mathbb{Q}\).
An integer \(n\) is divisible by \(m\) iff \(n=mk\) for some integer \(k\). This can also be expressed by saying that \(m\) evenly divides \(n\), which has the mathematical notation \(m \mid n\). So for example, \(2 \mid 8\), but \(8 \nmid 2\). \(2 \mid n\) iff \(n=2k\) for some integer \(k\); \(n\) is divisible by 3 iff \(n=3k\) for some integer \(k\), and so on. Note that if \(2 \nmid n\) (i.e., \(n\) is not divisible by 2), then \(n\) must be 1 more than a multiple of 2 so \(n=2k+1\) for some integer \(k\). Similarly, if \(n\) is not divisible by 3 then \(n\) must be 1 or 2 more than a multiple of 3, so \(n=3k+1\) or \(n=3k+2\) for some integer \(k\).
An integer is even iff it is divisible by 2 and odd iff it is not.
An integer \(n>1\) is prime if it is divisible by exactly two positive integers, namely 1 and itself. Note that a number must be greater than 1 to even have a chance of being termed ‘prime’. In particular, neither 0 nor 1 is prime.
3.2.3. Examples#
Let’s look now at another example of a proof. We set out to prove that the sum of any two rational numbers is rational.
Proof. We start by assuming that \(x\) and \(y\) are arbitrary rational numbers. Here’s a formal proof that the inference rule
\(x\) is rational |
\(y\) is rational |
\(\therefore\) \(x+y\) is rational |
is a valid rule of inference:
1. |
\(x\) is rational |
premise |
2. |
if \(x\) is rational, then \(x=\frac{a}{b}\) |
|
for some integers \(a\) and \(b\not=0\) |
definition of rationals |
|
3. |
\(x=\frac{a}{b}\) for some integers \(a\) and \(b\not=0\) |
from 1,2 (modus ponens) |
4. |
\(y\) is rational |
premise |
5. |
if \(y\) is rational, then \(y=\frac{c}{d}\) for |
|
some integers \(c\) and \(d\not=0\) |
definition of rational |
|
6. |
\(y=\frac{c}{d}\) for some \(c\) and \(d\not=0\) |
from 4,5 (modus ponens) |
7. |
\(x=\frac{a}{b}\) for some \(a\) and \(b\not=0\) and |
|
\(y=\frac{c}{d}\) for some \(c\) and \(d\not=0\) |
from 3,6 |
|
8. |
if \(x=\frac{a}{b}\) for some \(a\) and \(b\not=0\) and |
|
\(y=\frac{c}{d}\) for \(c\) and \(d\not=0\) then |
||
\(x+y = \frac{ad+bc}{bd}\)where \(a,b,c,d\) |
||
are integers and \(b,d \not=0\) |
basic algebra |
|
9. |
\(x+y = \frac{ad+bc}{bd}\) for some \(a,b,c,d\) |
|
where \(b,d \not=0\) |
from 7,8 (modus ponens) |
|
10. |
if \(x+y = \frac{ad+bc}{bd}\) for some \(a,b,c,d\) |
|
where \(b,d \not=0\) then \(x+y = \frac{m}{n}\) |
||
where \(m,n\) are integers and \(n\not= 0\) |
properties of integers |
|
11. |
\(x+y = \frac{m}{n}\) where \(m\) and \(n\) |
|
are integers and \(n\not= 0\) |
from 9,10 (modus ponens) |
|
12. |
if \(x+y = \frac{m}{n}\) where \(m\) and \(n\) are |
|
integers and \(n\not= 0\) |
||
then \(x+y\) is rational |
definition of rational |
|
13. |
\(x+y\) is rational |
from 11,12 (modus ponens) |
So the rule of inference given above is valid. Since \(x\) and \(y\) are arbitrary rationals, we have proved that the rule is valid for all rationals, and hence the sum of any two rationals is rational.
Again, a more informal presentation that we expect from you during the course would look like:
Proof. Proof by generalisation:
Let \(x\) and \(y\) be arbitrary rational numbers.
By the definition of rational, there are integers \(a,b\not=0,c,d\not=0\) such that \(x=\frac{a}{b}\) and \(y=\frac{c}{d}\).
Then \(x+y = \frac{ad+bc}{bd}\);
We know \(ad+bc\) and \(bd\) are integers since the sum and product of integers are integers, and we also know \(bd\not=0\) since neither \(b\) nor \(d\) is 0.
So we have written \(x+y\) as the ratio of two integers, the denominator being non-zero.
Therefore, by the definition of rational numbers, \(x+y\) is rational.
Since \(x\) and \(y\) were arbitrary rationals, the sum of any two rationals is rational.
And one more example: we will prove that any 4-digit number \(d_1d_2d_3d_4\) is divisible by 3 iff the sum of the four digits is divisible by 3.
Proof. This statement is of the form \(p \leftrightarrow q\); recall that \(p \leftrightarrow q\) is logically equivalent to \((p\rightarrow q) \wedge (q \rightarrow p)\). So we need to prove for any 4-digit number \(d_1d_2d_3d_4\) that (1) if \(d_1d_2d_3d_4\) is divisible by 3 then \(d_1+d_2+d_3+d_4\) is divisible by 3, and (2) if \(d_1+d_2+d_3+d_4\) is divisible by 3 then \(d_1d_2d_3d_4\) is divisible by 3. So let \(d_1d_2d_3d_4\) be an arbitrary 4-digit number.
(1) Assume \(d_1d_2d_3d_4\) is divisible by 3, i.e., \(d_1d_2d_3d_4=3k\) for some integer \(k\). The number \(d_1d_2d_3d_4\) is actually \(d_1 \times 1000 + d_2 \times 100 + d_3 \times 10 + d_4\), so we have the equation
Since \(1000=999+1\), \(100=99+1\), and \(10=9+1\), this equation can be rewritten
Rearranging gives
We can now factor a 3 from the right side to get
Since \((k - 333d_1 - 33d_2 - d_3)\) is an integer, we have shown that \(d_1 + d_2 +d_3 +d_4\) is divisible by 3.
(2) Assume \(d_1 + d_2 +d_3 +d_4\) is divisible by 3. Consider the number \(d_1d_2d_3d_4\). As remarked above,
so
We assumed that \(d_1 + d_2 +d_3 +d_4 = 3k\) for some integer \(k\), so we can substitute into the last equation to get
Since the quantity in parentheses is an integer, we have proved that \(d_1d_2d_3d_4\) is divisible by 3.
In (1) and (2) above, the number \(d_1d_2d_3d_4\) was an arbitrary 4-digit integer, so we have proved that for all 4-digit integers, \(d_1d_2d_3d_4\) is divisible by 3 iff the sum of the four digits is divisible by 3.
Now suppose we wanted to prove the statement ‘’For all integers \(n\), \(n^2\) is even if and only if \(n\) is even.’’ We have already proved half of this statement (‘’For all integers \(n\), if \(n\) is even then \(n^2\) is even’’), so all we need to do is prove the statement ‘’For all integers \(n\), if \(n^2\) is even then \(n\) is even’’ and we’ll be done. Unfortunately, this is not as straightforward as it seems: suppose we started in our standard manner and let \(n\) be an arbitrary integer and assumed that \(n^2=2k\) for some integer \(k\). Then we’d be stuck! Taking the square root of both sides would give us \(n\) on the left but would leave a \(\sqrt{2k}\) on the right. This quantity is not of the form \(2k'\) for any integer \(k'\); multiplying it by \(\frac{\sqrt{2}}{\sqrt{2}}\) would give \(2\frac{\sqrt{k}} {\sqrt{2}}\) but there is no way for us to prove that \(\frac{\sqrt{k}} {\sqrt{2}}\) is an integer. So we’ve hit a dead end. What do we do now?
The answer is that we need a different proof technique. The proofs we have written so far are what are called direct proofs: to prove \(p \rightarrow q\) you assume \(p\) is true and prove that the truth of \(q\) follows. Sometimes, when a direct proof of \(p \rightarrow q\) fails, an indirect proof will work. Recall that the contrapositive of the implication \(p \rightarrow q\) is the implication \(\lnot q \rightarrow \lnot p\), and that this proposition is logically equivalent to \(p \rightarrow q\). An indirect proof of \(p \rightarrow q\), then, is a direct proof of the contrapositive \(\lnot q \rightarrow \lnot p\). In our current example, instead of proving ‘’if \(n^2\) is even then \(n\) is even” directly, we can prove its contrapositive ‘’if \(n\) is not even (i.e., \(n\) is odd) then \(n^2\) is not even (i.e., \(n^2\) is odd)’’. We call this method a proof by contrapositive. The proof of this contrapositive is a routine direct argument which we leave to the exercises.
Alternatively we sometimes need a proof by division into cases. Consider for instance that we want to prove that \(3 \mid (n^3+3n^2+2n)\) for all integers \(n\). What we can do is split our proof into three different case based on the divisibility by \(3\). Recall from the definition of divisibility that every number can be written as either \(n = 3k\), \(n=3k+1\), or \(n=3k+2\). In a proof by division into cases, we prove that the claim holds for all of these cases and thereby prove the claim holds for all numbers.
Video
We have also created a pencast about several of the different proof techniques outlined in this chapter. This includes one in which we prove that \(3 \mid (n^3+3n^2+2n)\) using a proof by division into cases, found here: youtu.be/4OHyyGY_WpI
3.2.4. Exercises#
Exercise (1)
Find a natural number \(n\) for which \(n^2+n+41\) is not prime.
Exercise (2)
Show that the propositions \(p\vee q\) and \((\lnot p)\rightarrow q\) are logically equivalent.
Exercise (3)
Show that the proposition \((p\vee q)\rightarrow r\) is equivalent to \((p\rightarrow r)\wedge(q\rightarrow r)\).
Exercise (4)
Determine whether each of the following statements is true. If it true, prove it. If it is false, give a counterexample.
Every prime number is odd.
Every prime number greater than 2 is odd.
If \(x\) and \(y\) are integers with \(x<y\), then there is an integer \(z\) such that \(x<z<y\).
If \(x\) and \(y\) are real numbers with \(x<y\), then there is a real number \(z\) such that \(x<z<y\).
Exercise (5†)
Suppose that \(r\), \(s\), and \(t\) are integers, such that \(r\) evenly divides \(s\) and \(s\) evenly divides \(t\). Prove that \(r\) evenly divides \(t\).
Exercise (6)
Prove that for all integers \(n\), if \(n\) is odd then \(n^2\) is odd.
Exercise (7)
Prove that an integer \(n\) is divisible by 3 iff \(n^2\) is divisible by 3. (Hint: give an indirect proof of ‘’if \(n^2\) is divisible by 3 then \(n\) is divisible by 3.’’)
Exercise (8)
Prove or disprove each of the following statements. Remember that to disprove a statement we always expect a counterexample!
The product of two even integers is even.
The product of two integers is even only if both integers are even.
The product of two rational numbers is rational.
The product of two irrational numbers is irrational.
For all integers \(n\), if \(n\) is divisible by 4 then \(n^2\) is divisible by 4.
For all integers \(n\), if \(n^2\) is divisible by 4 then \(n\) is divisible by 4.