I want to know the meaning of these mathematical terms. What do they mean in mathematical logic? Do they refer to same thing or are they different. I am trying to learn "Proof by contradiction" Please help me.
Thanks in advance.
Asked
Active
Viewed 8,175 times
3
-
1Yes, proof by contradiction is the same as Reductio ad absurdum, see Reduction to absurdity: reductio ad absurdum in polemics, logic and mathematics – Jared Jul 29 '16 at 04:09
-
As an example consider this "proof" that $1=2$. The "proof" leads to an absurd result (a contradiction). This means that, undoubtedly one or more of the premises must be false. In this example, the premise that you can cancel $a^2 - ab$ from both sides is false since, if $a = b$ then $a^2 - ab = a^2 - a^2 = 0$ thus the equation they try to "cancel" from is really $1\cdot 0 = 2\cdot 0$--which clearly does not imply that $1 = 2$. – Jared Jul 29 '16 at 04:13
-
It's worth noting that there's a bit of a semantic imprecision. In modern math there are valid results that might be considered absurd, such as the Banach-Tarski paradox. In Reductio ad absurdum the word seems to imply outright falsity ... if we reach a false result, our premise must have been false. But mere absurdity is not enough these days to claim a result is false. – user4894 Jul 29 '16 at 04:21
-
@user4894 I think that's bad language--there is no such thing as a paradox. There are things which we cannot explain--which present an apparent paradox. This does not mean they are not explainable logically. If something presents a "true paradox", then it is a contradiction and one of its assumptions must be false (therefore it's not a paradox). – Jared Jul 29 '16 at 04:41
-
@Jared What definition of "paradox" are you using when you say there is no such thing? – anon Jul 29 '16 at 09:33
3 Answers
4
If you mean to ask whether or not "contradiction" and "absurdity" can be regarded as synonyms in math, then the answer is simply yes.
Certainly, the word "absurdity" is subjective in everyday parlance. However, when used by mathematical authors, it generally always refers to a contradiction.
user21820
- 57,693
- 9
- 98
- 256
MathematicsStudent1122
- 12,462
1
They are the same. Any formula or derivation which implies or is equivalent to something of the form $B\wedge \neg B$ for some formula $B$ is considered as a contradiction or an absurd.
Note 1: $B\wedge \neg B$ means "B and (not B)".
The Proof by Contradiction can be stated as the following metatheorem:
Let $A$ be a closed formula. Then $\Gamma \vdash A$ if and only if $\Gamma +\neg A$ is inconsistent.
Note 2: $\Gamma \vdash A$ means that with the set of assumptions $\Gamma$ I can prove the formula $A$.
Note 3: in most natural deduction systems The Proof by Contradiction is the name of an inference rule and not a metatheorem, in that case, the proposition that I stated is normally used implicitly to prove the Deduction Theorem.
So, in order to prove $A$ with a set of assumptions $\Gamma$ you can add $\neg A$ as a new assumption and find any contradiction (it doesn't have to be $A\wedge \neg A$ necessarily, anything in that form will do the trick), as $\Gamma +\neg A$ is inconsistent if and only if it contains a contradiction (don't worry about this "being inconsistent" thing, for now you can consider my previous statement as the definition of inconsistency).
One of the most notorious examples of a proof by contradiction (seeing it as the metatheorem that I stated and not the rule of inference) is the proof that $\sqrt{2}$ is an irrational number and, to do it, you suppose that it isn't, i.e., $\sqrt{2}=p/q$ with $p,q \in\mathbb{Z}$ and $gcd(p,q)=1$ and you have a contradiction when you get that $\neg gcd(p,q)=1$: on one hand you have that $gcd(p,q)=1$ and, at the same time, $\neg gcd(p,q)=1$ on the other hand, which means $(gcd(p,q)=1)\wedge (\neg gcd(p,q)=1)$ (a contradiction). So, with that, you conclude that $\sqrt{2}$ is indeed irrational, because if it wasn't, you get an absurd. You can check the complete proof here:
https://proofwiki.org/wiki/Square_Root_of_2_is_Irrational
Note 4: to be clear, my example doesn't mean in any way that a Proof by Contradiction is strictly required to show that $\sqrt{2}$ is irrational, it's just an example (which is simple to follow) for the metatheorem I stated.
user119459
- 302
- 1
- 11
-
Proof by contradiction is not a meta-theorem at all. It is a rule of inference and can be used even if your so-called meta-theorem fails. Also, as has been pointed out on this site many times already, the proof that $\sqrt{2}$ is irrational is essentially a direct proof, because "irrational" simply means "not rational", and "$\neg A$" can be treated as "$A \to \bot$". In contrast "proof by contradiction" usually refers to proving "$A$" by showing "$\neg A \to \bot$", which is indirect and uses the full strength of classical logic. – user21820 Jul 29 '16 at 05:07
-
1
- Proof by contradiction as I can be viewed as a metatheorem that follows from the Deduction Theorem, which can be proven by induction under the two basic inference rules (modus ponens and existential introduction).
– user119459 Jul 29 '16 at 05:20 -
1
- the proof of irrationality of $\sqrt{2}$ is just a simple example of the application of the metatheorem by proving that the standard theory plus the proposition " $\sqrt {2}$ is rational" is inconsistent, so the negation of it must be the case.
– user119459 Jul 29 '16 at 05:25 -
1(1) You're thoroughly confusing between theorems and inference rules. And proof by contradiction has nothing to do with existential introduction! Sorry but the more you say the more wrong it gets. Please read any logic textbook. (2) Did you even understand my point? From "$\sqrt{2}$ is rational implies contradiction" we immediately get $\sqrt{2}$ is irrational as a direct consequence, unlike what is typically called proof by contradiction. – user21820 Jul 29 '16 at 05:37
-
1
- I not only read some textbooks, but I also can show some of them that treat that statement as a metatheorem. Not all logic books use natural deduction systems that treat the proof by contradiction as an inference rule, here are some:
- A Course in Mathematical Logic; Y. I. Manin.
- Lectures in Logic and Set Theory: Volume 1, Mathematical Logic; G. Tourlakis.
- Mathematical Logic and Model Theory: A Brief Introduction; A. Prestel.
-
1
- Just apply the statement that I enunciated to the proposition "the standard theory plus $\sqrt{2}$ is rational is inconsistent" and you'll get "the standard theory proves that $\sqrt{2}$ is irrational, it's that simple, doesn't matter. that you consider it a "direct proof", it's just an application of the result I stated.
– user119459 Jul 29 '16 at 06:02 -
1(1) Okay, but that's not how the vast majority of mathematicians think of as proof by contradiction. You could equally say that Modus Ponens is a meta-theorem in some deductive systems that doesn't have it as an inference rule, but that's not what the name means to most people. (2) Okay I get that you are working outside the system, but normally when one talks about a proof, it is literally a proof, not a meta-proof. Does this explain why I disagree with your answer? – user21820 Jul 29 '16 at 06:07
-
Yes, I get why you disagree with my answer: I'm using a theory (or meta-theory) that you are not used to see in the literature and maybe also in lectures. For you, I'm outside of the standard mathematical logic. And I hope that you can understand that, although the theory I use maybe different, it's not wrong and, for that reason, I don't think it deserves a negativation. – user119459 Jul 29 '16 at 06:17
-
Sorry about the downvote, but I feel that we shouldn't confuse students with non-standard terminology. If you clarify that your answer is about a meta-theorem and not about the usual inference rule called proof by contradiction, I'll remove the downvote, but honestly I don't think your answer addresses the question since it was about the rule, and clearly from a student just beginning to learn about proofs. – user21820 Jul 29 '16 at 06:30
-
2
-
Lol! I'm not the downvoter now! Let's hope he reads your comments and accepts your point of view. =) – user21820 Jul 29 '16 at 06:44
-
The $\sqrt 2$ is irrational proof is not an example of proof by contradiction, but rather a direct proof of the claim. It is constructively valid. The answer as it stands should not be recommended to students. – Ittay Weiss Jul 29 '16 at 06:47
-
1user21820 Yes, I know it wasn't you... Well, thanks for your comprehension anyway.
@Ittay Weiss Don't you agree that "the standard theory plus $\sqrt{2}$ is rational is inconsistent" implies that "the standard theory proves that $\sqrt{2}$ is irrational" from "$\Gamma \vdash A$ if and only if $\Gamma+ \neg A$is inconsistent" when $\Gamma=$ "the standard theory" and $A$="$\sqrt{2}$ is irrational"?
– user119459 Jul 29 '16 at 06:53 -
I will just say that that proof is constructively valid, while proof by contradiction is not. – Ittay Weiss Jul 29 '16 at 06:59
-
1I never said it wasn't. I also never said that contradiction is required for that proof. I just gave an example for the application of the metatheorem I enunciated. Do you see anything wrong with the application I described? – user119459 Jul 29 '16 at 07:02
-
Are you familiar with the SE comment system? If you comment on a post, the poster gets notified, but you need to put
@usernamesomewhere in your comment if you want to notify another user. Only one notification is allowed per comment. Ittay probably didn't see your response to him. – user21820 Jul 30 '16 at 08:28
1
The contradiction is a proof technique: you state an hypothesis, derive consequences and show that they lead to an impossible situation, which is absurb.
For example, we want to show that zero has no inverse.
We first make the hypothesis that zero has an inverse, let $x$. Then by the definition of the inverse, $0\times x=1$.
But $0=0+0$, so that by the usual computation rules $0\times x=(0+0)\times x=0\times x+0\times x=1+1$ and $1+1=1$.
As the last equality is absurd, the hypothesis cannot be true and this contradiction proves that $0$ has no inverse.
-
Perhaps you meant to consider $0 \cdot x$... But wouldn't it be better prove that $0\cdot y=0$ first and be done with it all? – Ittay Weiss Jul 29 '16 at 06:54
-
-
-
-
-
-
Yes, that is all i was trying to say. I also dislike the use of $\times$, but that is another issue. – Ittay Weiss Jul 29 '16 at 09:25
-