Discrete Mathematics and Proof

Modus ponens, chaining, and a common fallacy

One fact is known to bring a second with it. If the first holds, is the second now certain? If the second holds, does that bring back the first? And when two such links meet end to end, what do they give?

You need

Valid and sound argumentsDiscrete Mathematics and Proof

Where you are 4 in What an argument is

Logic, proof and discrete math6

Logic9

What an argument is4

Modus ponens, chaining, and a common fallacy

Testing an argument with a truth table Valid and sound arguments Modus tollens, ruling out, and a common fallacy

Why this exists

Mathematics stores most of what it knows as if-then statements. “If a triangle has a right angle, then the square of its longest side is the sum of the squares of the other two.” “If a whole number ends in 0, then it is divisible by 10.” A statement like that, on its own, tells you nothing about any particular triangle or number. It is a promise waiting for a case.

The step that turns the promise into a fact is so natural it is easy to miss: you check that this triangle does have a right angle, and conclude that its sides obey the rule. That step is modus ponens, Latin for roughly “the way of affirming”: affirm the if-part, and the then-part comes with it. Every time a theorem is applied, and every time a line of algebra follows from the line above it, modus ponens is doing the work.

Two more moves sit right beside it. The first joins promises together. Suppose you know two separate facts: if the ferry is canceled, the team drives instead, and if the team drives, they arrive after dark. Neither fact alone links the ferry to the time they arrive. Put together, they say something neither one said by itself: if the ferry is canceled, the team arrives after dark. That new fact came out without checking whether the ferry actually was canceled, and without restating the driving step. Most real reasoning is built out of chains like this one: several “if... then...” statements laid end to end, each picking up where the last left off, and a direct proof often strings together several such steps. Rather than re-justify the whole chain every time, it helps to have one rule that says: whenever two conditionals share a middle statement this way, they collapse into a single conditional connecting the two ends. That rule is hypothetical syllogism.

The second move feels just as natural and is not allowed. Given “if it rained, the ground would be wet”, and told that the ground is wet, it feels as if you should be able to work backward to the rain. But sprinklers wet the ground too. Rain is one way among several to get a wet ground, and the wet ground does not record which way produced it. This move, affirming the consequent, differs from modus ponens only in which half of the conditional is given, so the broken version needs a name of its own.

Definition

Modus ponens, the law of detachment

Modus ponens is the argument form

\begin{array}{l} P \to Q \\ P \\ \hline \therefore\; Q \end{array}

Above the line are the two premises, the statements taken as given: a conditional P \to Q, and its if-part P standing on its own. Below the line is the conclusion Q, the conditional’s then-part. The symbol \therefore is read “therefore”. In words: if P then Q; and P; therefore Q.

In the conditional P \to Q, the if-part P is called the antecedent and the then-part Q the consequent. To affirm a statement is to assert that it is true, so modus ponens affirms the antecedent.

Any argument with this shape is an instance of modus ponens, whatever P and Q say. “If n is a multiple of 4, then n is even. n is a multiple of 4. Therefore n is even.” is one. “If the train is canceled, the fare is refunded. The train is canceled. Therefore the fare is refunded.” is another. The rule looks only at the shape, and the shape is strict: the second premise must be the if-part exactly, asserted as true, about the same object the conditional is about.

Geometry courses call the same rule the law of detachment: the conclusion Q is detached from the conditional and left standing on its own.

Hypothetical syllogism, the law of syllogism

Hypothetical syllogism takes two conditional statements that share a middle term and combines them into a third: given P \to Q and Q \to R, both true, conclude P \to R.

The letters P, Q and R can stand for any statements at all, simple or built out of others; the rule does not care what they say, only that the conclusion of the first is exactly the hypothesis of the second. Written as a deduction, the way a valid argument is usually laid out, with the premises above the line and the conclusion below it:

\begin{array}{l} P \to Q \\ Q \to R \\ \hline \therefore\; P \to R \end{array}

Geometry courses call it the law of syllogism. The word “hypothetical” here just means “conditional”: a statement of the form “if... then...” used to be called a hypothetical proposition, long before “hypothetical” came to mean “imagined” in everyday speech.

Unlike modus ponens, which needs P itself to be known true before it can hand you Q, hypothetical syllogism never asks whether P, Q or R is actually true. Its premises and its conclusion are all conditionals; whether the new conditional ever fires depends on facts this rule does not use.

Affirming the consequent, a fallacy

Affirming the consequent is the argument form

\begin{array}{l} P \to Q \\ Q \\ \hline \therefore\; P \end{array}

The second premise asserts the consequent Q instead of the antecedent, and the conclusion is the antecedent P. It is a formal fallacy: an argument form that is not valid, so the fault lies in the pattern and not in any particular sentence put into it.

The move treats P \to Q as if it also supplied its converse, Q \to P. It does not. A conditional and its converse are different statements, and one can be true while the other is false.

Intuition

Modus ponens: inside the circle

Picture every possible case as a point in a box, and each statement as the region of cases where it is true, as in Figure 1. Saying that “if P then Q” holds in every case puts the region for P wholly inside the region for Q: no point is in P and out of Q.

Figure 1Every case where P holds lies inside Q. Knowing P puts you in the shaded circle, and so inside Q.

The conditional alone does not tell you where you are. You might be inside P, or inside Q but outside P, or outside both. The second premise settles it: you are somewhere in P, the shaded circle. Wherever in it you are, you are inside Q. So Q holds.

Chaining: circles inside circles

“If P then Q” puts the P circle wholly inside the Q circle. “If Q then R” puts the Q circle wholly inside the R circle, as in Figure 2.

Figure 2P sits inside Q and Q sits inside R, so every case where P holds is already inside R.

Now look only at the shaded circle. It is inside Q, and all of Q is inside R, so the shaded circle is inside R: that is P \to R. The middle circle did its work and then disappears from the conclusion, which mentions only where the chain starts and where it ends.

The picture also shows why the order matters. P \to Q and R \to Q put both P and R inside Q, and two circles inside the same bigger circle can sit side by side, with neither inside the other.

Affirming the consequent: the room outside the inner circle

Draw P \to Q once more, with P inside Q, and this time shade all of Q, as in Figure 3.

Figure 3Knowing Q puts you somewhere in the shaded oval. That could be a point like A, where P holds, or a point like B, where it does not.

Being told Q places you somewhere in the shaded oval. It rules out the cases outside the oval, but it cannot tell a point like A from a point like B. With P: “the shape is a square” and Q: “the shape is a rectangle”, a 2-by-5 rectangle is a point like B. The move would be safe only if the oval had no room outside the circle, and the conditional P \to Q never says that.

Results

Modus ponens

Modus ponens is valid. Whenever both premises P \to Q and P are true, the conclusion Q is true.

Said as one statement, the conditional

\big( (P \to Q) \land P \big) \to Q

is true for every choice of truth values of P and Q.

Hypothetical syllogism

Hypothetical syllogism is valid. If P \to Q and Q \to R are both true, then P \to R is true.

P \to Q, \quad Q \to R \quad \Longrightarrow \quad P \to R

The same idea extends to a chain of any length. For any n \ge 2,

\begin{array}{l} P_1 \to P_2 \\ P_2 \to P_3 \\ \quad \vdots \\ P_{n-1} \to P_n \\ \hline \therefore\; P_1 \to P_n \end{array}

reached by applying the two-statement rule n - 2 times, once for each link after the first.

Affirming the consequent

Affirming the consequent is not valid. There is a truth assignment that makes both premises, P \to Q and Q, true and the conclusion P false.

From P \to Q and Q, nothing follows about P at all. One assignment satisfying both premises has P false and another has P true, so neither P nor \lnot P is a valid conclusion.

Valid is a promise about form

Validity is a promise about the form only. When a premise is false the promise is void, and the conclusion may be false too. Only a sound use, with premises that are actually true, guarantees the conclusion.

Why it is true

Modus ponens

An argument is valid when no assignment of truth values makes every premise true and the conclusion false. P and Q allow only four assignments, and the truth table for the conditional lists them all, with a column for every line of the argument:

Row	P	Q	P \to Q
1	T	T	T
2	T	F	F
3	F	T	T
4	F	F	T

The premises are P \to Q and P. Rows 3 and 4 have P false, so they are out. Row 2 has P true but P \to Q false, so it is out too. That leaves row 1, the only row where both premises are true, and in row 1, Q is true.

So no row has both premises true and the conclusion false, which is what valid means. The row-by-row test works for any argument; it is testing an argument with a truth table. The table also shows why both premises are needed: each rules out a row the other leaves standing.

Hypothetical syllogism

A conditional is false in exactly one case: its hypothesis true and its conclusion false. So to show P \to R is true, it is enough to rule out P true and R false happening together.

Suppose P \to Q and Q \to R are both true, and suppose, looking for a problem, that P is true and R is false. Since P \to Q is true and P is true, modus ponens gives Q true. Since Q \to R is true and Q is now true, modus ponens gives R true. That contradicts R being false. So P true and R false cannot both hold while the two premises are true, which is exactly what P \to R being true means.

The same fact shows up in a truth table, checking every combination of P, Q and R. First the two premises, in each of the eight rows:

Row	P	Q	R	{P \to Q}	{Q \to R}
1	T	T	T	T	T
2	T	T	F	T	F
3	T	F	T	F	T
4	T	F	F	F	T
5	F	T	T	T	T
6	F	T	F	T	F
7	F	F	T	T	T
8	F	F	F	T	T

Then the conclusion P \to R, in the same eight rows:

Row	P	R	{P \to R}
1	T	T	T
2	T	F	F
3	T	T	T
4	T	F	F
5	F	T	T
6	F	F	T
7	F	T	T
8	F	F	T

Rows 2 and 4 are the only rows where P \to R is false. In row 2 the premise Q \to R is false, and in row 4 the premise P \to Q is false, so the two premises are never true together there. In every row where P \to Q and Q \to R are both true, rows 1, 5, 7 and 8, P \to R is true as well. No row has the premises true and the conclusion false, which is what it means for a deduction rule to be valid.

Affirming the consequent

Go back to the four-row table for P \to Q above. The premises of affirming the consequent are P \to Q and Q, so only the rows where both columns Q and P \to Q read T matter: rows 1 and 3. In row 3, P is false. That single row, with both premises true and the conclusion false, is what makes the form invalid, since a valid form may have no such row. In row 1, P is true, which is why \lnot P does not follow either.

Row 3 is the sprinkler night: it did not rain (P false), the ground is wet (Q true), and “if it rained, the ground is wet” is still true. Modus ponens never meets row 3, because its second premise is P, and P is false there.

Worked examples

Example 1

Applying the rule

The premises are “If a whole number ends in the digit 0, then it is divisible by 5” and “The number 730 ends in the digit 0.” What does modus ponens let you conclude?

Solution

The first premise is about every whole number, so it holds in particular for 730: “if 730 ends in the digit 0, then 730 is divisible by 5.” Call the if-part P and the then-part Q.

The second premise asserts P exactly. So the two premises have the shape P \to Q, P, and modus ponens gives Q: 730 is divisible by 5.

Check. 730 \div 5 = 146, a whole number.

Example 2

Spotting the form

Which of these arguments are instances of modus ponens?

(a) x = 3 only if x^2 = 9. x = 3. Therefore x^2 = 9.

(b) A triangle is isosceles whenever it is equilateral. Triangle ABC is equilateral. Therefore triangle ABC is isosceles.

Solution

English has many ways to say “if P, then Q”, so first rewrite each conditional in that standard form.

(a) “P only if Q” says that P cannot hold without Q, which is “if P, then Q”. So the first premise is “if x = 3, then x^2 = 9”. The second premise is its if-part and the conclusion is its then-part. Modus ponens.

(b) “Q whenever P” also means “if P, then Q”: here, “if a triangle is equilateral, then it is isosceles”. The second premise is the if-part for triangle ABC, and the conclusion is the then-part for the same triangle. Modus ponens.

(c) The conditional is already in standard form, with if-part “n is a multiple of 6” and then-part “n is even”. But the second premise is the then-part. Not modus ponens. Nor is it valid: at n = 4 both premises are true, since 4 is even and the conditional holds for every n, yet 4 is not a multiple of 6. This invalid pattern is affirming the consequent, the subject of Examples 12 to 17.

Example 3

Using a theorem is modus ponens

The Pythagorean theorem says: if a triangle has a right angle, with legs a and b and hypotenuse c, then a^2 + b^2 = c^2.

(a) A right triangle has legs 5 and 12. Find its hypotenuse.

(b) A triangle has two sides of length 5 and 12, and none of its angles is a right angle. What does the theorem say about its third side?

Solution

(a) The theorem is a conditional, and this triangle satisfies its if-part: it has a right angle, with legs 5 and 12. By modus ponens its then-part holds for this triangle:

\begin{aligned} c^2 &= 5^2 + 12^2 \\ &= 25 + 144 = 169 \end{aligned}

A length is positive, so c = 13.

(b) Nothing. The if-part is false for this triangle, so there is no second premise and modus ponens cannot be used. (In fact the third side cannot be 13, but that needs a different result, the converse of the Pythagorean theorem.) This is why a theorem is used by checking its hypothesis first: that check supplies the premise P.

Example 4

A proof is modus ponens, line by line

Prove that the product of two odd whole numbers is odd.

Solution

The definition of “odd” supplies two conditionals, one in each direction:

if a whole number is odd, then it equals 2k + 1 for some whole number k;
if a whole number equals 2m + 1 for some whole number m, then it is odd.

Let a and b be odd. The first conditional’s if-part holds for a, so by modus ponens a = 2j + 1 for some whole number j. It holds for b as well, so b = 2k + 1 for some whole number k. The letters differ because nothing says a and b are equal.

Multiplying out,

\begin{aligned} ab &= (2j + 1)(2k + 1) \\ &= 4jk + 2j + 2k + 1 \\ &= 2(2jk + j + k) + 1. \end{aligned}

The number 2jk + j + k is a whole number, so ab meets the if-part of the second conditional with m = 2jk + j + k. Modus ponens once more: ab is odd.

Check. 7 \times 9 = 63 = 2 \times 31 + 1, and here j = 3, k = 4 give m = 24 + 3 + 4 = 31.

Every line feeds a case into a known conditional, or rewrites an expression by a rule that is itself a conditional (“if u = v, then uw = vw”). That is the anatomy of a direct proof.

Example 5

A chain of modus ponens

From the four premises

P \qquad P \to Q \qquad Q \to R \qquad R \to S

show that S follows.

Solution

Modus ponens may be used again on its own output. Write each statement on a numbered line, with the lines it comes from:

line	statement	reason
1	P	premise
2	P \to Q	premise
3	Q	modus ponens on lines 2 and 1
4	Q \to R	premise
5	R	modus ponens on lines 4 and 3
6	R \to S	premise
7	S	modus ponens on lines 6 and 5

Each use needs a conditional and its exact if-part, both already on the page, so Q \to R is useless until line 3 has produced Q. Joining two conditionals into a new one, P \to R, without knowing P at all, is a different rule, hypothetical syllogism, and the next six examples use it.

Example 6

A chain of everyday statements

If the alarm sounds, the sprinklers turn on. If the sprinklers turn on, the building manager’s phone gets a notification. What follows about the alarm and the notification?

Solution

Name the three statements: P is “the alarm sounds,” Q is “the sprinklers turn on,” and R is “the building manager’s phone gets a notification.” The two given facts are P \to Q and Q \to R, and the conclusion of the first is exactly the hypothesis of the second. Hypothetical syllogism combines them:

P \to R

In words: if the alarm sounds, the building manager’s phone gets a notification. The sprinklers, Q, do not appear in the conclusion at all; they were only the stepping stone.

Example 7

Extending the chain by one more link

A \to B, B \to C and C \to D are all true. What single conditional follows about A and D?

Solution

Apply the rule once to the first two: A \to B and B \to C share the middle statement B, so

A \to C

Now apply the rule again, this time to the new conditional A \to C and the premise C \to D, which share the middle statement C:

A \to D

Two applications of the same rule turn a chain of three links into one conditional connecting the two ends. The output of one application is a true conditional, so it may be fed straight into the next.

Example 8

A chain given out of order

X \to Y, W \to X and Y \to Z are all true, but they are not listed in an order that chains directly. What follows about W and Z?

Solution

Before chaining anything, find the order in which each hypothesis matches the previous conclusion. W appears only as a hypothesis, so W \to X starts the chain; X \to Y continues it, and Y \to Z finishes it:

W \to X, \quad X \to Y, \quad Y \to Z

Chaining the first two gives W \to Y. Chaining that with the third gives

W \to Z

The order the premises are written in never matters, since all of them are true at once. What matters is the order of the links.

Example 9

A chain of divisibility facts

Show that every multiple of 24 is a multiple of 3, by chaining conditionals about a whole number n.

Solution

Name four statements about n:

\begin{aligned} P&:\ n \text{ is a multiple of } 24 \\ Q&:\ n \text{ is a multiple of } 12 \\ R&:\ n \text{ is a multiple of } 6 \\ S&:\ n \text{ is a multiple of } 3 \end{aligned}

Each link is true because of how the divisors are related. If n = 24k for a whole number k, then n = 12(2k), so P \to Q. In the same way 12 = 6 \times 2 gives Q \to R, and 6 = 3 \times 2 gives R \to S. Chain the first two:

P \to R

Chain that with the third:

P \to S

So if n is a multiple of 24, then n is a multiple of 3, proved for every n at once without checking any particular number. This is the shape of a direct proof: small facts, each easy to justify, joined end to end.

Example 10

Turning a link around with the contrapositive

If the reservoir is low, a water ban is announced. If the car wash stays open, then no water ban has been announced. What follows about a low reservoir?

Solution

Let P be “the reservoir is low,” Q be “a water ban is announced,” and R be “the car wash closes.” The premises are

P \to Q, \qquad \lnot R \to \lnot Q

These do not chain as written: the first ends at Q, but the second starts at \lnot R. The second premise can be replaced by its contrapositive, Q \to R, because a conditional and its contrapositive are always true or false together. Now the premises read

P \to Q, \qquad Q \to R

and they share the middle statement Q exactly, so hypothetical syllogism gives

P \to R

If the reservoir is low, the car wash closes. Rewriting a link as an equivalent statement is always allowed, because it changes nothing about when the premises are true.

Example 11

A chain that breaks at a converse

For a whole number n: if n is a multiple of 10, then n is a multiple of 5; and if n is a multiple of 15, then n is a multiple of 5. Does it follow that every multiple of 10 is a multiple of 15?

Solution

Let P be “n is a multiple of 10,” Q be “n is a multiple of 5,” and R be “n is a multiple of 15.” The premises are P \to Q and R \to Q. Both end at Q; neither starts there. To chain them, the second link would have to be Q \to R, which is the converse of R \to Q, and a converse is a different statement. Here it is false: n = 5 is a multiple of 5 but not of 15.

So hypothetical syllogism does not apply, and the conclusion P \to R is in fact false. Take n = 10: it is a multiple of 10 and of 5, so both premises hold for it, but 10 \div 15 is not a whole number, so 10 is not a multiple of 15. The answer is no. Unlike the contrapositive in the previous example, the converse cannot stand in for a link. Reading a conditional backwards is the same mistake as affirming the consequent, the subject of the remaining examples.

Example 12

Naming the pieces and finding a counterexample

“If a number is divisible by 6, then it is divisible by 3. The number 15 is divisible by 3. Therefore 15 is divisible by 6.”

Solution

Let P be “the number is divisible by 6” and Q be “the number is divisible by 3”. The argument has the form P \to Q, Q, \therefore\ P, which is affirming the consequent.

The conditional is true, since 6 = 2 \cdot 3. The second premise is true: 15 = 3 \cdot 5. But 15 \div 6 = 2.5, so 15 is not divisible by 6. Both premises hold and the conclusion fails, exactly as in row 3 of the truth table for P \to Q.

Example 13

A true conclusion does not rescue the argument

“If a number is divisible by 4, then it is even. 8 is even. Therefore 8 is divisible by 4.”

Solution

Here P is “divisible by 4” and Q is “even”. The conclusion happens to be true: 8 \div 4 = 2.

Run the identical form on another number: “6 is even. Therefore 6 is divisible by 4.” Six is even, but 6 \div 4 is not a whole number, so this conclusion is false. The two arguments share one form, so the argument about 8 is invalid too: its conclusion is true for reasons the argument never gave.

Example 14

An algebraic version

“If x = 3, then x^2 = 9. x^2 = 9. Therefore x = 3.”

Solution

With P: “x = 3” and Q: “x^2 = 9”, this is affirming the consequent. The conditional is true, since 3^2 = 9. But x = -3 makes Q true and P false:

(-3)^2 = 9 \qquad\text{yet}\qquad -3 \ne 3

The same form hides inside solving an equation, as the boundary “It runs one way” below explains.

Example 15

A geometric version

“If a quadrilateral is a square, then it has four right angles. This quadrilateral has four right angles. Therefore it is a square.”

Solution

Let P: “the quadrilateral is a square” and Q: “it has four right angles”. Every square has four right angles, so P \to Q is true. A 2-by-6 rectangle has four right angles and is not a square, since 2 \ne 6. It makes Q true and P false: row 3 again.

Example 16

When the converse is proved separately

Let n be an integer, P: “n is divisible by 4”, and Q: “n^2 is divisible by 16”. Show that P \to Q is true. Then decide whether P can be concluded from Q.

Solution

If n is divisible by 4, write n = 4k for an integer k. Then n^2 = 16k^2, which is divisible by 16. So P \to Q is true.

From P \to Q and Q alone, concluding P is affirming the consequent, and the form is invalid here as everywhere. But this Q \to P can be proved on its own. Suppose n^2 is divisible by 16. Then n^2 is even, so n is even (an odd number times an odd number is odd). Write n = 2m. Then n^2 = 4m^2, and since 16 divides 4m^2, 4 divides m^2. So m^2 is even, m is even, m = 2j, and n = 4j. That proves Q \to P.

Now Q together with Q \to P gives P by modus ponens. For instance n^2 = 144 = 16 \cdot 9, and indeed n = \pm 12 = \pm 4 \cdot 3. The proof of Q \to P did the work; P \to Q played no part in reaching P. Statements that imply each other form a biconditional, and each direction needed its own proof.

Example 17

A mixed argument, checked step by step

“If Maria is at the library, she has her laptop. Maria has her laptop. If she has her laptop, she is doing homework. Therefore, Maria is at the library and is doing homework.”

Solution

Let P: “Maria is at the library”, Q: “she has her laptop”, R: “she is doing homework”. The premises are P \to Q, Q and Q \to R.

From Q and Q \to R, modus ponens gives R: she is doing homework. From P \to Q and Q, concluding P is affirming the consequent: she could have her laptop anywhere. “P and R” needs both parts, so it is not established.

Boundaries

Modus ponens

The second premise must be the if-part. From P \to Q and Q, nothing follows about P; that is affirming the consequent. From P \to Q and \lnot P, nothing follows about Q; that is denying the antecedent. From P \to Q and \lnot Q something does follow, namely \lnot P, but by a different rule, modus tollens.

It must be the if-part exactly. “If n is a multiple of 10, then n is even” together with “n is a multiple of 5” gives nothing: n = 15 makes both premises true and n odd. A premise that is close to the hypothesis, or about a different object, is not the hypothesis.

Valid is not the same as true. “If 2x + 3 = 11, then x = 5” is false, since 2x + 3 = 11 gives 2x = 8 and x = 4. Feed it the premise 2x + 3 = 11 and modus ponens delivers the false x = 5. The rule passes truth along; it does not check it.

It runs one way. Solving an equation by a chain of steps is modus ponens down the chain, so it proves that every solution is among the answers found, not that each answer is a solution. Concluding that it is would be affirming the consequent. Squaring both sides of an equation E to get S, for instance, makes every solution of E a solution of S but not the other way round: in Example 14, squaring x = 3 gives x^2 = 9, and -3 solves that too. So each answer is checked, by reversing the steps or by substituting it back into E (Exercise 12), and where a step does not reverse, an answer can be extraneous.

Hypothetical syllogism

The middle statement must match exactly, not just sound similar. “If a triangle is equilateral, then it is isosceles” and “if a triangle is a right isosceles triangle, then it has a 45^\circ angle” do not chain. The first ends at “isosceles,” the second starts at “right isosceles,” and those are different statements. Chaining them anyway would claim that an equilateral triangle has a 45^\circ angle, when all of its angles are 60^\circ.

Links run in the direction they point. P \to Q and R \to Q, both ending at Q, do not chain to anything. A link may be replaced by its contrapositive, which is equivalent to it, but never by its converse, which is not (Examples 10 and 11). Statements joined by “or” are combined by a different rule, disjunctive syllogism.

Chaining never decides whether P, Q or R is true. It only produces the new conditional P \to R. To get an actual fact out of the chain, a truth has to be fed in separately, the way modus ponens or modus tollens does.

A chain reaches only as far as its unbroken links. A single missing or mismatched link anywhere stops the chain at that point, however many links follow it.

Affirming the consequent

A further premise changes the form. Add Q \to P and the argument Q \to P, Q, \therefore\ P is modus ponens, which is valid. That premise must be established separately, as in Example 16; the conditional P \to Q never supplies it.

Invalidity is a fact about the form, not the conclusion. An instance can have a true conclusion (Example 13), even one that is always true (Exercise 40). What fails is the guarantee.

Deduction stops where evidence begins. Suppose P forces Q, so the cases with P are among the cases with Q, and \Pr(Q) > 0. Then \Pr(P \text{ and } Q) = \Pr(P), so

\Pr(P \mid Q) = \frac{\Pr(P)}{\Pr(Q)} \ge \Pr(P).

Learning Q never makes P less likely, and makes it strictly more likely when P was possible and Q was not already certain. So Q is evidence for P without being proof of it. A prediction that comes true supports a scientific theory in exactly this sense, and never proves it.

Where this goes next

Modus ponens is the step inside every direct proof, as Example 4 showed, and hypothetical syllogism is the quiet engine that joins those steps: a proof is usually a chain of “if... then...” facts laid end to end, each hypothesis matching the previous conclusion, until the chain reaches the statement being proved. A two-column proof in geometry puts the pattern on almost every line: the reason column names a conditional (a definition, a postulate, a theorem), the statement column records its then-part, and the if-part sits on an earlier line. Theorems that list several equivalent conditions are often proved with a cycle of links, P \to Q \to R \to P, which by chaining makes every one of them imply every other.

Once one end of a chain is known to be true or false, the chain hands off to modus ponens or to modus tollens, which runs a conditional backwards from a false then-part, to turn it into a fact. Disjunctive syllogism reasons from “or”. Longer arguments are these small valid steps put together.

Affirming the consequent and denying the antecedent, which argues from \lnot P, are the two invalid patterns that most resemble these valid ones. Row 3 is a single counterexample, and one is enough to break a form; confirming that a form is valid means checking every row, which testing an argument with a truth table makes routine for any number of premises, chains and all. A long argument can hide a single affirming step inside a chain (Exercise 44), and that check finds it.

Exercises

Drawing the conclusion

The premises are “If a whole number is divisible by 9, then it is divisible by 3” and “The number 432 is divisible by 9.” What does modus ponens let you conclude? Check the conclusion by division.
Write this argument in symbols, saying what P and Q stand for: “If the mixture is heated, the reaction speeds up. The mixture is heated. So the reaction speeds up.”
P \to Q is true and P is true. What is the truth value of Q?
The statement “if n is a multiple of 12, then n is a multiple of 4” is true for every whole number n. For which of n = 60, n = 64 and n = 70 can modus ponens be used, and what does it give?

Is it modus ponens?

Say whether each argument is an instance of modus ponens. If it is not, say what goes wrong.

If x > 5, then x^2 > 25. We know x \ge 5. So x^2 > 25.
14 is even only if 14^2 is even. 14 is even. So 14^2 is even.
If x > 5, then x > 3. x is not greater than 5. So x is not greater than 3.
Whenever a triangle has two equal sides, it has two equal angles. In triangle ABC, AB = AC. So triangle ABC has two equal angles.
If P, then Q. Q is false. So P is false.

Theorems and equations

A theorem says: if b^2 - 4ac < 0, then ax^2 + bx + c = 0 has no real solutions. Use it on x^2 + 2x + 5 = 0.
From the premises A, A \to B, B \to C and D \to E, which of B, C, D and E can be reached by modus ponens?
Solve 2(x - 3) = 10, writing each step as a conditional. What has the chain of modus ponens shown, and what settles that your answer really is a solution?
A theorem says: if the slopes of two lines multiply to -1, then the lines are perpendicular. Line \ell passes through (0, 1) and (2, 5), and line m through (0, 0) and (4, -2). What does the theorem let you conclude?

When a premise is false

“If a whole number is a multiple of 4, then it is a multiple of 8. 12 is a multiple of 4. Therefore 12 is a multiple of 8.” Is this modus ponens? Is the conclusion true, and if not, which premise fails?
Write an argument in the form of modus ponens whose conclusion is false. Which premise must be false, and why?

Chaining statements in words

If the trail floods, the race is canceled. If the race is canceled, the trophies are mailed instead of handed out. What follows about a flooded trail?
If Priya waters the seedling every day, it sprouts within a week. If a seedling sprouts within a week, it is a fast-growing variety. What follows about a seedling Priya waters every day?
If n is a multiple of 20, then n is a multiple of 10. If n is a multiple of 10, then n is a multiple of 5. What follows about a multiple of 20?
“If the invoice is late, the account is flagged. If the account is flagged, new orders are held.” Write the single conditional these two combine into, and name its hypothesis and its conclusion.

Symbolic chains

P \to Q and \lnot R \to \lnot Q are both true. What follows about P and R?
(A \land B) \to C and C \to (D \lor E) are both true. What follows?
\lnot P \to Q and Q \to R are both true. What follows?
P \to Q, R \to S and Q \to R are all true, listed in that order. What follows about P and S?
P \to Q, Q \to R and R \to P are all true. What conditional follows from Q to P, and what does that say about P and Q together?
A \to B, B \to C and D \to C are all true. Which of A \to C, D \to B and A \to D follow?
P_1 \to P_2, P_2 \to P_3, and so on up to P_9 \to P_{10}, are all true. What single conditional follows, and how many times is the two-statement rule applied to reach it?

Is the chain a valid deduction?

“If x = 3, then x^2 = 9. If x = -3, then x^2 = 9. Therefore, if x = 3, then x = -3.” Is this valid? If not, give a value of x that shows it.
Is P \to Q, R \to Q, therefore P \to R, a valid deduction? If not, give truth values for P, Q and R that make both premises true and the conclusion false.
Is P \to Q, Q \to R, therefore R \to P, a valid deduction? If not, give truth values for P, Q and R that make both premises true and the conclusion false.

Affirming the consequent: identifying the form

“If a shape is a rhombus, it has four equal sides. This shape has four equal sides. Therefore, this shape is a rhombus.” Name P and Q, and say which one is being affirmed.
“If Marcus studies, he passes the quiz. Marcus passed the quiz. Therefore, Marcus studied.” Name P and Q.
“If n is a multiple of 9, then n is a multiple of 3. n is a multiple of 3. Therefore n is a multiple of 9.” Name P and Q.
Write the general form of affirming the consequent using P and Q, and say which line is the invalid step.

Building a counterexample

Give a value of n that shows the argument in Exercise 32 is invalid: a multiple of 3 that is not a multiple of 9.
“If it is a golden retriever, then it is a dog. This animal is a dog. Therefore, it is a golden retriever.” Give a counterexample.
“If today is Saturday, then school is closed. School is closed today. Therefore, today is Saturday.” Give a reason school might be closed on a day that is not Saturday.
Row 3 of the truth table for P \to Q has P false and Q true. Explain in one sentence why this is exactly the row that defeats affirming the consequent.

Affirming the consequent in algebra and geometry

“If x = 5, then x^2 = 25. x^2 = 25. Therefore x = 5.” Find a value of x that shows this argument is invalid.
“If a number is divisible by 8, then it is divisible by 2. 6 is divisible by 2. Therefore 6 is divisible by 8.” Is the conclusion true? Is the argument valid? Explain the difference.
“If a quadrilateral is a square, then its diagonals are equal in length and bisect each other at right angles. This quadrilateral’s diagonals are equal in length and bisect each other at right angles. Therefore it is a square.” Is this argument valid as it stands?
“If two triangles are congruent, they have equal areas. These two triangles have equal areas. Therefore they are congruent.” Give two triangles with equal area that are not congruent.

Mixed arguments

“If Priya is on the swim team, she practices on Tuesdays. Priya practices on Tuesdays. If she practices on Tuesdays, she wakes up at 5 a.m. Therefore, Priya is on the swim team and wakes up at 5 a.m.” Which half of the conclusion follows validly, and which does not?
A kite is a quadrilateral with two distinct pairs of adjacent sides equal in length. For a quadrilateral ABCD, let P: “ABCD is a kite”, Q: “some two adjacent sides of ABCD are equal in length”, and R: “one of the diagonals of ABCD cuts off an isosceles triangle”. Given P \to Q, Q and Q \to R, which of R and P can you validly conclude? For the one you cannot, describe a quadrilateral that makes Q true and it false.
“If a plant is a cactus, it needs little water. If a plant needs little water, it can survive a drought. This plant can survive a drought. Therefore, this plant is a cactus.” Let P: it is a cactus, Q: it needs little water, R: it can survive a drought. Combine the first two lines into one conditional, name the rule that lets you do that, and then say which single step commits affirming the consequent.

Reasoning

Show that \big((P \to Q) \land P\big) \to Q is true in all four rows of its truth table.
A classmate says: “If I already know P \to Q is true, then I already know Q is true, so the second premise is wasted.” Explain what is wrong.
A proof establishes P \to Q. Explain why that proof alone does not establish Q, and what else a reader needs before modus ponens delivers Q.
Explain why hypothetical syllogism never needs you to know whether P is actually true.
P \to Q and Q \to R are both true. Explain why \lnot R \to \lnot P must be true as well.
For a whole number n: “if n is a multiple of 8, then n is even” and “if n is a multiple of 4, then n^2 is a multiple of 16” are both true. Explain why hypothetical syllogism does not combine them into “if n is a multiple of 8, then n^2 is a multiple of 16,” even though that statement is true, and name a link that would make the chain work.
Adapted from Levin’s Discrete Mathematics: An Open Introduction: explain why P_1 \to P_2, P_2 \to P_3, \dots, P_{n-1} \to P_n, therefore P_1 \to P_n, holds for a chain of any length n \ge 2, once it holds for a chain of two links.
Explain why finding one counterexample is always enough to show an argument form is invalid, while checking a hundred cases where the conclusion happens to be true is never enough to show the form is valid.
In Exercise 38, the value x = 5 makes the premise x^2 = 25 and the conclusion x = 5 both true. Explain why that does not make the argument valid.
Suppose you can prove separately that Q \to P is also true. Explain why concluding P from Q is now justified, and why this does not mean affirming the consequent has become a valid form.
Affirming the consequent starts from P \to Q and Q, and concludes P. Denying the antecedent starts from P \to Q and \lnot P, and concludes \lnot Q. Write out both conclusions, and explain in one sentence what the two fallacies have in common.

Answers

432 is divisible by 3. The second premise is the if-part of the first, applied to 432, so modus ponens gives the then-part. Check: 432 \div 3 = 144.
P is “the mixture is heated” and Q is “the reaction speeds up”. The argument is P \to Q, P, \therefore Q, which is modus ponens.
Q is true. The only row of the truth table with P and P \to Q both true is the row where Q is true.
Only n = 60, and it gives that 60 is a multiple of 4. 60 = 12 \times 5, so the if-part holds, and indeed 60 = 4 \times 15. Neither 64 nor 70 is a multiple of 12, so for them the if-part is false and modus ponens gives nothing, even though 64 happens to be a multiple of 4.
No. The second premise, x \ge 5, is not the if-part x > 5: it also allows x = 5. At x = 5 both premises are true, but x^2 = 25, which is not greater than 25, so the conclusion is false.
Yes. “P only if Q” means “if P, then Q”, and the second premise is that if-part. Indeed 14^2 = 196, which is even.
No. The second premise denies the if-part instead of asserting it. At x = 4 both premises are true, but the conclusion “4 is not greater than 3” is false. This is denying the antecedent.
Yes. “Q whenever P” means “if P, then Q”. AB = AC says that triangle ABC has two equal sides, which is the if-part for this triangle, so the then-part follows.
No. The second premise denies the then-part. The argument is valid, but by a different rule, modus tollens.
It has no real solutions. Here a = 1, b = 2 and c = 5, so b^2 - 4ac = 4 - 20 = -16 < 0. That is the if-part, so modus ponens gives the then-part.
B and C only. A with A \to B gives B, then B with B \to C gives C. Nothing gives D, so D \to E can never be used, and neither D nor E can be reached.
x = 8. If 2(x - 3) = 10, then x - 3 = 5, dividing by 2. If x - 3 = 5, then x = 8, adding 3. The chain shows that every solution equals 8. Substituting settles that 8 is a solution: 2(8 - 3) = 10.
The lines are perpendicular. The slope of \ell is \displaystyle \frac{5 - 1}{2 - 0} = 2 and the slope of m is \displaystyle \frac{-2 - 0}{4 - 0} = -\frac{1}{2}. Their product is \displaystyle 2 \times \left(-\frac{1}{2}\right) = -1, which is the if-part, so modus ponens gives the then-part.
It is modus ponens, so it is valid, but the conclusion is false: 12 \div 8 = 1.5. Since the form is valid, a premise must be false. The second one is true (12 = 4 \times 3), so the conditional is false, and 12 itself is the case that breaks it.
For example: “If a number is greater than 2, then it is greater than 10. 5 is greater than 2. So 5 is greater than 10.” Because the form is valid, true premises would force a true conclusion, so some premise is false. Here it is the conditional, and 5 itself breaks it.
If the trail floods, the trophies are mailed instead of handed out. Let P = “the trail floods,” Q = “the race is canceled,” R = “the trophies are mailed instead of handed out.” The two facts are P \to Q and Q \to R, so hypothetical syllogism gives P \to R.
If Priya waters the seedling every day, it is a fast-growing variety. The two facts share the middle statement “it sprouts within a week,” so they chain straight through it.
If n is a multiple of 20, then n is a multiple of 5. The two facts share “multiple of 10” as the middle statement.
If the invoice is late, new orders are held. The hypothesis is “the invoice is late” and the conclusion is “new orders are held”; “the account is flagged” was only the middle statement.
P \to R. The contrapositive of \lnot R \to \lnot Q is Q \to R, which is equivalent to it. Chaining P \to Q with Q \to R gives P \to R.
(A \land B) \to (D \lor E). The middle statement C matches exactly; the ends being compound statements changes nothing.
\lnot P \to R. The rule does not care that the hypothesis is itself a negation; \lnot P is just the statement playing the role of the first link’s hypothesis.
P \to S. Reordered, the chain reads P \to Q, Q \to R, R \to S, so two applications of the rule give P \to S.
Q \to P, by chaining Q \to R with R \to P. Together with the premise P \to Q, this means P and Q are always true or false together: P \leftrightarrow Q. (The same argument shows all three statements are equivalent.)
Only A \to C, by chaining A \to B with B \to C. D \to B does not follow: with A and B false and C and D true, all three premises are true but D \to B is false. A \to D does not follow: with A, B and C true and D false, the premises are true but A \to D is false.
P_1 \to P_{10}, after 8 applications. There are 9 links, and each application merges two conditionals into one, so going from 9 down to 1 takes 9 - 1 = 8 applications, the n - 2 of the Results with n = 10.
Not valid. Take x = 3: the first premise holds since 3^2 = 9, the second holds because its hypothesis x = -3 is false, but the conclusion is false because 3 \ne -3. Both premises end at x^2 = 9, so there is no chain.
No. P = \text{T}, Q = \text{T}, R = \text{F} makes P \to Q true and R \to Q true, but P \to R false. Both premises end at Q, rather than one’s conclusion being the other’s hypothesis.
No. P = \text{F}, Q = \text{T}, R = \text{T} makes P \to Q true and Q \to R true, but R \to P false. Hypothetical syllogism gives P \to R, not R \to P; nothing here reverses the direction.
P: “the shape is a rhombus”, Q: “the shape has four equal sides”. The consequent Q is affirmed, and P is concluded from it.
P: “Marcus studies”, Q: “Marcus passes the quiz”.
P: “n is a multiple of 9”, Q: “n is a multiple of 3”.
P \to Q, Q, \therefore\ P. The last line, concluding P from the first two, is the invalid step.
n = 6. It is a multiple of 3 (6 \div 3 = 2) but not of 9 (6 \div 9 is not a whole number), so both premises hold and the conclusion fails.
Any dog that is not a golden retriever, such as a poodle.
A snow day, or a public holiday. School can be closed for reasons that have nothing to do with the day of the week.
In that row both premises, P \to Q and Q, are true while P, the conclusion, is false, and one such row is exactly what invalidity means.
x = -5. (-5)^2 = 25, so the premise x^2 = 25 holds, but -5 \ne 5.
The conclusion is false: 6 \div 8 is not a whole number, so 6 is not divisible by 8. The argument is invalid because its form is affirming the consequent; the false conclusion only makes that easy to see.
Not valid as it stands: from P \to Q and Q alone, concluding P is affirming the consequent. The conclusion is in fact always true here, because the converse is a separate theorem (diagonals that bisect each other give a parallelogram, equal ones make it a rectangle, perpendicular ones make it a rhombus), but the argument never cites it.
A right triangle with legs 3 and 4 has sides 3, 4, 5 and area \displaystyle \frac{1}{2}(3)(4) = 6. A right triangle with legs 2 and 6 has sides \displaystyle 2, 6, 2\sqrt{10} and area \displaystyle \frac{1}{2}(2)(6) = 6. Equal areas, but congruent triangles have the same three side lengths, and these do not.
“She wakes up at 5 a.m.” follows validly, from Q and Q \to R by modus ponens. “She is on the swim team” does not follow: that step affirms the consequent, using P \to Q and Q to conclude P.
R follows validly from Q and Q \to R by modus ponens. P does not: concluding P from P \to Q and Q is affirming the consequent. A quadrilateral with AB = AD = 5, BC = 3 and CD = 7 (it exists: take diagonal BD = 6, which fits both triangles ABD and CBD) has one pair of equal adjacent sides and no second pair, so Q is true and P is false.
P \to Q and Q \to R combine into P \to R by hypothetical syllogism, which is valid. The remaining step, concluding P from P \to R and R, is one application of affirming the consequent.
The if-part (P \to Q) \land P is true only in the row where P and Q are both true (Exercise 3), and there Q is true, so the whole conditional is true. In the other three rows the if-part is false, and a conditional with a false if-part is true. So all four rows are true.
P \to Q is true in three rows, and in one of them, P false and Q false, Q is false. So the conditional alone leaves Q open. The premise P is what removes that row. Knowing “if n is a multiple of 10, then n is even” does not tell you whether n is even until you know something about n.
A proof of P \to Q shows that Q holds in every case where P holds, and says nothing about whether P holds. The reader must also establish P for the case at hand; then modus ponens delivers Q. This is why a theorem is used by first checking its hypothesis (Example 3).
Hypothetical syllogism only produces the new conditional P \to R from two others. It asks whether the two given conditionals are true, never whether P, Q or R is, and its conclusion is a conditional, which says nothing about whether P happens.
Chaining gives P \to R. Its contrapositive is \lnot R \to \lnot P, and a conditional and its contrapositive are always true together, so \lnot R \to \lnot P is true. (Equally: chain the contrapositives \lnot R \to \lnot Q and \lnot Q \to \lnot P.)
The first conditional ends at “n is even” and the second starts at “n is a multiple of 4,” which are different statements, and being even does not force being a multiple of 4: n = 6 is even but not a multiple of 4, and 6^2 = 36 is not a multiple of 16. A true conclusion does not make the chain valid. Replacing the first link with “if n is a multiple of 8, then n is a multiple of 4” (true, since 8k = 4(2k)) gives a matching middle statement, and then the chain works.
Once the rule holds for a chain of two links, apply it to the first two premises to get P_1 \to P_3, then again to that result and the next premise to get P_1 \to P_4, and so on down the chain, one application for each further link, until P_1 \to P_n is reached. Each step turns a true chain one link shorter, which is the idea behind a proof by induction on n.
Validity requires that no case has the premises true and the conclusion false, so one such case disproves it. A hundred good cases say nothing about a case not yet tried.
Validity asks for the conclusion in every case where the premises hold, not in some. The value x = -5 is a case where the premise x^2 = 25 holds and the conclusion x = 5 fails, so the argument is invalid whatever x = 5 does.
With Q \to P proved, Q and Q \to P give P by modus ponens, so the conclusion is justified. But the justification is the separately proved Q \to P; from P \to Q and Q alone, the form still has row 3 as a counterexample.
Affirming the consequent concludes P. Denying the antecedent concludes \lnot Q. Both use the conditional P \to Q as though it also gave its converse Q \to P, a statement it does not imply.