1.1  Statements, Arguments and How to Break One

When is an argument a proof? This section says what the sentences of a proof are, how they are built from smaller ones, and how to test the form of an argument by trying to break it.

1.1.1. Two arguments about squares

Recall that an integer $n$ is even when $n=2k$ for some integer $k$, and odd when $n=2k+1$ for some integer $k$. Here is a fact about integers.

For every integer $n$, if $n^2$ is even, then $n$ is even.

Read the following two arguments for it. Each is written in the style of a textbook proof, and each claim in each of them is true.

Argument A. Suppose $n$ is odd, say $n=2k+1$ for an integer $k$. Then $n^2=4k^2+4k+1=2(2k^2+2k)+1$, so $n^2$ is odd, and therefore $n^2$ is not even. So an odd $n$ never has an even square. Since every integer is even or odd, an integer with an even square must be even.

Argument B. Suppose $n$ is even, say $n=2k$ for an integer $k$. Then $n^2=4k^2=2(2k^2)$, and $2k^2$ is an integer, so $n^2$ is even. Hence if $n^2$ is even, then $n$ is even.

Argument A is a correct proof. Argument B is not, although none of its claims is false. It starts from “$n$ is even” and arrives at “$n^2$ is even”. That is a perfectly good proof of a different statement: “if $n$ is even, then $n^2$ is even”. The claim asks for the journey in the opposite direction, from the square back to the number, and the last sentence of B announces a conclusion that the argument never reached.

Seeing this is easy once it is pointed out. Saying in general what went wrong is harder, and that is what this chapter and the next are for. To name the error we need to know what the rules of proof are, and before that, what they act on. So we start with the smallest pieces: the sentences a proof is made of.

1.1.2. Statements

A proof is written in sentences, but not every sentence can appear in one. “Is 91 prime?” asserts nothing, so it cannot serve as a premise or a conclusion; neither can “Let us now turn to the case $n=0$.” The sentences a proof asserts are the ones that make a claim. A proof also has steps of another kind, such as “Suppose $n$ is odd”, which assert nothing but set up a temporary hypothesis; their rules come in Section 1.4.

A statement is a sentence that is either true or false.

In words: a statement makes a claim, and the claim is either correct or incorrect. The definition asks that one of the two is the case. It does not ask that we know which one. A statement whose truth nobody has settled is still a statement.

Items (e) and (f) differ by one symbol, and the difference is the whole point. The open sentence $x>2$ becomes a statement in two ways. We can put a number in for $x$, as in (f). Or we can say which $x$ we mean in some other way, as in “for every real number $x$, $x>2$” (a false statement) or “for some real number $x$, $x>2$” (a true one). The words “for every” and “for some” are the quantifiers.

1.1.3. The connectives

Most statements in mathematics are built from smaller ones. “$0<x$ and $x<1$” is built from “$0<x$” and “$x<1$” with the word “and”. “If $n^2$ is even, then $n$ is even” is built from two statements with “if … then”. The words that do the building are the connectives. A statement built from smaller statements by a connective is compound; one that is not is atomic. For this chapter, “$x>0$” is atomic: it has an inner structure, a number and an order, but no connective joins parts of it.

We write $P$, $Q$, $R$, $S$ for statements whose inner structure we are ignoring. They stand for arbitrary statements, atomic or compound. There are five connectives. In the last column, $x$ is a real number, and every example is true whatever $x$ is.

To the five connectives we add one statement with no parts at all, written $\mathrm{\perp }$ and read “contradiction”. It stands for a statement that is false however things stand: $0=1$ will do. A proof that reaches $\mathrm{\perp }$ has shown that the situation it was working in cannot occur. That is the heart of proof by contradiction, and the rules for $\mathrm{\perp }$ come with those for “not”.

In $P\to Q$, the statement $P$ is the hypothesis (or antecedent) and $Q$ the conclusion (or consequent). “If and only if” is often shortened to iff.

Several English words become $\wedge$: “but”, “although”, and “while” all assert both parts, and add a tone of contrast that logic ignores. “$2$ is prime but not odd” is a conjunction. So is “neither … nor”, in disguise: “$9$ is neither even nor prime” asserts that $9$ is not even and that $9$ is not prime, which is $\mathrm{\neg }P\wedge \mathrm{\neg }Q$ with $P$: “$9$ is even” and $Q$: “$9$ is prime”.

Chained inequalities are conjunctions in disguise too. $0<x<1$ abbreviates $(0<x)\wedge (x<1)$, and $a\le b\le c$ abbreviates $(a\le b)\wedge (b\le c)$. The symbol $\le$ itself hides a disjunction: $a\le b$ means $(a<b)\vee (a=b)$. And $a\ne b$ is the negation $\mathrm{\neg }(a=b)$. All three facts are used often in the sections that follow.

In theorem statements the book writes $\Rightarrow$ and $⟺$, as mathematicians usually do, and in running prose it says “implies” and “if and only if”. The arrows $\to$ and $\leftrightarrow$ are kept for statements written in logical symbols, as in this section, whether built from letters like $P\to Q$ or from formulas like $(x>1)\to (x^2>1)$, and for the formal derivations that start in the next. Nothing but typography separates the two pairs.

1.1.4. When is an implication broken?

Read $P\to Q$ as a promise: whenever $P$ holds, $Q$ holds too. A promise is broken only when its condition is met and the promised thing fails.

An implication is broken only when its hypothesis holds and its conclusion fails.

Take the table’s example, “if $x>1$, then $x^2>1$”. Its two parts can be true or false in four combinations:

(No value lands in the second row: if $x>1$, then $x^2>x>1$.) This answers the question “what if $P$ is false?”: then $P\to Q$ is not broken, so it counts as true. To show $P\to Q$ false, exhibit one case with $P$ true and $Q$ false.

1.1.5. “Only if”, “necessary” and “sufficient”

English has many ways of saying $P\to Q$: “$P$ implies $Q$”, “$Q$ if $P$”, “$Q$ whenever $P$”, “$P$ only if $Q$”, “$P$ is sufficient for $Q$”, and “$Q$ is necessary for $P$”. To sort out the last three, ask of each sentence: when is it broken? Let $x$ be a real number, with $P$: “$x>2$” and $Q$: “$x^2>4$”.

• “$x>2$ only if $x^2>4$” says that $x>2$ never happens without $x^2>4$. It is broken exactly when $x>2$ and $x^2\le 4$, which is exactly when $P\to Q$ is broken. So “$P$ only if $Q$” is $P\to Q$. It is true here: if $x>2$, then $x^2>2x>4$.
• The reverse, “$x^2>4$ only if $x>2$”, is $Q\to P$, broken by $x=-3$ (the Quick check above).
• “$x^2>4$ is necessary for $x>2$” says that there is no $x>2$ without $x^2>4$: again $P\to Q$. “$x>2$ is sufficient for $x^2>4$” says that $x>2$ is enough to guarantee $x^2>4$: $P\to Q$ once more.

“If” and “only if” put the same two statements in opposite directions: “$Q$ if $P$” is $P\to Q$, while “$Q$ only if $P$” is $Q\to P$. Confusing them is Argument B’s mistake.

1.1.6. Translating a sentence

Translating into symbols is a skill of its own, best learned slowly, in three steps. Find the atomic statements, the smallest pieces that make a claim, and give each a letter. Find the connectives, whatever English words carry them. Then decide how the pieces group.

Take “if $12$ is divisible by $3$ and by $4$, then $12$ is divisible by $6$”. The atomic statements are $P$: “$12$ is divisible by $3$”, $Q$: “$12$ is divisible by $4$” and $R$: “$12$ is divisible by $6$”. English lets “$12$ is divisible by” be said once and shared; logic writes each piece in full. The words “if … then” carry $\to$, and “and” carries $\wedge$. The hypothesis is everything between “if” and “then”, so the statement is $(P\wedge Q)\to R$, not $P\wedge (Q\to R)$. The second reading would claim $P$ outright, and the English sentence claims nothing outright: it only says what follows from what.

A second example shows a connective hidden inside a word. Let $x$ be a real number, and read “$x$ is non-zero, and if $x$ is positive, then so is $x^3$”. With $Z$: “$x=0$”, $P$: “$x>0$” and $C$: “$x^3>0$”, “non-zero” is $\mathrm{\neg }Z$, and the whole sentence is $\mathrm{\neg }Z\wedge (P\to C)$. Letters that recall their statements, as here, often help; a letter is only a name.

In both examples the English word order is a poor guide to the grouping. When in doubt, ask of each connective: which two statements does it join?

1.1.7. A phrase book

Many English phrases carry a connective in disguise. The table collects the common ones; in each row, ask the question of “Only if”: when is the sentence broken? In the examples, $n$ is an integer and $x$ is a real number.

“Unless” is Exercise C1.

“Neither … nor” and “not both” differ by one word and say different things. At $n=3$, “$n$ is neither even nor prime” is false, since $3$ is prime, while “$n$ is not both even and prime” is true. In the “exactly one” row, at $x=2$ exactly one part holds ($2>0$, and $2<1$ fails); at $x=\frac{1}{2}$ both hold, so “exactly one” fails. In the last row, $n=6$ satisfies all three parts, and $n=-3$ only one: it is a multiple of $3$, but odd and negative.

Not every “and” joins two statements. Some sentences with “and” in them make one claim about several things together.

• “$4$ and $9$ are coprime.” Not: “$4$ is coprime $\wedge$ $9$ is coprime”. Coprime is a relation between two numbers (their only common positive divisor is $1$), so the sentence is one atomic statement about a pair. Contrast “$4$ and $9$ are squares”, which is a conjunction.
• “The points $A$, $B$, $C$ are collinear.” Not: a conjunction of three statements about single points. Collinearity is one statement about all three points at once.
• “$1.414$ is an approximate root of $x^2-2=0$.” Not: “$1.414$ is approximate $\wedge$ $1.414$ is a root”. It is not a root, since ${1.414}^2=1.999396$. “Approximate” changes the meaning of “root”, and nothing here is a conjunction.

By contrast, “$12$ is a positive even number” is the conjunction of “$12>0$” and “$12$ is even”.

1.1.8. Reading a statement: precedence and the main connective

Connectives can be combined without limit, and a string of symbols is only useful if it can be read in one way. Consider $\mathrm{\neg }P\wedge Q$. Does it deny $P$ and then assert $Q$, or does it deny the whole of $P\wedge Q$? These are different claims. With $P$: “$n$ is even” and $Q$: “$n>0$”, the first says that $n$ is odd and positive, while the second says only that $n$ is not a positive even number, which $n=-4$ satisfies.

Parentheses settle every such question, and a few conventions let us drop the ones that would only add clutter.

In a mixture of $\wedge$ and $\vee$, or of $\to$ and $\leftrightarrow$, the parentheses are always written.

In this chapter we parse by eye.

The conventions only decide where parentheses may be dropped. The next definition names the one piece of information that reading a statement is for.

The main connective is found by undoing the construction from the outside. Take $$\mathrm{\neg }(P\wedge Q)\to R.$$ By convention (1), the $\mathrm{\neg }$ applies only to the parenthesized $P\wedge Q$. That leaves a single connective outside the parentheses, the $\to$, joining $\mathrm{\neg }(P\wedge Q)$ on its left and $R$ on its right. So the last step joined $\mathrm{\neg }(P\wedge Q)$ and $R$ with $\to$, and $\to$ is the main connective. Its hypothesis $\mathrm{\neg }(P\wedge Q)$ has main connective $\mathrm{\neg }$, applied to $P\wedge Q$, whose main connective is $\wedge$. The construction can be drawn as a tree, with the main connective at the root and the letters at the leaves.

Reading the tree from the top: the statement is an implication; its hypothesis is a negation; what is negated is a conjunction. Reading from the bottom retraces how the statement was built. A one-symbol change moves the root: in $\mathrm{\neg }(P\wedge Q\to R)$ the parentheses make the whole implication the thing denied, and the main connective is $\mathrm{\neg }$.

The main connective is not grammar for its own sake. It is the first thing to find when a proof has to be written, because it decides how the proof begins. To prove “if $0<x<1$, then $x^2<x$”, whose main connective is $\to$, a proof starts “Suppose $0<x<1$.” To prove “$x^2+1>0$ and $x^2+1\ne 0$”, whose main connective is $\wedge$, a proof has two parts, one for each side. Section 1.2 gives this habit a name, and each later section adds to it.

1.1.9. The form of an argument

Here are two short arguments, one about integers and one about real numbers.

If $n$ is odd, then $n^2$ is odd. And $n$ is odd. So $n^2$ is odd.

If $x>2$, then $x^2>4$. And $x>2$. So $x^2>4$.

They are about different things, and yet they are the same argument. Write $P$ for “$n$ is odd” and $Q$ for “$n^2$ is odd” in the first, and $P$ for “$x>2$” and $Q$ for “$x^2>4$” in the second. Both then read: from $P\to Q$ and $P$, conclude $Q$. What makes the step correct has nothing to do with odd numbers or squares. It depends only on the shape of the premises, on the fact that one of them is an implication and the other is its hypothesis. That shape is the argument’s form, and the part of the argument that lives in the letters is its content.

Logic studies the forms of arguments, not their content.

Separating the two has a payoff. Once a form has been shown to be correct, every argument of that form is correct, whatever its content; we check the form once and use it forever. An argument form is written with its premises above a line and its conclusion below it: $$\begin{array}{l}P\to Q\\ P\\ Q\end{array}$$ In running text the same form is written “from $P\to Q$ and $P$, conclude $Q$”.

1.1.10. Try to break it

Breaking a form means making several statements true at once, and the list of them deserves a name.

For “from $P\to Q$ and $Q$, conclude $P$” the counterexample set is $P\to Q$, $Q$, $\mathrm{\neg }P$.

To test a form, try to break it: put statements in for the letters that make every premise true and the conclusion false.

One counterexample settles that the form is bad. Failing to find one settles nothing yet: showing that a form is good takes a reason that covers every choice of statements at once.

Where to look first. Make the conclusion false first: that fixes some letters, and the premises must then be made true around it. With statements about numbers, try $0$, $1$, $-1$, $2$ and $\frac{1}{2}$ before anything clever; most bad forms about numbers break at one of them. Take the form “from $P\to Q$ and $Q\to R$, conclude $R\to P$”. Its conclusion is false only with $R$ true and $P$ false. Take $P$: “$x>2$”, $Q$: “$x>1$” and $R$: “$x>0$”; both premises then hold for every real $x$. At $x=\frac{1}{2}$, $R$ is true and $P$ is false, so the whole counterexample set $P\to Q$, $Q\to R$, $\mathrm{\neg }(R\to P)$ is true, and the form is bad.

Argument B, tried. B’s reasoning shows “if $n$ is even, then $n^2$ is even”, and its last sentence concludes the converse, “if $n^2$ is even, then $n$ is even”. That step has the form “from $P\to Q$, conclude $Q\to P$”, and it breaks: take $P$: “$n$ is divisible by $4$” and $Q$: “$n$ is even”. The premise is true for every integer, and the conclusion fails at $n=2$. B’s tempting repair, “from $P\to Q$ and $Q$, conclude $P$”, is the form of (i), which $n=2$ just broke. With B’s own content no integer breaks the repair, since every integer with an even square is even (the fact B set out to prove); but the form breaks. A true conclusion reached by a bad form is still not proved.

1.1.11. Good form, false sentences

Argument B has true claims and a bad form. The opposite happens too:

If $6$ is even, then $6$ is prime. And $6$ is even. So $6$ is prime.

Its form, “from $P\to Q$ and $P$, conclude $Q$”, is good (Quick check (ii) above), and its conclusion is false. The fault is the first premise, false since $6$ is even and not prime. Form and truth are separate questions; all four combinations occur.

The top left is the odd-square argument at $n=3$; the bottom right is the Quick check’s (i) at $n=2$. Argument A is not placed. One bad step puts an argument in the bottom row, which is how B got there, but the top row needs every step shown good. A’s steps argue from a supposition (“Suppose $n$ is odd …”) and use “some” (an integer $k$ with $n=2k+1$), and a form written as premises above a line cannot yet express either. Section 1.4 gives the rules for a supposition, and Chapter 5 those for “some”.

A good form guarantees only that true premises give a true conclusion.

1.1.12. Two ways to attack an argument

An argument can be attacked in two ways, and the two are independent. Attack a premise: show that it is false, as with the argument about $6$ above. Attack a step: show that its form is bad by breaking it, as with Argument B. A false premise says nothing about the steps, and a broken step says nothing about the premises. A defended argument needs both: good forms, and premises the reader accepts.

To doubt an argument, doubt a premise or break a step.

The two attacks, in the order a checker makes them:

Failing to break a step is not the “no” answer: the arrow down from the first question needs every step shown good, by a reason that covers every choice of statements.

1.1.13. Each connective, two rules

We now come to the idea that organizes this chapter and the next. Think about what a mathematician does with the word “and”. There are exactly two things to do with it.

• To prove a statement of the form $P\wedge Q$, prove $P$ and prove $Q$.
• To use a statement of the form $P\wedge Q$ that is already known, take either half.

Nobody needs to be taught these two moves. They are also, and this is the point, all there is to know about “and” for the purpose of writing proofs. Every other fact about $\wedge$, such as that $P\wedge Q$ and $Q\wedge P$ say the same thing, follows from the two moves, as Section 1.2 shows. The first move is called the introduction rule for $\wedge$, written $\wedge \mathrm{I}$, because it is how a $\wedge$ gets into a proof. The second is the elimination rule, $\wedge \mathrm{E}$, because it is how a $\wedge$ is taken apart.

The table below is an informal preview. Section 1.2 states these two rules exactly, as patterns of lines.

Every connective works the same way. Each comes with introduction rules, saying how to prove a statement with that main connective, and elimination rules, saying what a statement with that main connective lets us conclude. The rules for $\wedge$ come in Section 1.2, those for $\to$ in Sections 1.3 and 1.4, and those for $\vee$ in Sections 1.5 and 1.6. The rules for $\mathrm{\neg }$, $\mathrm{\perp }$, and $\leftrightarrow$, and one more rule for proof by contradiction, which stands apart from the others, come after these. Two slogans summarize the plan.

Each connective comes with a way to prove it and a way to use it.

A proof is a chain in which every line is a premise, an assumption, or one application of a rule.

The second slogan is what makes a proof possible to check. Finding a proof may need an idea. Checking one needs none: go through it line by line and ask of each line which rule produced it and whether that rule was applied to lines that really are there. A reader who has lost the thread of a long argument can always fall back on that question, and it is the question to ask of Argument B.

Section 1.4 names exactly what B did wrong; the test try to break it has already shown, at $n=2$ in its Quick check (i), that B’s tempting repair, “from $P\to Q$ and $Q$, conclude $P$”, is a bad form.

1.1.14. What comes next

Section 1.2 shows what a derivation is, with the rules for “and”. Each later section adds one rule. Two questions guide every search: what does the goal’s main connective ask for, and what does an available line’s main connective let me do?

1.1.15. Exercises

A. Check your understanding

B. Practice

Solution.

• (a) $(\mathrm{\neg }P)\to Q$, main connective $\to$. As a tree:
  
• (b) $(P\vee (\mathrm{\neg }Q))\leftrightarrow (\mathrm{\neg }R)$, main connective $\leftrightarrow$. Each $\mathrm{\neg }$ applies to the single letter after it, and $\vee$ binds more tightly than $\leftrightarrow$. As a tree:
  
• (c) $(\mathrm{\neg }(\mathrm{\neg }P))\wedge (Q\to R)$, main connective $\wedge$. The first $\mathrm{\neg }$ applies to the statement $\mathrm{\neg }P$, which is the smallest complete statement following it. As a tree:

The statement $P\wedge Q\to R$ is $(P\wedge Q)\to R$: “if $x>0$ and $y>0$, then $xy>0$”. It is true for all real $x$ and $y$, since the product of two positive numbers is positive.