2600 words | 1.2 hours estimated reading time | chapter 8 source

8.1 A historical example

In his book, The Two New Sciences,^[10] Galileo Galilea (1564-1642) gives several arguments meant to demonstrate that there can be no such thing as actual infinities or actual infinitesimals. One of his arguments can be reconstructed in the following way. Galileo proposes that we take as a premise that there is an actual infinity of natural numbers (the natural numbers are the positive whole numbers from 1 on):

{1, 2, 3, 4, 5, 6, 7, ….}

He also proposes that we take as a premise that there is an actual infinity of the squares of the natural numbers.

{1, 4, 9, 16, 25, 36, 49, ….}

Now, Galileo reasons, note that these two groups (today we would call them “sets”) have the same size. We can see this because we can see that there is a one-to-one correspondence between the two groups.

{1,	2,	3,	4,	5,	6,	7, ….}

{1,	4,	9,	16,	25,	36,	49, ...}

If we can associate every natural number with one and only one square number, and if we can associate every square number with one and only one natural number, then these sets must be the same size. But wait a moment, Galileo says. There are obviously very many more natural numbers than there are square numbers. That is, every square number is in the list of natural numbers, but many of the natural numbers are not in the list of square numbers. The following numbers are all in the list of natural numbers but not in the list of square numbers.

{2, 3, 5, 6, 7, 8, 10, ….}

So, Galileo reasons, if there are many numbers in the group of natural numbers that are not in the group of the square numbers, and if there are no numbers in the group of the square numbers that are not in the naturals numbers, then the natural numbers is bigger than the square numbers. And if the group of the natural numbers is bigger than the group of the square numbers, then the natural numbers and the square numbers are not the same size. We have reached two conclusions: the set of the natural numbers and the set of the square numbers are the same size; and, the set of the natural numbers and the set of the square numbers are not the same size. That’s contradictory. Galileo argues that the reason we reached a contradiction is because we assumed that there are actual infinities. He concludes, therefore, that there are no actual infinities.

8.2 Indirect proofs

Our logic is not yet strong enough to prove some valid arguments. Consider the following argument as an example.

(P→(QvR))

¬Q

¬R

_____

¬P

This argument looks valid. By the first premise we know: if P were true, then so would (Q v R) be true. But then either Q or R or both would be true. And by the second and third premises we know: Q is false and R is false. So it cannot be that (Q v R) is true, and so it cannot be that P is true. We can check the argument using a truth table. Our table will be complex because one of our premise is complex.

Truth Table
				premise	premise	premise	conclusion
P	Q	R	(QvR)	(P→(QvR))	¬Q	¬R	¬P
T	T	T	T	T	F	F	F
T	T	F	T	T	F	T	F
T	F	T	T	T	T	F	F
T	F	F	F	F	T	T	F
F	T	T	T	T	F	F	T
F	T	F	T	T	F	T	T
F	F	T	T	T	T	F	T
F	F	F	F	T	T	T	T

In any kind of situation in which all the premises are true, the conclusion is true. That is: the premises are all true only in the last row. For that row, the conclusion is also true. So, this is a valid argument. But take a minute and try to prove this argument. We begin with

$\fitchprf{ \pline[1.]{(P \lif (Q \lor R))}[premise]\\ \pline[2.]{\lnot Q}[premise]\\ \pline[3.]{\lnot R}[premise] } { }$

And now we are stopped. We cannot apply any of our rules. Here is a valid argument that we have not made our reasoning system strong enough to prove. There are several ways to rectify this problem and to make our reasoning system strong enough. One of the oldest solutions is to introduce a new proof method, traditionally called “reductio ad absurdum”, which means a reduction to absurdity. This method is also often called an “indirect proof” or “indirect derivation”. The idea is that we assume the denial of our conclusion, and then show that a contradiction results. A contradiction is shown when we prove some sentence Ψ, and its negation ¬Ψ. This can be any sentence. The point is that, given the principle of bivalence, we must have proven something false. For if Ψ is true, then ¬Ψ is false; and if ¬Ψ is true, then Ψ is false. We don’t need to know which is false (Ψ or ¬Ψ); it is enough to know that one of them must be. Remember that we have built our logical system so that it cannot produce a falsehood from true statements. The source of the falsehood that we produce in the indirect derivation must, therefore, be some falsehood that we added to our argument. And what we added to our argument is the denial of the conclusion. Thus, the conclusion must be true. The shape of the argument is like this:

$\fitchctx{ \subproof{\pline{\lnot \phi}}{ \ellipsesline\\ \pline{\psi}\\ \pline{\lnot \psi} } \fpline{\phi} }$

Traditionally, the assumption for indirect derivation has also been commonly called “the assumption for reductio”. As a concrete example, we can prove our perplexing case.

$\fitchprf{\pline[1.]{(P \lif (Q \lor R))} [premise]\\ \pline[2.]{\lnot Q} [premise]\\ \pline[3.]{\lnot R} [premise] } { \subproof{\pline[4.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[5.]{P}[double negation, 4]\\ \pline[6.]{(Q \lor R)}[modus ponens, 1, 5]\\ \pline[7.]{R}[modus tollendo ponens, 6, 2]\\ \pline[8.]{\lnot R}[repeat, 3]\\ } \pline[9.]{\lnot P}[indirect derivation, 4-8] }$

We assumed the denial of our conclusion on line 4. The conclusion we believed was correct was ¬P, and the denial of this is ¬¬P. In line 7, we proved R. Technically, we are done at that point, but we would like to be kind to anyone trying to understand our proof, so we repeat line 3 so that the sentences R and ¬R are side by side, and it is very easy to see that something has gone wrong. That is, if we have proven both R and ¬R, then we have proven something false. Our reasoning now goes like this. What went wrong? Line 8 is a correct use of repetition; line 7 comes from a correct use of modus tollendo ponens; line 6 from a correct use of modus ponens; line 5 from a correct use of double negation. So, we did not make a mistake in our reasoning. We used lines 1, 2, and 3, but those are premises that we agreed to assume are correct. This leaves line 4. That must be the source of my contradiction. It must be false. If line 4 is false, then ¬P is true. Some people consider indirect proofs less strong than direct proofs. There are many, and complex, reasons for this. But, for our propositional logic, none of these reasons apply. This is because it is possible to prove that our propositional logic is consistent. This means, it is possible to prove that our propositional logic cannot prove a falsehood unless one first introduces a falsehood into the system. (It is generally not possible to prove that more powerful and advanced logical or mathematical systems are consistent, from inside those systems; for example, one cannot prove in arithmetic that arithmetic is consistent.) Given that we can be certain of the consistency of the propositional logic, we can be certain that in our propositional logic an indirect proof is a good form of reasoning. We know that if we prove a falsehood, we must have put a falsehood in; and if we are confident about all the other assumptions (that is, the premises) of our proof except for the assumption for indirect derivation, then we can be confident that this assumption for indirect derivation must be the source of the falsehood. A note about terminology is required here. The word “contradiction” gets used ambiguously in most logic discussions. It can mean a situation like we see above, where two sentences are asserted, and these sentences cannot both be true. Or it can mean a single sentence that cannot be true. An example of such a sentence is (P^¬P). The truth table for this sentence is:

P	¬P	(P ^ ¬P)
T	F	F
F	T	F

Thus, this kind of sentence can never be true, regardless of the meaning of P. To avoid ambiguity, in this text, we will always call a single sentence that cannot be true a “contradictory sentence”. Thus, (P^¬P) is a contradictory sentence. Situations where two sentences are asserted that cannot both be true will be called a “contradiction”.

8.3 Our example, and other examples

We can reconstruct a version of Galileo’s argument now. We will use the following key.

P: There are actual infinities (including the natural numbers and the square numbers).

Q: There is a one-to-one correspondence between the natural numbers and the square numbers.

R: The size of the set of the natural numbers and the size of the set of the square numbers are the same.

S: All the square numbers are natural numbers.

T: Some of the natural numbers are not square numbers.

U: There are more natural numbers than square numbers.

With this key, the argument will be translated:

(P→Q)

(Q→R)

(P→(S^T))

((S^T)→U)

(U→¬R)

______

¬P

And we can prove this is a valid argument by using indirect derivation:

$\fitchprf{\pline[1.]{(P \lif Q)} [premise]\\ \pline[2.]{(Q \lif R)} [premise]\\ \pline[3.]{(P \lif (S \land T))} [premise]\\ \pline[4.]{((S \land T) \lif U)}[premise]\\ \pline[5.]{(U \lif \lnot R)} [premise] } { \subproof{\pline[6.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[7.]{P}[double negation, 6]\\ \pline[8.]{Q}[modus ponens, 1, 7]\\ \pline[9.]{R}[modus ponens, 2, 8]\\ \pline[10.]{(S \land T)}[modus ponens, 3, 7]\\ \pline[11.]{U}[modus ponens, 4, 10]\\ \pline[12.]{\lnot R}[modus ponens, 5, 11]\\ \pline[13.]{R}[repeat, 9] } \pline[14.]{\lnot P}[indirect derivation, 6-13] }$

On line 6, we assumed ¬¬P because Galileo believed that ¬P and aimed to prove that ¬P. That is, he believed that there are no actual infinities, and so assumed that it was false to believe that it is not the case that there are no actual infinities. This falsehood will lead to other falsehoods, exposing itself. For those who are interested: Galileo concluded that there are no actual infinities but there are potential infinities. Thus, he reasoned, it is not the case that all the natural numbers exist (in some sense of “exist”), but it is true that you could count natural numbers forever. Many philosophers before and after Galileo held this view; it is similar to a view held by Aristotle, who was an important logician and philosopher writing nearly two thousand years before Galileo. Note that in an argument like this, you could reason that not the assumption for indirect derivation, but rather one of the premises was the source of the contradiction. Today, most mathematicians believe this about Galileo’s argument. A logician and mathematician named Georg Cantor (1845-1918), the inventor of set theory, argued that infinite sets can have proper subsets of the same size. That is, Cantor denied premise 4 above: even though all the square numbers are natural numbers, and not all natural numbers are square numbers, it is not the case that these two sets are of different size. Cantor accepted however premise 2 above, and, therefore, believed that the size of the set of natural numbers and the size of the set of square numbers is the same. Today, using Cantor’s reasoning, mathematicians and logicians study infinity, and have developed a large body of knowledge about the nature of infinity. If this interests you, see section 17.5.

Let us consider another example to illustrate indirect derivation. A very useful set of theorems are today called “De Morgan’s Theorems”, after the logician Augustus De Morgan (1806–1871). We cannot state these fully until chapter 9, but we can state their equivalent in English: DeMorgan observed that ¬(PvQ) and (¬P^¬Q) are equivalent, and also that ¬(P^Q) and (¬Pv¬Q) are equivalent. Given this, it should be a theorem of our language that (¬(PvQ)→(¬P^¬Q)). Let’s prove this.

The whole formula is a conditional, so we will use a conditional derivation. Our proof must thus begin:

$\fitchprf{} { \subproof{\pline[1.]{\lnot (P \lor Q)}[assumption for conditional derivation]}{ } }$

To complete the conditional derivation, we must prove (¬P^¬Q). This is a conjunction, and our rule for showing conjunctions is adjunction. Since using this rule might be our best way to show (¬P^¬Q), we can aim to show ¬P and then show ¬Q, and then perform adjunction. But, we obviously have very little to work with—just line 1, which is a negation. In such a case, it is typically wise to attempt an indirect proof. Start with an indirect proof of ¬P.

We now need to find a contradiction—any contradiction. But there is an obvious one already. Line 1 says that neither P nor Q is true. But line 3 says that P is true. We must make this contradiction explicit by finding a formula and its denial. We can do this using addition.

To complete the proof, we will use this strategy again.

$\fitchprf{} { \subproof{\pline[1.]{\lnot (P \lor Q)}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[3.]{P}[double negation, 2]\\ \pline[4.]{(P \lor Q)}[addition, 3]\\ \pline[5.]{\lnot (P \lor Q)}[repeat, 1] } \pline[6.]{\lnot P}[indirect derivation 2-5]\\ \subproof{\pline[7.]{\lnot \lnot Q}[assumption for indirect derivation]}{ \pline[8.]{Q}[double negation, 7]\\ \pline[9.]{(P \lor Q)}[addition, 8]\\ \pline[10.]{\lnot (P \lor Q)}[repeat, 1] } \pline[11.]{\lnot Q}[indirect derivation 7-10]\\ \pline[12.]{(\lnot P \land \lnot Q)}[adjunction, 6, 11] } \pline[13.]{(\lnot (P \lor Q) \lif (\lnot P \land \lnot Q))}[conditional derivation 1-12] }$

We will prove De Morgan’s theorems as problems for chapter 9. Here is a general rule of thumb for doing proofs: When proving a conditional, always do conditional derivation; otherwise, try direct derivation; if that fails, then, try indirect derivation.

[10] This translation of the title of Galileo’s book has become the most common, although a more literal one would have been Mathematical Discourses and Demonstrations. Translations of the book include Drake (1974).