19
$\begingroup$

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.

$\endgroup$
13
  • 2
    $\begingroup$ What are the details of the proof you have in mind that the square root of two is irrational? If hh = 2kk, and h and k are integers, then we know from previously established facts (the fundamental theorem of arithmetic) that we have an even number of factors of 2 on the left side of our equation ("hh") and an odd number of factors of 2 on the right side of our equation (2kk). Here we are assuming that the square root of 2 is rational, and then reaching a conclusion that we know (from previously established facts) to be false. It looks like what you called "1st CASE." $\endgroup$ Feb 22, 2023 at 17:32
  • 14
    $\begingroup$ If A is true, then A is false. If A is false, then A is false.So we deduce that A is false. $\endgroup$ Feb 23, 2023 at 5:47
  • 7
    $\begingroup$ $(A \to \lnot A)$ is not a contradiction (check it with truth table) but $(A \to \lnot A)$ implies $\lnot A$ (check it with truth table). $\endgroup$ Feb 23, 2023 at 13:44
  • 1
    $\begingroup$ What @MauroALLEGRANZA said. $A \rightarrow B$ is equivalent to $\neg A \lor B$, so $(A \rightarrow \neg A) \equiv (\neg A \lor \neg A) \equiv \neg A$. $\endgroup$
    – BrianO
    Feb 23, 2023 at 21:32
  • 1
    $\begingroup$ To the extent that there is an implicit assumption here, it is that A is either true or false (equivalently, that not-A is either true or false). If a problem with the math is to interfere with your type-2 proof by contradiction, it would be through A (equivalently, not-A) being neither true nor false. Technically, though, that would be an incompleteness, not an inconsistency. An inconsistency would manifest as A and not-A each being both true and false, which presents no impediment to the proof by contradiction of either one. $\endgroup$ Feb 24, 2023 at 1:51

9 Answers 9

12
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Could you please specify a bit more what you mean by "applying P2 to P1"? $\endgroup$
    – Agustin G.
    Feb 22, 2023 at 16:55
  • 1
    $\begingroup$ Agustin G. wrote: "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." --> The antecedent of P2 is A and the consequent is (not-A), and you are calling the antecedent of P2 your "assumption." However, you have obtained P2. Now, P1 indicates that there are two cases. In the left or first case, you have A, so by P2 and modus ponens you get the consequent in P2: (not-A). P1 tells you that the "other" case or possibility is the same thing: (not-A). $\endgroup$ Feb 22, 2023 at 17:17
  • $\begingroup$ @Agustin Sure! What we're doing is taking $(A \lor \neg A) \land (A \implies \neg A)$, distributing the disjunction to get $(A \land (A \implies \neg A)) \lor (\neg A \land (A \implies \neg A))$, reducing the conjunction on the right to get $(A \land (A \implies \neg A)) \lor \neg A$, then using modus ponens on the left to get $\neg A \lor \neg A$. I tend to find this easier to understand as just one step though, hence "applying P2". $\endgroup$
    – Lemmon
    Feb 26, 2023 at 12:25
8
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I don't believe you actually need the consistency of math for proofs by contradiction any more than you need them for any other proofs. That is a bit of a red herring. You conclude $\neg A$ from $A\implies \neg A$ based on the Law of excluded middle not based on math being consistent. Without the law of excluded middle you could have math being consistent and $\neg (A\vee \neg A)$ holding. $\endgroup$
    – DRF
    Feb 24, 2023 at 14:19
  • $\begingroup$ Note that consistency works the other way. You have inconsistency if you know $A\wedge \neg A$ not $\neg (A\vee \neg A)$ this seems to be same thing because we are so used to law of excluded middle and $\neg \neg A \equiv A$. $\endgroup$
    – DRF
    Feb 24, 2023 at 14:27
  • $\begingroup$ @DRF Yes, I agree that you need consistency of math for all proofs, in fact part of my answer applies to any proof. I agree that you essentially conclude using the law of excluded middle, but this was already answered elsewhere. I wanted to put emphasis on the second part of the question, as it is not clear in the simple argument one would write how consistency of math plays a role. $\endgroup$ Feb 24, 2023 at 17:26
  • $\begingroup$ I agree with what you mean by logical inconsistency, but note that in my case I am including $ZF$ as hypotheses and assuming that all logic principles hold, so the law of excluded middle holds (and the two things you wrote are equivalent). From my point of view, inconsistency (of math) would be $(ZF\rightarrow A)\wedge(ZF\implies\neg A)$, for some $A$. To be even more clear, by $ZF$ I mean $P_1\wedge P_2\wedge\dots P_k$, where the $P_j$’s are the axioms of your mathematical theory. This also means that in the setting I am describing, $\neg(A\wedge\neg A)$ always. $\endgroup$ Feb 24, 2023 at 17:31
  • 1
    $\begingroup$ The point is consistency has nothing to do with the problem. Bringing it up just muddies the waters. The consistency of ZF is completely irrelevant to the proof by contradiction. In other words the consistency of math plays no special role in proof by contradiction. No more than it does in proving that 2+2 is 4. That's what I'm trying to explain. $\endgroup$
    – DRF
    Feb 24, 2023 at 17:46
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Thank you for your answer Amit. It is very clear and quite helpful. I have one question: "In the second case, ¬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 ¬B is true but you didn't know it beforehand, hence it is called a contradiction." $\endgroup$
    – Agustin G.
    Feb 22, 2023 at 19:23
  • $\begingroup$ Could you expand more on the "contradiction in the proof itself that implies that not-B is true? I do not see where is is implied that not-B is true in the 2nd Case $\endgroup$
    – Agustin G.
    Feb 22, 2023 at 19:25
  • $\begingroup$ @AgustinG. - Sure. You would just have to take some specific version for the proof showing $\sqrt{2}$ is not rational. In one version, at some point of the proof after you have assumed that $\sqrt{2}\in\mathbb{Q}$ and hence can be represented by irreducible fraction $\frac{m}{n}$ you find that this implies something which is clearly false: that $2$ divides an odd number. Then from that you obtain $\lnot{B}$ by the same principle. In other words if you denote by $C$ now: "$2$ divides an odd number" then $B\implies{C}$ but we know that $\lnot{C}$. Same principle, just with several extra steps. $\endgroup$
    – Amit
    Feb 22, 2023 at 19:31
  • 1
    $\begingroup$ Oh, ok. I think I get it now! So, the argument is that sqrt(2) being a rational number implies the existence of a fraction which is both in its reduced form and not in its reduced form (a contradiction), something which we know is always false (due to common sense / the law of non-contradiction). Therefore, by the contrapositive, we get that sqrt(2) cannot be a rational number $\endgroup$
    – Agustin G.
    Feb 22, 2023 at 20:16
  • 1
    $\begingroup$ Ok, perfect. Thank you very very much! $\endgroup$
    – Agustin G.
    Feb 22, 2023 at 20:33
3
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ I believe that the second proof does not rely on LEM. The argument seems to be $A \implies \lnot A$ therefore $\lnot A$, which is intuitionistically valid. $\endgroup$
    – chi
    Feb 23, 2023 at 11:22
  • $\begingroup$ @chi: It does rely on LEM. Let's assume that LEM is not valid, and call the middle $?A$. Then $A \lor \lnot A \lor {?A}$, and applying $A \rightarrow \lnot A$ gives us only proof of $\lnot A \lor ?A$, which is a weaker result than $\lnot A$ $\endgroup$
    – Ben Voigt
    Feb 23, 2023 at 16:24
  • $\begingroup$ @BenVoigt Proof without LEM: the Hp1 $A \implies \lnot A$ is defined as $A \implies (A \implies \bot)$. To prove the thesis $\lnot A$, AKA $A \implies \bot$ we introduce the implication, assuming a new Hp2 $A$ and proceeding to prove the new thesis $\bot$. Use modus ponens on Hp1 and Hp2, twice, to obtain the thesis. $\endgroup$
    – chi
    Feb 23, 2023 at 19:25
  • $\begingroup$ @BenVoigt In intuitionistic logic, $\lnot A$ and $A \implies \bot$ are equivalent. Actually, in that context one typically does not take $\lnot$ as a primitive notion, but defines $\lnot A$ as $A\implies\bot$, so they are the same. $\endgroup$
    – chi
    Feb 23, 2023 at 20:13
  • 1
    $\begingroup$ @BenVoigt I agree, they are not equivalent. The OP wrote "suppose that from a premise A, I can show that the conclusion not-A follows. ... In this case, I cannot see how we can deduce that A must be false", so I formalized it as $(A \implies \lnot A)$ implying $\lnot A$. The answer by Lemmon also proves this (using LEM, even if it's not needed). The contradiction principle mentioned in this answer indeed requires LEM, but is not needed to prove the OP's claim, I believe. $\endgroup$
    – chi
    Feb 23, 2023 at 20:45
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Why? You can just prove that there doesn't exist any rational $p/q$ such that $(p/q)^2=2$. That doesn't need reals anywhere at all. $\endgroup$
    – DRF
    Feb 24, 2023 at 14:30
  • $\begingroup$ Depends what you want to prove. Your suggestion is sufficient to show that $\sqrt{2}$ is not rational. That doesn't prove that $\sqrt{2}$ is an irrational number. It could be undefined, or not a number. Alternatively, you could prove a closure property for positive square roots. Ex. 1/(2-2) is not rational, that doesn't prove that it is irrational. Irrational is not just the negation of rational; the irrationals are a set of numbers, Usually defined as the Reals - Rationals; in which case showing that $\sqrt{2}$ is not rational and a Real, proves it is irrational. $\endgroup$ Feb 24, 2023 at 14:48
  • 1
    $\begingroup$ Yes on not proving it's an irrational. No on the argument in your answer. The problem with the proof by contradiction has nothing to do with the reals/irrationals. It comes strictly before that. You prove by contradiction that it is not rational and you prove by construction (of the reals) that it is real, thus it's irrational. But in the bit of the proof where I'm using the contradiction the irrationals are completely irrelevant. The confusion of the OP is in the proof by contradiction bit. Not the existence as a real bit. $\endgroup$
    – DRF
    Feb 24, 2023 at 15:10
  • $\begingroup$ Ah, I understood their problem with proof by contradiction, to be why is $\sqrt{2}$ necessarily irrational, after being shown to be not rational That's what I understood to be their main issue, and so why I brought up the fact that $\sqrt{2}$ is Real. $\endgroup$ Feb 24, 2023 at 15:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .