Four cards lie on a table. Each has a letter on one side and a number on the other, and the faces you can see are A, K, 4, and 7. Someone asserts a rule: if a card has a vowel on one side, then it has an even number on the other. Which cards must you turn over to find out whether the rule holds for these four cards?
Most people choose A and 4. The correct answer is A and 7, and the reason is the subject of this chapter. The rule is a conditional statement, and a conditional statement can fail in only one way. Turning over the 4 cannot reveal a failure, whatever is on the back; turning over the 7 can. Ordinary conversation tolerates a loose reading of “if”, “or”, “every”, and “some”. Mathematics does not, because a proof is a chain in which each link must hold for a stated reason, and the reasons are the precise meanings of exactly those words. This chapter fixes the meanings, shows how to negate any statement built from them, and then puts them to work in the basic forms of proof.
1.1 Statements and connectives
Definition 1.1 (statement). A statement, or proposition, is a sentence that is either true or false, and not both. Its truth value is \(T\) if it is true and \(F\) if it is false.
“Seven is a prime number” is a true statement and “every integer is even” is a false one. “Is seven prime?” and “add two to both sides” are not statements. The sentence “\(n\) is even” is not a statement either until \(n\) is given a value; sentences with free variables are treated in Section 1.4. A statement need not have a known truth value: “every even integer greater than \(2\) is a sum of two primes” is a statement, although nobody knows whether it is true.
Compound statements are built from simpler ones with five connectives, whose meanings are fixed by a table.
Definition 1.2 (connectives). For statements \(P\) and \(Q\) , the negation \(\neg P\) (“not \(P\) ”), the conjunction \(P\land Q\) ("\(P\) and \(Q\) "), the disjunction \(P\lor Q\) ("\(P\) or \(Q\) "), the conditional \(P\to Q\) (“if \(P\) then \(Q\) ”), and the biconditional \(P\leftrightarrow Q\) ("\(P\) if and only if \(Q\) ") are the statements whose truth values are determined by those of \(P\) and \(Q\) as follows.
| \(P\) | \(Q\) | \(\neg P\) | \(P\land Q\) | \(P\lor Q\) | \(P\to Q\) | \(P\leftrightarrow Q\) |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Three rows of this table deserve comment. First, “or” is inclusive: \(P\lor Q\) is true when both parts are true. A menu that offers soup or salad means one of them; a mathematician who says that \(n\) is even or \(n\) is a multiple of three is not excluding six. Second, the conditional \(P\to Q\) is false in exactly one row, the row in which the hypothesis \(P\) is true and the conclusion \(Q\) is false. Third, and as a consequence, a conditional with a false hypothesis is true no matter what its conclusion says. Such a conditional is called vacuously true.
Vacuous truth feels strange at first, and a promise is the best way to see that it is right. Suppose a teacher says: if you score full marks on the final, you will receive the top grade. The promise is broken in one situation only, when a student scores full marks and does not receive the top grade. A student who scores less and receives the top grade anyway has not been lied to, and neither has a student who scores less and receives a lower grade. The promise says nothing about those students, and a promise that says nothing about you has not been broken.
The conditional has many English renderings, all with the same table: “\(P\) implies \(Q\) ”, “\(Q\) if \(P\) ”, “\(P\) only if \(Q\) ”, “\(P\) is sufficient for \(Q\) ”, and “\(Q\) is necessary for \(P\) ”. The phrase “only if” is the one most often misread. “You pass only if you sit the exam” says that passing forces having sat the exam; it is the conditional from passing to sitting, not the other way round.
Example 1.1: The four cards
For a single card let \(P\) be “the letter side shows a vowel” and \(Q\) be “the number side shows an even number”. The rule asserts \(P\to Q\) for each card, and by the table a card violates the rule exactly when \(P\) is true and \(Q\) is false, that is, when it carries a vowel and an odd number.
Take the cards in turn. The card showing A has \(P\) true; if its hidden number is odd the rule fails, so it must be turned. The card showing K has \(P\) false, so \(P\to Q\) is true for it whatever the hidden number is; turning it teaches nothing. The card showing 4 has \(Q\) true, so \(P\to Q\) is true for it whatever the hidden letter is; turning it teaches nothing either. The card showing 7 has \(Q\) false; if its hidden letter is a vowel the rule fails, so it must be turned.
The cards to turn are A and 7, exactly two of the four. The popular wrong choice of the card showing 4 comes from reading the rule backwards, as if it said that an even number forces a vowel. That backwards statement has a name, the converse, and the next section shows that it is a different statement.
1.2 Logical equivalence
A compound statement such as \((P\to Q)\land\neg Q\) has a truth value for every assignment of truth values to its letters. With \(k\) letters there are \(2^{k}\) assignments, one for each row of a truth table, and the table is a complete description of the statement’s logical behaviour.
Definition 1.3 (tautology, contradiction, equivalence). A compound statement is a tautology if it is true in every row of its truth table and a contradiction if it is false in every row. Two compound statements \(A\) and \(B\) built from the same letters are logically equivalent, written \(A\equiv B\) , if they have the same truth value in every row; equivalently, if \(A\leftrightarrow B\) is a tautology.
Equivalent statements can be substituted for one another anywhere, and a small stock of equivalences does most of the work in practice.
Theorem 1.4 (basic equivalences). For all statements \(P\) , \(Q\) , \(R\) :
Each claim is verified by writing out both sides in a truth table and comparing columns. The following table evaluates the two sides of (c), (d), and (e), and also records the column of \(Q\to P\) for later use.
| \(P\) | \(Q\) | \(P\to Q\) | \(\neg P\lor Q\) | \(\neg Q\to\neg P\) | \(\neg(P\to Q)\) | \(P\land\neg Q\) | \(Q\to P\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | F | T |
| T | F | F | F | F | T | T | T |
| F | T | T | T | T | F | F | F |
| F | F | T | T | T | F | F | T |
Proof. In the table, the third, fourth, and fifth columns agree in all four rows, which proves (c) and (d). The sixth and seventh agree, which proves (e). The remaining parts are checked the same way, with two rows for (a), four rows for (b) and (g), and eight rows for (f).
The two laws in part (b) are De Morgan’s laws. They say that negation turns “and” into “or” and “or” into “and”: to deny that both of two things hold is to assert that at least one fails.
Part (d) involves a statement with its own name. Given a conditional \(P\to Q\) , three related conditionals can be formed.
Definition 1.5 (converse, inverse, contrapositive). The converse of \(P\to Q\) is \(Q\to P\) . The inverse is \(\neg P\to\neg Q\) . The contrapositive is \(\neg Q\to\neg P\) .
Theorem 1.4(d) says that a conditional and its contrapositive are equivalent: they are the same assertion in two wordings. The last column of the table shows that a conditional and its converse are not equivalent, because the columns of \(P\to Q\) and \(Q\to P\) differ in the second and third rows. The inverse is the contrapositive of the converse, so it is equivalent to the converse and not to the original. “If it is a square then it is a rectangle” is true; its converse, “if it is a rectangle then it is a square”, is false; its contrapositive, “if it is not a rectangle then it is not a square”, is true.
Part (e) is the one to memorize, because it is used every time a conditional is to be disproved or assumed false: the negation of “if \(P\) then \(Q\) ” is not another conditional. It is the conjunction “\(P\) and not \(Q\) ”.
Example 1.2: A tautology in eight rows
Reasoning often chains conditionals: from “if \(P\) then \(Q\) ” and “if \(Q\) then \(R\) ” one concludes “if \(P\) then \(R\) ”. The claim that this is always legitimate is the claim that
is a tautology. There are three letters, so the table has \(2^{3}=8\) rows.
| \(P\) | \(Q\) | \(R\) | \(P\to Q\) | \(Q\to R\) | both | \(P\to R\) | whole statement |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
The column headed “both” is the conjunction of the two columns before it. It is true in four rows, and in each of those four rows \(P\to R\) is true as well, so the whole statement is true there. In the other four rows the hypothesis of the outer conditional is false, so the whole statement is vacuously true. The final column reads T in all eight rows: the statement is a tautology.
Notice how the outer conditional was evaluated. Only the rows where its hypothesis is true needed any inspection. That observation is the idea behind the definition of a valid argument.
1.3 Valid arguments
Definition 1.6 (valid argument form). An argument form consists of compound statements \(A_1,\dots,A_m\) , the premises, and a compound statement \(C\) , the conclusion. The form is valid if \(C\) is true in every row of the truth table in which all of \(A_1,\dots,A_m\) are true; equivalently, if \((A_1\land\dots\land A_m)\to C\) is a tautology. Otherwise it is invalid, and a row in which every premise is true and the conclusion is false is a counterexample row.
Validity is a property of the form of an argument and not of the truth of its parts. A valid argument with a false premise may have a false conclusion; an invalid argument may happen to have a true conclusion. What validity guarantees is the one thing a proof needs: if the premises are true, the conclusion is true.
Four valid forms are used constantly and have traditional names. Modus ponens: from \(P\to Q\) and \(P\) , conclude \(Q\) . Modus tollens: from \(P\to Q\) and \(\neg Q\) , conclude \(\neg P\) . Hypothetical syllogism: from \(P\to Q\) and \(Q\to R\) , conclude \(P\to R\) ; this is Example 1.2. Disjunctive syllogism: from \(P\lor Q\) and \(\neg P\) , conclude \(Q\) . Two invalid forms are common enough to have names as well. Affirming the consequent argues from \(P\to Q\) and \(Q\) to \(P\) . Denying the antecedent argues from \(P\to Q\) and \(\neg P\) to \(\neg Q\) . The first treats a conditional as its converse and the second treats it as its inverse.
Example 1.3: Testing two arguments
First argument. If it rained, the match was cancelled. The match was cancelled. Therefore it rained. With \(P\) for “it rained” and \(Q\) for “the match was cancelled”, the premises are \(P\to Q\) and \(Q\) , and the conclusion is \(P\) . Look for a row where both premises are true and the conclusion is false. The conclusion is false when \(P\) is false; with \(P\) false and \(Q\) true, the premise \(P\to Q\) is true and the premise \(Q\) is true. So the row with \(P\) false and \(Q\) true is a counterexample row, and the form is invalid. In words: the match may have been cancelled for another reason. This is affirming the consequent.
Second argument. The premises are \(P\lor Q\) , \(P\to R\) , and \(Q\to R\) , and the conclusion is \(R\) . There are eight rows. If \(R\) is false, the premises \(P\to R\) and \(Q\to R\) can both be true only if \(P\) and \(Q\) are both false, and then \(P\lor Q\) is false; so no row with \(R\) false makes all three premises true. If \(R\) is true, the second and third premises are true automatically and the first is true when at least one of \(P\) , \(Q\) is true. Hence the premises are all true in exactly three rows, namely those where \((P,Q,R)\) is \((T,T,T)\) , \((T,F,T)\) , or \((F,T,T)\) , and \(R\) is true in each. The form is valid.
The second form is the logical skeleton of proof by cases: if one of two situations must occur, and the desired conclusion follows in each, then the conclusion holds. Section 1.6 uses it.
1.4 Predicates and quantifiers
The sentence “\(n\) is even” has no truth value until \(n\) is specified. Most mathematical assertions are built from sentences of this kind.
Definition 1.7 (predicate, quantifiers). A predicate \(P(x)\) is a sentence containing a variable \(x\) that becomes a statement whenever \(x\) is replaced by an element of a specified set \(D\) , the domain. The universal statement \(\forall x\in D\ P(x)\) is true if \(P(x)\) is true for every element \(x\) of \(D\) , and false otherwise. The existential statement \(\exists x\in D\ P(x)\) is true if \(P(x)\) is true for at least one element \(x\) of \(D\) , and false otherwise. When the domain is clear it is omitted from the notation.
The domain is part of the statement. “There is an \(x\) with \(x^{2}=2\) ” is false over the rationals and true over the reals. “For all \(x\) , \(x^{2}\ge x\) ” is true over the integers and false over the reals, where \(x=\tfrac12\) fails. A universal statement over an empty domain is vacuously true, for the same reason that a conditional with a false hypothesis is true: there is no element for which it could fail.
To prove a universal statement one must give an argument that works for an arbitrary element of the domain; no number of examples is enough when the domain is infinite. To disprove it, one element for which \(P(x)\) fails is enough, and such an element is called a counterexample. For an existential statement the roles are reversed: one example, a witness, proves it, and disproving it requires an argument covering every element. These roles follow from the rules for negation.
Theorem 1.8 (negating quantifiers). For every predicate \(P(x)\) on a domain \(D\) ,
Proof. The statement \(\neg\,\forall x\,P(x)\) is true exactly when \(\forall x\,P(x)\) is false, which by Definition 1.7 happens exactly when \(P(x)\) fails to be true for some \(x\) in \(D\) , that is, when \(\neg P(x)\) is true for at least one \(x\) . That is the meaning of \(\exists x\,\neg P(x)\) . The second equivalence follows from the first applied to the predicate \(\neg P(x)\) : it gives \(\neg\,\forall x\,\neg P(x)\equiv\exists x\,P(x)\) , and negating both sides gives the claim.
When the domain is a finite set \(\{d_1,\dots,d_k\}\) , the universal statement is the conjunction \(P(d_1)\land\dots\land P(d_k)\) and the existential statement is the disjunction \(P(d_1)\lor\dots\lor P(d_k)\) , and Theorem 1.8 is De Morgan’s laws applied \(k-1\) times. The quantifier rules are De Morgan’s laws for domains of any size.
Statements with several quantifiers are read from left to right, and each variable may depend on those introduced before it. Because of this, the order of unlike quantifiers matters.
Example 1.4: Changing the order of two quantifiers
Let the domain be \(D=\{1,2,3,4\}\) and let \(R(x,y)\) be the predicate “\(x+y\) is divisible by \(4\) ”. Consider the statement \(\forall x\,\exists y\,R(x,y)\) : for every \(x\) there is some \(y\) , allowed to depend on \(x\) , with \(x+y\) divisible by \(4\) . It is true. For \(x=1,2,3,4\) take \(y=3,2,1,4\) respectively; the sums are \(4,4,4,8\) .
Now consider \(\exists y\,\forall x\,R(x,y)\) : there is one \(y\) that works for every \(x\) at once. It is false. If \(y\) is fixed, the four sums \(1+y,2+y,3+y,4+y\) are four consecutive integers, and exactly one of four consecutive integers is divisible by \(4\) , so \(R(x,y)\) holds for only one \(x\) .
Compare a second predicate on the same domain: let \(S(x,y)\) be “\(y\) divides \(x\) ”. Here \(\exists y\,\forall x\,S(x,y)\) is true with the witness \(y=1\) , since \(1\) divides everything. Then \(\forall x\,\exists y\,S(x,y)\) is true as well, with the same \(y\) serving every \(x\) .
Figure 1.1 shows why one direction always holds. If a single \(y\) works for every \(x\) , then certainly every \(x\) has some \(y\) that works: a full row puts a filled cell in every column. So \(\exists y\,\forall x\,R(x,y)\) implies \(\forall x\,\exists y\,R(x,y)\) for every predicate \(R\) . The left grid shows that the reverse implication fails.
Negating a statement with several quantifiers is mechanical: move the negation inward one quantifier at a time by Theorem 1.8, switching each quantifier as it passes, and finally negate the innermost predicate using Theorem 1.4.
Example 1.5: Negating to find out what must be proved
A universal conditional. Most theorems have the form \(\forall x\,(P(x)\to Q(x))\) . By Theorem 1.8 and then Theorem 1.4(e),
So a counterexample to “every \(P\) is a \(Q\) ” is an object that is a \(P\) and is not a \(Q\) . To refute “every prime is odd” one exhibits a prime that is not odd, namely \(2\) .
Two quantifiers. The negation of \(\forall x\,\exists y\,R(x,y)\) is obtained in two steps:
On a finite domain this can be confirmed exhaustively. A domain of three elements carries \(2^{9}=512\) different predicates \(R(x,y)\) , one for each way of marking the nine cells of a grid like those in Figure 1.1, and for every one of the \(512\) the statements \(\neg\,\forall x\,\exists y\,R(x,y)\) and \(\exists x\,\forall y\,\neg R(x,y)\) have the same truth value.
A definition with two quantifiers. Call a set \(S\) of integers bounded above if \(\exists M\in\mathbb Z\ \forall s\in S\ (s\le M)\) . To show that the set \(E\) of even integers is not bounded above we must prove the negation, which is
The negation tells us the shape of the proof: an arbitrary integer \(M\) is given, and we must produce an even integer larger than it. The integer \(s=2\lvert M\rvert+2\) is even, and \(s>\lvert M\rvert\ge M\) . Before negating, the task was a vague “show it is unbounded”; after negating, it is a definite instruction.
1.5 Direct proof
A proof of a statement is a finite sequence of statements, each of which is a hypothesis, a definition, a previously established result, or a consequence of earlier lines by a valid argument form, ending with the statement to be proved. In practice proofs are written in connected sentences, and routine logical steps are not named. What is never omitted is the reason for a step that is not routine.
Proofs need definitions to work from. The following three are used throughout the book.
Definition 1.9 (even, odd, divides). An integer \(n\) is even if \(n=2k\) for some integer \(k\) , and odd if \(n=2k+1\) for some integer \(k\) . For integers \(a\) and \(b\) , we say \(a\) divides \(b\) , and write \(a\mid b\) , if \(b=ak\) for some integer \(k\) ; then \(a\) is a divisor of \(b\) and \(b\) is a multiple of \(a\) .
We shall use without proof, until Chapter 4 supplies one, the fact that every integer is even or odd and that no integer is both. Notice that each definition contains a hidden existential quantifier: “\(n\) is even” means \(\exists k\in\mathbb Z\ (n=2k)\) . To use the hypothesis that \(n\) is even, one introduces a name for the integer whose existence is asserted: “since \(n\) is even, \(n=2k\) for some integer \(k\) ”. To prove that a number is even, one must exhibit it as twice an explicitly described integer.
A direct proof of \(\forall x\,(P(x)\to Q(x))\) takes an arbitrary \(x\) in the domain, assumes \(P(x)\) , and derives \(Q(x)\) . The assumption costs nothing: if \(P(x)\) is false the conditional is vacuously true, so only the elements satisfying \(P\) need attention.
Proposition 1.10 (sum of two odd integers). If \(m\) and \(n\) are odd integers, then \(m+n\) is even.
Proof. Let \(m\) and \(n\) be odd integers. By Definition 1.9 there are integers \(j\) and \(k\) with \(m=2j+1\) and \(n=2k+1\) . Then
Since \(j+k+1\) is an integer, \(m+n\) is twice an integer, so \(m+n\) is even.
Every sentence of that proof has a job. The first names arbitrary objects satisfying the hypothesis. The second unfolds the hypothesis by the definition, introducing two different letters because nothing says the two odd numbers are equal. The display computes. The last sentence folds the result back into the definition of the conclusion, and it says why the definition applies. Unfold, compute, fold back is the pattern of a great many direct proofs.
Example 1.6: From scratch work to a written proof
Claim. Let \(a\) , \(b\) , \(c\) be integers. If \(a\mid b\) and \(a\mid c\) , then \(a\mid(bx+cy)\) for all integers \(x\) and \(y\) .
Scratch work. First try numbers. With \(a=6\) , \(b=18\) , \(c=-30\) , \(x=5\) , \(y=2\) we get \(bx+cy=90-60=30\) , and \(30=6\cdot 5\) , so the claim holds in this instance. Why? Because \(18=6\cdot 3\) and \(-30=6\cdot(-5)\) , so \(bx+cy=6\cdot 3\cdot 5+6\cdot(-5)\cdot 2=6\,(15-10)\) . The factor \(6\) comes out of both terms. That is the whole idea, and it does not depend on the particular numbers.
What is to be shown. By Definition 1.9 the conclusion \(a\mid(bx+cy)\) means: there is an integer \(k\) with \(bx+cy=ak\) . So the proof must produce such a \(k\) .
Written proof. Let \(x\) and \(y\) be integers, and suppose \(a\mid b\) and \(a\mid c\) . Then there are integers \(s\) and \(t\) with \(b=as\) and \(c=at\) . Hence
The number \(sx+ty\) is an integer because sums and products of integers are integers. Therefore \(a\mid(bx+cy)\) .
The scratch work is not part of the proof and the numerical instance proves nothing in general; its role was to reveal the mechanism. The written proof begins from the hypotheses and ends at the conclusion, and it never assumes what it is trying to show. This proposition is used repeatedly in Chapter 4, where an expression \(bx+cy\) is called an integer linear combination of \(b\) and \(c\) .
1.6 Contrapositive, contradiction, and cases
A direct proof is not always available. Suppose we want to prove that if \(n^{2}\) is even then \(n\) is even. Unfolding the hypothesis gives \(n^{2}=2k\) , and there is no evident way to get from there to a statement about \(n\) itself, short of taking a square root. The equivalent contrapositive statement starts from information about \(n\) and is easy.
Proposition 1.11 (even squares). For every integer \(n\) , if \(n^{2}\) is even then \(n\) is even.
Proof. We prove the contrapositive: if \(n\) is not even, then \(n^{2}\) is not even. Let \(n\) be an integer that is not even. Then \(n\) is odd, so \(n=2k+1\) for some integer \(k\) , and
Thus \(n^{2}\) is odd, hence not even. By Theorem 1.4(d) the original statement follows.
A proof by contrapositive of \(P\to Q\) is a direct proof of \(\neg Q\to\neg P\) . Announce it in the first line, as above, so that the reader knows what is being assumed.
A proof by contradiction goes further. To prove a statement \(S\) , assume \(\neg S\) and derive a statement that is false, typically of the form \(C\land\neg C\) . Since a true hypothesis cannot lead by valid steps to a false conclusion, \(\neg S\) must be false, so \(S\) is true. When \(S\) is a conditional \(P\to Q\) , Theorem 1.4(e) says that assuming \(\neg S\) means assuming \(P\) and \(\neg Q\) together, which gives two hypotheses to work with instead of one.
Theorem 1.12 (irrationality of the square root of two). There are no positive integers \(a\) and \(b\) with \(a^{2}=2b^{2}\) . Consequently \(\sqrt2\) is not a rational number.
Proof. Suppose, for contradiction, that positive integers \(a\) and \(b\) with \(a^{2}=2b^{2}\) exist. Among all such pairs choose one in which \(b\) is as small as possible; this can be done because every nonempty set of positive integers has a least element.
Since \(a^{2}=2b^{2}\) , the integer \(a^{2}\) is even, so \(a\) is even by Proposition 1.11. Write \(a=2c\) with \(c\) a positive integer. Then \(4c^{2}=2b^{2}\) , so \(b^{2}=2c^{2}\) . Thus \(b^{2}\) is even, and by Proposition 1.11 again \(b\) is even. Write \(b=2d\) with \(d\) a positive integer. Substituting into \(b^{2}=2c^{2}\) gives \(4d^{2}=2c^{2}\) , that is, \(c^{2}=2d^{2}\) .
Now \((c,d)\) is a pair of positive integers with \(c^{2}=2d^{2}\) and \(d<b\) . This contradicts the choice of \(b\) as the smallest possible. Hence no such pair exists. If \(\sqrt2\) were rational it would equal \(a/b\) for some positive integers \(a\) and \(b\) , and squaring would give \(a^{2}=2b^{2}\) , which we have shown to be impossible.
The proof used a fact about the positive integers, that a nonempty set of them has a least element. Chapter 3 gives this fact a name, the well-ordering principle, and builds the method of induction on it.
Proof by cases splits the domain into finitely many parts that together cover it and proves the claim separately on each part. Its validity is the second argument of Example 1.3.
Proposition 1.13 (squares and division by four). For every integer \(n\) , the remainder of \(n^{2}\) on division by \(4\) is \(0\) or \(1\) ; more precisely, \(n^{2}=4q\) or \(n^{2}=4q+1\) for some integer \(q\) .
Proof. Every integer is even or odd, so there are two cases. If \(n\) is even, then \(n=2k\) for some integer \(k\) and \(n^{2}=4k^{2}\) , which has the form \(4q\) with \(q=k^{2}\) . If \(n\) is odd, then \(n=2k+1\) for some integer \(k\) and \(n^{2}=4k^{2}+4k+1=4(k^{2}+k)+1\) , which has the form \(4q+1\) with \(q=k^{2}+k\) . In both cases the claim holds.
Three other tasks complete the list. A biconditional \(P\leftrightarrow Q\) is proved in two parts, by Theorem 1.4(g): prove \(P\to Q\) and prove \(Q\to P\) , and label which direction is which. An existence statement is proved by producing a witness and checking it; a proof that shows something must exist without producing it is called nonconstructive, and the pigeonhole arguments of Chapter 5 are of that kind. A uniqueness statement is proved by supposing that two objects have the property and showing they are equal.
Finally, a universal statement is disproved by a counterexample, and here a single instance is a complete argument.
Example 1.7: A formula that produces primes forty times
Consider the claim: for every integer \(n\ge 0\) , the number \(n^{2}+n+41\) is prime. The values for \(n=0,1,2,3,4\) are \(41,43,47,53,61\) , all prime, and the pattern continues for a long time: the formula gives a prime for every \(n\) from \(0\) to \(39\) . Forty confirming cases might seem persuasive.
The claim is false. Taking \(n=40\) gives
which is \(41^{2}\) and therefore not prime. The counterexample need not be found by trial. The expression \(n^{2}+n+41\) equals \(n(n+1)+41\) , which is visibly divisible by \(41\) when \(n=40\) or \(n=41\) .
Two lessons follow. No finite list of examples proves a universal statement about infinitely many integers, however long the list. And one counterexample, fully checked, settles the matter; there is nothing further to argue. An existence claim is the mirror image: “some positive integer is a sum of two positive cubes in two different ways” is proved completely by the witness \(1729=1^{3}+12^{3}=9^{3}+10^{3}\) .
1.7 Writing proofs and reading them critically
The logical form of a statement determines both what a proof of it must do and how it may be used once it is known. The table summarizes the correspondences developed in this chapter.
| Form | To prove it | To use it once known |
|---|---|---|
| \(P\land Q\) | prove \(P\) ; prove \(Q\) | you may use \(P\) and you may use \(Q\) |
| \(P\lor Q\) | assume \(\neg P\) and prove \(Q\) | argue by cases: once from \(P\) , once from \(Q\) |
| \(P\to Q\) | assume \(P\) , derive \(Q\) ; or assume \(\neg Q\) , derive \(\neg P\) | if you also know \(P\) , conclude \(Q\) |
| \(P\leftrightarrow Q\) | prove both directions | replace either side by the other |
| \(\neg P\) | assume \(P\) and derive a contradiction | combine with \(P\) to obtain a contradiction |
| \(\forall x\,P(x)\) | take an arbitrary \(x\) and prove \(P(x)\) | apply it to any particular element you like |
| \(\exists x\,P(x)\) | exhibit a witness and verify it | name an element with the property; assume nothing else about it |
The row for disjunction rests on Theorem 1.4(c): \(P\lor Q\) is equivalent to \(\neg P\to Q\) .
A written proof should let the reader check it without guessing. State at the start what is assumed and, if the method is not direct, which method is used. Introduce every letter before using it and say what kind of object it is. Give a reason for each step that is not a routine computation. End by saying that the required statement has been reached. Write in complete sentences; a string of equations with no words leaves the logical relations between the lines unstated, and those relations are the proof.
Reading a purported proof critically is a separate skill, and the commonest errors have recognisable shapes.
Example 1.8: Three arguments with something wrong
Specimen one. Claim: for every integer \(n\) , if \(n^{2}\) is odd then \(n\) is odd. Argument: “Let \(n\) be odd. Then \(n=2k+1\) for some integer \(k\) , so \(n^{2}=2(2k^{2}+2k)+1\) is odd.” Every line is correct, and the claim is true, but the argument does not prove it. It assumes that \(n\) is odd and concludes that \(n^{2}\) is odd, which is the converse of the claim. A correct proof would assume \(n^{2}\) odd, or would assume the negation of the conclusion, that \(n\) is even, and deduce that \(n^{2}\) is even.
Specimen two. Claim: the product of two odd integers is a perfect square. Argument: “Let \(m\) and \(n\) be odd. Then \(m=2k+1\) and \(n=2k+1\) for some integer \(k\) , so \(mn=(2k+1)^{2}\) , a perfect square.” The claim is false: \(3\cdot 5=15\) is not a perfect square. The error is in the second sentence, which uses the same letter \(k\) for both numbers and thereby assumes \(m=n\) . Each use of an existential hypothesis needs its own new letter.
Specimen three. Claim: \(-1=1\) . Argument: “Suppose \(-1=1\) . Squaring both sides gives \(1=1\) , which is true. Hence \(-1=1\) .” The argument starts from the statement to be proved and derives a true statement. That shows only that the claim implies something true, and a false statement can imply a true one, as the third row of the truth table of the conditional records. Deriving a truth from the desired conclusion proves nothing unless every step can be reversed, and squaring cannot be reversed.
Common mistake. Proving a universal statement by checking examples, or by an argument that silently fixes a special case. Example 1.7 shows forty examples failing to establish a claim. The subtler version appears in specimen two above, where an argument that looks general has quietly restricted itself to the case \(m=n\) . After writing a proof of a statement about all \(x\) , reread it and ask of each line: does this hold for every \(x\) allowed by the hypotheses, or only for the ones I was picturing?
Common mistake. Negating a conditional as another conditional. The negation of “if \(n\) is prime then \(n\) is odd” is not “if \(n\) is prime then \(n\) is even” and not “if \(n\) is not prime then \(n\) is not odd”. With the quantifier restored, the original says \(\forall n\,(P(n)\to Q(n))\) and its negation says \(\exists n\,(P(n)\land\neg Q(n))\) : some \(n\) is prime and not odd. Write the quantifier and apply Theorem 1.8 and Theorem 1.4(e) in order.
With the language in place, the next chapter turns to the objects that all later chapters talk about: sets, the functions between them, and the relations on them. Every definition there is a quantified statement, and every proof there is one of the forms above. A question to carry forward: the proof of Theorem 1.12 chose a smallest counterexample and then produced a smaller one. What, exactly, entitles us to choose a smallest element, and what else can be done with that entitlement?
Exercises
-
Write out the truth table of \((P\lor Q)\land\neg(P\land Q)\) , describe in words when it is true, and show that it is logically equivalent to \(\neg(P\leftrightarrow Q)\) .
Answer
In the row order \((P,Q)=(T,T),(T,F),(F,T),(F,F)\) the statement has truth values \(F,T,T,F\) . It is true exactly when one of \(P\) , \(Q\) is true and the other false; this is the exclusive “or”. The biconditional \(P\leftrightarrow Q\) has values \(T,F,F,T\) , so its negation has values \(F,T,T,F\) , the same column.
-
For the statement “if an integer is divisible by \(6\) then it is divisible by \(3\) ”, write the converse, the inverse, the contrapositive, and the negation in plain English, and say which of the five statements are true for all integers.
Solution
Write \(D_6(n)\) for “\(n\) is divisible by \(6\) ” and \(D_3(n)\) for “\(n\) is divisible by \(3\) ”. The statement is \(\forall n\,(D_6(n)\to D_3(n))\) .
Converse: if an integer is divisible by \(3\) then it is divisible by \(6\) . Inverse: if an integer is not divisible by \(6\) then it is not divisible by \(3\) . Contrapositive: if an integer is not divisible by \(3\) then it is not divisible by \(6\) . Negation: there is an integer that is divisible by \(6\) and not divisible by \(3\) .
The original statement is true: if \(n=6k\) then \(n=3(2k)\) . The contrapositive is equivalent to it by Theorem 1.4(d), so it is true as well. The converse is false, with counterexample \(n=3\) , and the inverse is equivalent to the converse, so it is false with the same counterexample: \(3\) is not divisible by \(6\) and yet is divisible by \(3\) . The negation of a true statement is false. So exactly two of the five statements are true: the original and its contrapositive.
-
Decide by truth table whether each statement is a tautology, a contradiction, or neither: (a) \((P\to Q)\lor(Q\to P)\) ; (b) \((P\to Q)\land(P\land\neg Q)\) ; (c) \((P\to Q)\to(\neg P\to\neg Q)\) .
Answer
(a) Tautology: if \(Q\) is true then \(P\to Q\) is true, and if \(Q\) is false then \(Q\to P\) is true. (b) Contradiction: the second conjunct \(P\land\neg Q\) is the negation of the first by Theorem 1.4(e). (c) Neither: it is false in the row where \(P\) is false and \(Q\) is true, and true in the other three rows.
-
Using only the equivalences of Theorem 1.4 and no truth table, show that \(\neg\bigl(P\to(Q\land\neg R)\bigr)\equiv P\land(\neg Q\lor R)\) , naming the part of the theorem used at each step.
Solution
Start from the left side and apply one law at a time.
\[ \begin{aligned} \neg\bigl(P\to(Q\land\neg R)\bigr) &\equiv P\land\neg(Q\land\neg R) &&\text{by (e), with } Q\land\neg R \text{ in the role of the conclusion}\\ &\equiv P\land(\neg Q\lor\neg\neg R) &&\text{by the first law of (b)}\\ &\equiv P\land(\neg Q\lor R) &&\text{by (a).} \end{aligned} \]Each step replaces a part of the statement by an equivalent part, which is legitimate because equivalent statements have the same truth value in every row. In words: the conditional “if \(P\) then \(Q\) and not \(R\) ” fails exactly when \(P\) holds and either \(Q\) fails or \(R\) holds.
-
Test each argument form for validity, giving a counterexample row if it is invalid: (a) premises \(P\to Q\) and \(\neg P\) , conclusion \(\neg Q\) ; (b) premises \(P\to Q\) , \(Q\to R\) , and \(\neg R\) , conclusion \(\neg P\) .
Solution
(a) Invalid. Take the row in which \(P\) is false and \(Q\) is true. The premise \(P\to Q\) is true because its hypothesis is false, the premise \(\neg P\) is true, and the conclusion \(\neg Q\) is false. This is a counterexample row. The form is denying the antecedent.
(b) Valid. Suppose all three premises are true in some row. Since \(\neg R\) is true, \(R\) is false. Since \(Q\to R\) is true and \(R\) is false, \(Q\) cannot be true, so \(Q\) is false. Since \(P\to Q\) is true and \(Q\) is false, \(P\) is false. Hence \(\neg P\) is true in that row. In fact the premises are all true in exactly one of the eight rows, the row where \(P\) , \(Q\) , \(R\) are all false, and the conclusion holds there. The form is two applications of modus tollens.
-
An inspector must enforce the rule “if a person is drinking beer, then that person is at least eighteen”. Four people are present: one is drinking beer, one is drinking cola, one is known to be twenty-five, and one is known to be sixteen. Say whose age or drink must be checked, and explain how this is the four-card problem in other clothing.
Answer
Check the age of the beer drinker and the drink of the sixteen-year-old. With \(P\) for “is drinking beer” and \(Q\) for “is at least eighteen”, the rule is \(P\to Q\) and can be violated only by someone with \(P\) true and \(Q\) false. The beer drinker is the card showing a vowel, the cola drinker the consonant, the twenty-five-year-old the even number, and the sixteen-year-old the odd number.
-
Let the domain be \(\{2,3,4,5,6\}\) and let \(T(x,y)\) mean “\(x\) divides \(y\) ”. Determine the truth value of each of \(\forall x\,\exists y\,T(x,y)\) , \(\exists y\,\forall x\,T(x,y)\) , \(\exists x\,\forall y\,T(x,y)\) , and \(\forall y\,\exists x\,T(x,y)\) , justifying each answer with a witness or a counterexample.
Answer
\(\forall x\,\exists y\,T(x,y)\) is true: take \(y=x\) . \(\exists y\,\forall x\,T(x,y)\) is false: such a \(y\) would be divisible by both \(4\) and \(5\) , hence at least \(20\) , and no element of the domain is. \(\exists x\,\forall y\,T(x,y)\) is false: an \(x\) dividing \(2\) must be \(2\) , and \(2\) does not divide \(3\) . \(\forall y\,\exists x\,T(x,y)\) is true: take \(x=y\) .
-
Negate each statement, and simplify until every negation has been absorbed into a relation between numbers, such as \(\ne\) or a reversed inequality, or into the words “is not prime”; the domain is the integers: (a) \(\forall x\,\exists y\,(y>x\land y\text{ is prime})\) ; (b) \(\exists x\,\forall y\,(xy=y)\) ; (c) \(\forall x\,\bigl(x>2\to\exists y\,(y^{2}<x\land y>1)\bigr)\) .
Solution
Move the negation inward one symbol at a time.
(a) \(\neg\,\forall x\,\exists y\,(y>x\land y\text{ is prime})\equiv\exists x\,\forall y\,\neg(y>x\land y\text{ is prime})\equiv\exists x\,\forall y\,(y\le x\lor y\text{ is not prime})\) . The first step uses Theorem 1.8 twice and the second uses De Morgan’s law. In words: some integer has no prime above it.
(b) \(\neg\,\exists x\,\forall y\,(xy=y)\equiv\forall x\,\exists y\,(xy\ne y)\) . In words: no integer acts as a multiplicative identity. The original is true, with witness \(x=1\) , so this negation is false.
(c) The inner statement is a conditional, so Theorem 1.4(e) applies after the first quantifier is passed:
\[ \neg\,\forall x\,\bigl(x>2\to\exists y\,(y^{2}<x\land y>1)\bigr)\equiv\exists x\,\bigl(x>2\land\forall y\,(y^{2}\ge x\lor y\le 1)\bigr). \]Here the negation is the true statement: \(x=3\) is a witness, because every integer \(y\) with \(y>1\) has \(y^{2}\ge 4\ge 3\) .
-
Translate into quantified symbolic form over the integers, introducing predicates as needed: (a) there is no largest integer; (b) every even integer greater than \(2\) is a sum of two primes; (c) between any two distinct integers that differ by more than one there lies another integer. Then write the negation of (a) in words.
Hint
(a) Say that no integer \(M\) is at least as large as every integer: \(\neg\,\exists M\,\forall n\,(n\le M)\) , equivalently \(\forall M\,\exists n\,(n>M)\) . (b) Introduce \(E(n)\) for “\(n\) is even” and \(\mathrm{Pr}(p)\) for “\(p\) is prime”; the outer shape is \(\forall n\,((E(n)\land n>2)\to\exists p\,\exists q\,(\dots))\) . (c) Use two universal quantifiers, a hypothesis \(b-a>1\) , and one existential quantifier. The negation of (a) reads: there is an integer that is greater than or equal to every integer.
-
Write complete proofs, in the unfold, compute, fold-back style of Proposition 1.10, that the sum of an even integer and an odd integer is odd and that the product of two odd integers is odd.
Hint
For the first claim write the even number as \(2j\) and the odd number as \(2k+1\) with different letters, add, and factor out a \(2\) from everything except a single \(1\) . For the second, multiply \((2j+1)(2k+1)\) and collect the three even terms. Finish each proof by saying which integer plays the role of \(k\) in Definition 1.9.
-
Prove that for all integers \(a\) , \(b\) , \(c\) : if \(a\mid b\) and \(b\mid c\) then \(a\mid c\) . Then prove that if \(a\) and \(b\) are positive integers with \(a\mid b\) and \(b\mid a\) , then \(a=b\) .
Solution
First statement. Let \(a\) , \(b\) , \(c\) be integers with \(a\mid b\) and \(b\mid c\) . By Definition 1.9 there are integers \(s\) and \(t\) with \(b=as\) and \(c=bt\) . Substituting, \(c=(as)t=a(st)\) . The number \(st\) is an integer, so \(a\mid c\) .
Second statement. Let \(a\) and \(b\) be positive integers with \(a\mid b\) and \(b\mid a\) . There is an integer \(s\) with \(b=as\) . Since \(a\) and \(b\) are positive, \(s\) is positive, and a positive integer is at least \(1\) ; hence \(b=as\ge a\) . In the same way \(a=bt\) for a positive integer \(t\) , so \(a\ge b\) . From \(b\ge a\) and \(a\ge b\) we conclude \(a=b\) .
Positivity was used to get \(s\ge 1\) , and it cannot be dropped: \(2\mid -2\) and \(-2\mid 2\) , yet \(2\ne -2\) . Both statements are used later, in Section 2.6, where they say that divisibility on the positive integers is transitive and antisymmetric.
-
Prove by contrapositive that for all integers \(m\) and \(n\) , if \(mn\) is even then \(m\) is even or \(n\) is even. State the contrapositive explicitly before proving it, using De Morgan’s laws to simplify it.
Solution
By De Morgan’s law, the negation of “\(m\) is even or \(n\) is even” is “\(m\) is not even and \(n\) is not even”, that is, “\(m\) is odd and \(n\) is odd”. So the contrapositive of the claim is: if \(m\) and \(n\) are both odd, then \(mn\) is odd.
Proof of the contrapositive. Let \(m\) and \(n\) be odd integers. Then \(m=2j+1\) and \(n=2k+1\) for some integers \(j\) and \(k\) , and
\[ mn=(2j+1)(2k+1)=4jk+2j+2k+1=2(2jk+j+k)+1 . \]Since \(2jk+j+k\) is an integer, \(mn\) is odd, hence not even. This proves the contrapositive, and therefore the original statement, by Theorem 1.4(d).
-
Prove that for all integers \(a\) and \(b\) , if \(a+b\ge 15\) then \(a\ge 8\) or \(b\ge 8\) .
Hint
Prove the contrapositive. By De Morgan’s law the negation of “\(a\ge 8\) or \(b\ge 8\) ” is “\(a\le 7\) and \(b\le 7\) ”. Add the two inequalities.
-
Assume that every integer has exactly one of the forms \(3k\) , \(3k+1\) , \(3k+2\) . Prove that if \(3\mid n^{2}\) then \(3\mid n\) , and then adapt the proof of Theorem 1.12 to show that there are no positive integers \(a\) , \(b\) with \(a^{2}=3b^{2}\) .
Solution
First part, by contrapositive: we show that if \(3\nmid n\) then \(3\nmid n^{2}\) . If \(3\nmid n\) then \(n\) is not of the form \(3k\) , so \(n=3k+1\) or \(n=3k+2\) for some integer \(k\) . In the first case \(n^{2}=9k^{2}+6k+1=3(3k^{2}+2k)+1\) . In the second case \(n^{2}=9k^{2}+12k+4=3(3k^{2}+4k+1)+1\) . In both cases \(n^{2}\) has the form \(3q+1\) , and since every integer has exactly one of the three forms, \(n^{2}\) is not of the form \(3q\) . So \(3\nmid n^{2}\) .
Second part. Suppose positive integers \(a\) , \(b\) with \(a^{2}=3b^{2}\) exist, and choose such a pair with \(b\) as small as possible. Then \(3\mid a^{2}\) , so \(3\mid a\) by the first part; write \(a=3c\) . Then \(9c^{2}=3b^{2}\) , so \(b^{2}=3c^{2}\) , so \(3\mid b^{2}\) and hence \(3\mid b\) ; write \(b=3d\) . Then \(9d^{2}=3c^{2}\) , so \(c^{2}=3d^{2}\) with \(c\) , \(d\) positive and \(d<b\) . This contradicts the minimality of \(b\) . Hence no such pair exists, and \(\sqrt3\) is irrational.
-
Assume two facts that Chapter 4 will prove: every integer has one of the forms \(4k\) , \(4k+1\) , \(4k+2\) , \(4k+3\) , and no integer has two different remainders on division by \(8\) . Prove by cases that the square of every integer leaves remainder \(0\) , \(1\) , or \(4\) on division by \(8\) , and deduce that no integer of the form \(8k+7\) is a sum of two squares.
Solution
Let \(n\) be an integer. There are four cases.
If \(n=4k\) , then \(n^{2}=16k^{2}=8(2k^{2})\) , remainder \(0\) . If \(n=4k+1\) , then \(n^{2}=16k^{2}+8k+1=8(2k^{2}+k)+1\) , remainder \(1\) . If \(n=4k+2\) , then \(n^{2}=16k^{2}+16k+4=8(2k^{2}+2k)+4\) , remainder \(4\) . If \(n=4k+3\) , then \(n^{2}=16k^{2}+24k+9=8(2k^{2}+3k+1)+1\) , remainder \(1\) . So every square leaves remainder \(0\) , \(1\) , or \(4\) on division by \(8\) .
Now let \(x\) and \(y\) be integers, and write \(x^{2}=8s+r_1\) and \(y^{2}=8t+r_2\) with \(r_1,r_2\in\{0,1,4\}\) . Then \(x^{2}+y^{2}=8(s+t)+(r_1+r_2)\) , and the possible values of \(r_1+r_2\) are \(0,1,2,4,5,8\) . Hence the remainder of \(x^{2}+y^{2}\) on division by \(8\) is one of \(0,1,2,4,5\) . The remainder \(7\) never occurs, so no integer of the form \(8k+7\) is a sum of two squares. The same argument excludes the forms \(8k+3\) and \(8k+6\) .
-
Disprove each statement with an explicit, fully checked counterexample: (a) for all integers \(a\) , \(b\) , \(c\) , if \(a\mid bc\) then \(a\mid b\) or \(a\mid c\) ; (b) \(2^{n}+1\) is prime for every integer \(n\ge 0\) ; (c) for every real number \(x\) , \(x^{2}\ge x\) .
Solution
(a) Take \(a=6\) , \(b=4\) , \(c=9\) . Then \(bc=36=6\cdot 6\) , so \(a\mid bc\) . But \(6\nmid 4\) , since the multiples of \(6\) nearest to \(4\) are \(0\) and \(6\) , and \(6\nmid 9\) , since \(9\) lies strictly between the consecutive multiples \(6\) and \(12\) . The hypothesis holds and the conclusion fails.
(b) Take \(n=3\) . Then \(2^{3}+1=9=3\cdot 3\) , which is not prime. The values for \(n=0,1,2\) are the primes \(2,3,5\) , which is why the statement looks plausible.
(c) Take \(x=\tfrac12\) . Then \(x^{2}=\tfrac14\) , and \(\tfrac14<\tfrac12\) , so \(x^{2}\ge x\) fails. Every real number strictly between \(0\) and \(1\) is a counterexample; one is enough.
-
Prove that an integer \(n\) is even if and only if \(7n+4\) is even, writing the two directions separately and saying which method you use for each.
Hint
For “if \(n\) is even then \(7n+4\) is even” use a direct proof: substitute \(n=2k\) and factor. For “if \(7n+4\) is even then \(n\) is even” use the contrapositive: substitute \(n=2k+1\) and show that \(7n+4=2(7k+5)+1\) .
-
Prove that there is exactly one integer \(n\ge 2\) for which \(n^{2}-1\) is prime: establish existence with a witness and uniqueness with an argument valid for every other \(n\) .
Solution
Existence. For \(n=2\) we have \(n^{2}-1=3\) , which is prime.
Uniqueness. Let \(n\) be an integer with \(n\ge 3\) . Factor \(n^{2}-1=(n-1)(n+1)\) . Since \(n\ge 3\) , the first factor satisfies \(n-1\ge 2\) and the second satisfies \(n+1\ge 4\) . So \(n^{2}-1\) is a product of two integers each greater than \(1\) , and therefore each smaller than \(n^{2}-1\) itself; it has a divisor other than \(1\) and itself and is not prime. Hence \(n=2\) is the only integer \(n\ge 2\) for which \(n^{2}-1\) is prime. Notice that the uniqueness argument does not examine examples; the factorization handles every \(n\ge 3\) at once.
-
Claim: for every integer \(n\) , if \(n^{2}\) is divisible by \(4\) then \(n\) is divisible by \(4\) . Proposed proof: “Let \(n=4k\) . Then \(n^{2}=16k^{2}=4(4k^{2})\) , which is divisible by \(4\) .” Say precisely what the argument proves, and decide whether the claim itself is true.
Answer
The argument assumes that \(n\) is divisible by \(4\) and concludes that \(n^{2}\) is divisible by \(4\) : it proves the converse of the claim. The claim itself is false, with counterexample \(n=2\) , since \(2^{2}=4\) is divisible by \(4\) and \(2\) is not.
-
The following argument “proves” that \(\sqrt4\) is irrational. “Suppose \(\sqrt4=a/b\) with \(b\) as small as possible. Then \(a^{2}=4b^{2}\) , so \(a^{2}\) is divisible by \(4\) , so \(a\) is divisible by \(4\) ; write \(a=4c\) . Then \(16c^{2}=4b^{2}\) , so \(b^{2}=4c^{2}\) , so \(b\) is divisible by \(4\) ; write \(b=4d\) . Then \(\sqrt4=c/d\) with \(d<b\) , a contradiction.” Find the first false step and give a number showing it is false.
Solution
The first false step is “\(a^{2}\) is divisible by \(4\) , so \(a\) is divisible by \(4\) ”. The number \(a=2\) shows that this inference is not valid: \(2^{2}=4\) is divisible by \(4\) , and \(2\) is not. Indeed \(\sqrt4=2/1\) , so in the supposed minimal representation \(a=2\) and \(b=1\) , and the false step is applied to exactly this \(a\) .
What is true is only that \(a\) is even. Following the argument with that correct inference, \(a=2c\) gives \(4c^{2}=4b^{2}\) , so \(b=c\) , and no contradiction arises. The proof of Theorem 1.12 does not have this defect, because the corresponding step there, from “\(a^{2}\) is even” to “\(a\) is even”, is Proposition 1.11, which was proved. The lesson is that a proof obtained by imitating another must have each borrowed step justified again in the new setting.
-
Explain why the statement “for every integer \(n\) , if \(n^{2}<0\) then \(n=17\) ” is true, state its converse, and decide whether the converse is true.
Hint
Ask how many integers satisfy the hypothesis \(n^{2}<0\) . The converse is “for every integer \(n\) , if \(n=17\) then \(n^{2}<0\) ”; test it at the one integer that satisfies its hypothesis.
-
Prove by contradiction that the sum of a rational number and an irrational number is irrational, stating clearly which two hypotheses the assumption for contradiction gives you.
Solution
Let \(r\) be rational and \(x\) irrational. The statement to prove is the conditional “if \(r\) is rational and \(x\) is irrational, then \(r+x\) is irrational”. Assuming it false gives, by Theorem 1.4(e), the hypotheses together with the negated conclusion: \(x\) is irrational, and \(r+x\) is rational.
Since \(r\) and \(r+x\) are rational, there are integers \(a,b,c,d\) with \(b\ne 0\) , \(d\ne 0\) , \(r=a/b\) , and \(r+x=c/d\) . Then
\[ x=(r+x)-r=\frac cd-\frac ab=\frac{cb-ad}{bd}. \]The numerator \(cb-ad\) and the denominator \(bd\) are integers, and \(bd\ne 0\) . So \(x\) is rational. This contradicts the hypothesis that \(x\) is irrational. Hence \(r+x\) is irrational.