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.
$\endgroup$ 53 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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:
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.
$\endgroup$ 16 $\begingroup$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.
$\endgroup$ 8
