Don't Understand Mechanism behind Proof by Contradiction

Question

I believe there are two kinds of proof by contradictions, one which I understand, and another one which I have some questions. I'll begin with the first one.

1st CASE

Suppose I can logically show that from a premise A, a conclusion B follows (that is if A is true then B is true). However, I previously know that B is false. Therefore, I can conclude that A cannot be true. For example, when proving that there are infinite primes I show that:

If there is a finite number of primes (A) then 1 can be divided by a prime (B). I know from previously established facts that B is false, therefore A cannot be true.

2nd CASE

However, suppose that from a premise A, I can show that the conclusion not-A follows.

For example, when proving $\sqrt{2}$ is irrational I do the following:

If $\sqrt{2}$ can be written as an irreducible fraction (A) then it is not written as an irreducible fraction (not-A).

In this case, I cannot see how we can deduce that A must be false, since I cannot be certain that the consequent (not-A) is either true or false, since its truth value depends on my assumption.

Perhaps I could argue that $\sqrt{2}$ being rational implies that math is inconsistent, and then, since we know that math is consistent, we can conclude that $\sqrt{2}$ is not rational. But then we would also need to justify why we "know" or "assume" that math is consitent.

Answer 1

For the second case, the argument runs by cases. Roughly, it is:

P1. $A\lor \neg A$, by the principle of the excluded middle.

P2. $A \implies \neg A$, by assumption.

By applying P2 to P1, we have:

L3. $\neg A \lor \neg A$

And by disjunction reduction:

C4. $\neg A$

QED

Answer 2

A long answer

Here I address the second part of your question dealing with the consistency of math. For the first part, I like the answer by Lemmon.

All arguments by contradiction, as well as all proofs, morally (not formally) assume that math is consistent. Many times I thought in my mind, while writing a proof, something like

"...therefore, either math is broken, or the theorem is proved. Q.e.d. $\square$",

as if math is not consistent, in principle you can prove that the same statement you have just proved is false as well.

But the truth, and my short answer, is that proofs do not formally rely on the consistency of math, not even in practice. I think that to discuss about these subtleties one needs some care to avoid misunderstandings, so the answer is going to be a bit long. I will first try to explain the basic concepts involved in my argument and then go straight to what I think is the source of your confusion. Along the way I will come back to the irrationality of $\sqrt 2$ several times.

---

1. How to think of proofs and axioms.

First, I think a good way to think about this is to include your axioms in the hypotheses of your theorem. For instance, if you want to prove $A$, then you are not simply saying $$ A \text{ is true}. $$ What you really mean is $$ \text{ZF}\implies A, $$ where "$A$" is the statement you want to prove, and where $ZF$ is the set of axioms that make your mathematical theory (Zermelo-Fraenkel, or whatever). This does not a priori exclude the fact that $ZF$ is inconsistent, as if $ZF$ is inconsistent, the conjunction of its axioms is logically false, and roughly speaking, something false implies anything. This says “If you assume that $ZF$ is true, then $A$ is true”.

---

2. How a proof by contradiction works.

Second, let's look at your proof (second kind). If you don't make use of the above formalism, a proof by contradiction goes like this. We call "$\neg A$" the negation of the statement $A$ (I exchange the roles of $A$ and $\neg A$ in your proof for the sake of clarity, so what we want to prove is the statement $A$).

Theorem. $A$ Is true.

Proof (by contradiction). Assume that $\neg A$ is true (this of course is either a true statement or a false statement). Then…

(... body of the proof ...)

… I show that $\neg A \implies A$. Since it is simply false that both $A$ and $\neg A$ are true (by the principle of non-contradiction), it must be $\neg A$ is false (that is, by the principle of the excluded middle, $A$ is true). $\square$

(this proof is longer that it should, you don't really need the principle of non-contradiction, but I write it like this to clarify your doubts; check the answer by Lemmon or the comment by LuckyJollyMoments). If you let $ZF$ enter the party, which makes things a bit more complicated but closer to reality, the proof by contradiction then sounds like the following.

Theorem. $ZF\implies A$.

Proof (by contradiction). Assume that $ZF$ and $\neg A$ are true. Then…

(... body of the proof ...)

… I show that $ZF$ and $\neg A$ together imply $A$. Since it is simply false that both $A$ and $\neg A$ are true (by the principle of non-contradiction), it must be either $ZF$ is false (and/or it has a contradiction inside), or $\neg A$ is false (that is, by the principle of the excluded middle, $A$ is true). This then implies $ZF\implies A$. $\square$

Some comments.

1. The first ($ZF$ is false) is something you exclude in practice, since you take for granted that ZF is true (and it is consistent). This is why, essentially, you are proving that $A$ is true. But on the formal level, you are not excluding that $ZF$ is false. You are simply proving that your axioms $ZF$ imply $A$, that is, “If you assume that $ZF$ is true, then $A$ is true”. You don’t need to know a priori that the axioms are “true” (whatever that means in the absolute sense) or on their consistency to make that work. The proof I wrote above works just fine and does not care on whether $ZF$ is a nice set of axioms or not.

2. Another way of looking at it: nothing excludes a priori that $ZF\implies A$ and $ZF\implies\neg A$, it's just that if both are true then $ZF$ must be false from a logical point of view. If you want to work with the set of axioms $ZF$, it's basically like you are making the universal assumption that $ZF$ is true all the time. Since inconsistency also implies falseness from a logical point of view, then as a student/mathematician/human being, you really need to hope that $ZF$ is consistent if there is no way of proving it, because if it isn't consistent, you are simply proving that something false implies something else (not very useful; if donkeys fly, then everything is true). But again, this does not play a role at all in the proof of $ZF\implies A$: even if you prove (or you simply don’t know) that $ZF\implies \neg A$, it is still possible to prove that $ZF\implies A$, either directly or by contradiction.

3. I stress again the fact that in arguments like the one you wrote about $\sqrt 2$ being irrational, you don’t use that your axioms are consistent, you simply use the laws of logic, like those of excluded middle and of non-contradiction (see the last part). As I wrote in the previous comment, for how unlikely, it could also be the case that there exists a proof of $\sqrt 2$ being rational as well that mathematicians have overlooked so far (this would imply that the axioms of math are inconsistent). But that would not invalidate or create an obstruction for the proof that $\sqrt 2$ is irrational.

To conclude this part, my point is that, as your intuition suggests, you can think about how proofs by contradiction work from a pure logical point of view, and I wanted to give you an idea on how this works.

---

3. An example: proof by contradiction relying on some of the axioms.

Assume you have a set of axioms $X$ with which you can prove $A$ by contradiction, and a set of axioms $Y$ that can prove $\neg A$, still by contradiction. Consider the set of axioms $Z=X\cup Y$ (I am using the set notation improperly, but that’s to make things simple). With the axioms $Z$, you can prove $A$ by contradiction, and you can prove $\neg A$ by contradiction. Of course, $Z$ is inconsistent.

The proof by contradiction of the statement $\neg A$, for instance, works just fine: you simply forget for a moment about the axioms $X$ and use the axioms of $Y$ to prove $\neg A$. This is a crucial fact to understand: when you prove something in math, you don’t need to use all the axioms; maybe you only use some of them. In the body of the proof at some point you will say

“… so, we show that $A$ implies $\neg A$ assuming $Z$ is true. But it is not possible that $A$ and $\neg A$ are true, so it must be $ A$ is false, that is, $\neg A$ is true…”

So, in the body of the proof you will say that “$A$ is false” (e.g., “it is not true that $\sqrt 2$ is rational”)… In our example, though, if you do the same thing and use the axioms $X$ instead, you can prove that $Z$ proves $A$, so that in a sense, “$A$ is true”. This might be a little confusing, but it is just a consequence of the fact that when you prove something, you only use some of the axioms, not necessarily all of them. Some statement $A$ could be a consequence of some axioms $X$, and go in conflict with some axioms $Y$, where $X$ and $Y$ are both part of your mathematical axioms $Z$.

Now that you have been reading this answer for a while, you probably know how to adjust things: what you really mean when saying “$A$ is false” is “$A$ is false, assuming $Z$ is true”. That is, “$Z\implies \neg A$”, or, “from my axioms (possibly only some of them) it follows that $\sqrt 2$ is not rational”. That does not exclude that there exists a proof somewhere of $Z$ implies $\neg A$, that is, with some axioms of $Z$ you prove $A$ and with some other axioms of $Z$ you prove $\neg A$.

This situation is similar to a law system in which you have two laws that contradict each other (like, “killing a person is always a crime” and “defending oneself from aggressions is never a crime”). Two judges can reach incompatible verdicts on the same case if they choose to follow different laws. Does that mean that the two verdicts are “wrong”? No, both verdicts are a legitimate consequence of some laws. The problem of course is that the law system is broken, so a judge could choose the law he/she likes the most to turn things in the more convenient way for him/her.

A key point. This fact can happen regardless of the kind of proofs of $A$ and $\neg A$ are structured, being them by contradiction or not. A proof by contradiction could still rely on some of the axioms, not necessarily all of them. For instence, to prove $A$, you simply need to show that $\neg A$ goes into conflict with some of the axioms.

---

4. Final remark: difference between logic and math.

Finally, also to sum things up, I make a remark on the principle of non-contradiction, where I think your confusion lies. In Classical logic, the law of non-contradiction always holds, so that a statement cannot be both true and false. In logical symbols, $\neg(A\wedge\neg A)$. This however, roughly speaking, "does not apply to mathematics". That is, in principle, it could be that a mathematical fact is proved to be both false and true from a set of mathematical axioms $ZF$ (in symbols, both $ZF\implies A$ and $ZF\implies \neg A$). This of course would imply that $ZF$ is inconsistent. But (and here is the key point) in the proof I wrote above, and in the one you would write to prove that $\sqrt 2$ is irrational, you make use of the "logical version" of the principle of non-contradiction, not the "mathematical one" (which only holds if math is consistent). So, nothing excludes that math is inconsistent, and that with the same axioms you can prove that $\sqrt 2$ is rational as well (that would be quite fun for Pithagoras), but this is not a problem at all (and does not play any role) in the proof itself of the irrationality. If you go back and read the proof I wrote above, the only thing I use is logic to show that $ZF\implies A$, and in logic something simply cannot be both true and false.

(Additional remark: note that I wrote the proof above using this principle just for the sake of showing you that it is not a problem to use it. To be fair, you can write a proof without the principle of non-contradiction to begin with (see the answer by Lemmon), which makes a much shorter answer to your doubts. But I still thought there was much more to be said, that is the reason of my long answer.)

Analogously, the law of excluded middle always holds in logic, that is, "$A\vee\neg A$", either $A$ is true or $A$ is false. I have used it in the proof above, and this is necessary to conclude. Although the law of excluded middle holds in formal logic, "it doesn't necessarily hold in math". That is, there exist statements $A$ such that the set of mathematical axioms $ZF$ can not prove $A$ and can not prove $\neg A$ as well. A given statement $A$ is then called undecidable. However, in my proof I am not assuming that either $ZF$ proves $A$ or $ZF$ proves $\neg A$, but rather that one among $A$ and $\neg A$ is true. This one could be a bit counterintuitive, at least it was for me, but again, you are using the "logical version" of the law of the excluded middle, not the "matematical one" (which is simply not true).

---

---

Edit 1: I am not entering the discussion about what is and what isn't a proof by contradiction because I can easily get confused. In any case, it seems clear to me that the first and second example you brought are very similar, as for both proofs, the conclusion you have is "$A$ is both true and false". After that, it seems to me that in both cases you still need an extra step to say "...therefore, $A$ is proved" (more precisely, the last step should be "...therefore, $ZF\implies\neg A$"). I think when you think about this from a logical point of view, you are forced to make clear the distinction between "$A \text{ is false}$", which is a statement that could be true or not depending on your axioms (in logical symbols, $\neg A$), and "we have proved $A$", that is a fact that you can actually verify unless $A$ is undecidable (in logical symbols, $ZF\implies \neg A$). This is why it could help you understand things. It's not an easy subject, one needs some time to really understand what is going on.

Edit 2: For all Italian people that are reading this answer. If you are interested in these topics but you don't have time to read something about it, I would suggest the podcast by Piergiorgio Odifreddi called "Storia della logica" (I have found it on Spotify).

Edit 3: Thanks to DRF for the interesting and useful discussion.

Answer 3

Both types are based on Contraposition

The first one is a direct application of the rule of contraposition, which says that:

$$ (A \implies B) \iff (\lnot{B} \implies \lnot{A}) $$

Arguably it is not actually a proof by contradiction: you begin from constructing the left hand side proposition, by showing that if there were finite primes (construction of proposition $A$) you could divide $1$ by a prime (implication of proposition $B$) thus you obtain $A\implies B$. The next step is to use the above contraposition rule to obtain the equivalent proposition which is: $\lnot{B}\implies\lnot{A}$ which you then use to establish the required result: since you know that $\lnot{B}$ is true (you cannot divide $1$ by any prime) then $\lnot{A}$ must also be true (there isn't a finite number of primes).

---

In the second case you begin by assuming $\sqrt{2}\in\mathbb{Q}$, let's denote that proposition by $A$. Then by definition of $\mathbb{Q}$ you also obtain: $(\sqrt{2}\in\mathbb{Q}) \implies (\exists{m,n}\in\mathbb{Z}:\sqrt{2}=\frac{m}{n}, n\neq{0})$

Let us denote by $B$ the latter proposition: $(\exists{m,n}\in\mathbb{Z}:\sqrt{2}=\frac{m}{n}, n\neq{0})$

So we have $A\implies B$ again, but now through several further implications, you obtain $\lnot{B}$ and call that the "contradiction" part of the proof, and hence similarly to the first case we obtain:

$$\lnot{B}\implies\lnot{A}$$

Which means $\sqrt{2}\notin\mathbb{Q}$.

---

The difference between both cases is subtle, and as you may have noticed, is mainly concerned with when do we use the contraposition rule. In the first case, since you apriori had $\lnot{B}$ as true, all you had to do was use the contraposition rule after obtaining $A\implies{B}$.

In the second case, $\lnot{B}$ is obtained as more of a 'surprise' if you will, and not known apriori, in other words: there is some contradiction in the proof itself that implies that $\lnot{B}$ is true but you didn't know it beforehand, hence it is called a contradiction.

A lot of confusion in propositional logic I think arises from not distinguishing between the relationships of propositions and their truth/false values. The rules of logic themselves are about the relationships, but the truth and false values come into play only when we make use of these relationships, for example in formal proofs. I think this is an example of a case that can lead to such a confusion: in both cases we've used the same relationships, but since the propositions are given truth/false values at slightly different points, the actual process of writing down or thinking about the proof may be quite different.

Note that by definition proof by contradiction means that given some propositions $p$ and $q$, you begin by assuming that $p$ is true, but then you also obtain truth value for the proposition:

$$(p\implies q) \land \lnot q$$

From which you conclude that $p$ must be false, so the basic idea behind proof by contradiction is: a proposition that implies something and the negation of that same thing must be false.

As an aside, there are some approaches to logic that don't always accept proof by contradiction as valid, for various reasons. One reason is that some people argue that saying that $(q\lor\lnot{q})$ (also known as "The law of the excluded middle") must always be true, only makes sense when the proposition is related to finite sets, but when the proposition says something about infinite sets that requires asserting something about an infinite number of items, which is not accepted for example in Intuitionistic logic.

Answer 4

Just so you know, what you’re describing is called proof of negation, while proof by contradiction usually means specifically that not-A is assumed, a contradiction derived, and thereby A is proven. The distinction between the two is important for the explanation to your question, otherwise I wouldn’t mention it since it’s a somewhat superficial distinction.

The reason is roughly because of the principle of explosion. That is, if you accept that Case 1 is a sensible use of proof by negation, then if you have explosion, it’s easy to derive absurdities of your choosing in order to accept Case 2. So, if you’re uncomfortable with deriving not-A from assuming A and deriving not-A itself, then either use explosion or a paraconsistent logic. Another reason is that in many logical formalizations, $\neg A$ is defined as $A \to \bot$ where “$\bot$” is a generalized contradiction. Further, in many logics $\neg A$ is materially equivalent to $ A \to \bot$ regardless of its semantic definition.

Answer 5

For case 2, you need to know that $\sqrt{2}$ can be proven to be a Real Number.

Since Real Numbers are either rational or irrational, then $\sqrt{2}$ is either rational or irrational.

The proof by contradiction follows.

Answer 6

The principle of proof by contradiction says that you can prove $A$ by assuming $\lnot A$ and deducing $A$ from that assumption. It relies on a principle called the law of the excluded middle (LEM) that asserts that $A \lor \lnot A$ holds for every proposition.

Your second kind of proof relies on LEM. The validity of LEM is debatable: there has been a long debate about it in the philosophy of mathematics. See https://en.wikipedia.org/wiki/Intuitionism.

Your first kind of proof does not rely on LEM but on the principle of contraposition: the principle that if $A$ implies $B$ than $\lnot B$ implies $\lnot A$. This is acceptable to intuitionists. I would recommend you to give proofs that are intuitionistically acceptable whenever you can.

Answer 7

In this case, I cannot see how we can deduce that A must be false, since I cannot be certain that the consequent (not-A) is either true or false, since its truth value depends on my assumption.

You're missing a step that's usually just skipped over because it's so simple. For example, assume you are showing "A is not true" by contradiction.

1. A is either true or not true, but not both. (Law of excluded middle.)
2. Case 1: If A is not true, then A is not true. (This is the step you're missing, but if there's any question about this then you can write it out and show that if you start with the assumption that A is not true then, in fact, you can conclude that A is not true.)
3. Case 2: If A is true, then (...some series of steps...) we can conclude A is not true.

So no matter what your choice of assumption is, in all cases A is not true.

Answer 8

The good news is that you can assume math is consistent because if it isn't, all theorems are true. Specifically if your theorem set is inconsistent, there exists P such that P and !P are both true. Therefore by a bit of boolean algebra, you can prove any statement true.

Answer 9

How we can deduce that $A$ must be false

I think you misunderstand the proof in the video you mentioned in your comment.

It is not the proof of $A\implies \lnot A$. It shows $A\implies \bot (\text{contradiction})$, then derives $\lnot A$ by the introduction rule of $\lnot$.

$$\frac{A\implies \bot}{\lnot A}$$

If we assume $A$ and derive a contradiction, then we can derive $\lnot A$ without assuming $A$.