0
$\begingroup$

I had a doubt in the proof by contradiction technique.

Under this technique, we assume the negation of what we want to prove as true, then show that assuming so generates a contradiction. Since a consistent system cannot have a contradiction, so our assumption must be false and the original statement must be true.

The doubt here is, is the proof by contradiction valid if the statement we contradict is the assumption itself. That is I start with wanting to prove q, assume negation q to be true, and then reach q eventually, leading to a contradiction and hence concluding q at the end?

It would be helpful if someone can explain this with the help of a concrete example, if it exists.

$\endgroup$
3
  • $\begingroup$ Then you could just skip the "assume negation q to be true" step. This is not a proof by contradiction because you don't need that assumption. A proof by contradiction showing $q$ must proceed as follows: Assume "not $q$". Prove a falsum $A$ by using "not $q$" somewhere in the proof for $A$. Because the falsum cannot be true, "not $q$" cannot hold, thus implying $q$ holds. $\endgroup$
    – idmean
    Oct 12 at 9:17
  • 2
    $\begingroup$ I’m voting to close this question because it belongs in Mathematics. $\endgroup$ Oct 12 at 9:19
  • 1
    $\begingroup$ You may want to read Andrej Bauer's Proof of negation and proof by contradiction. $\endgroup$ Oct 12 at 10:04
2
$\begingroup$

There is no problem with assuming $ \neg q$ towards a contradiction and showing that this implies $q$.

Here is an example, adapted from Euclid's proof that there are infinitely many primes.

Let $p$ be a prime number and suppose we want to prove "there exists a prime number larger than $p$". We proceed by contradiction, i.e., we assume that "all prime numbers are smaller than or equal to $p$".

Let $P$ be the set containing all prime numbers and define $x = \prod_{p \in P} p + 1$. If $x$ is not prime then, by our assumption, there must be some $p^* \in P$ that divides $x$. However our choice of $x$ ensures that $x \bmod p^* = 1$ for every $p^* \in P$. Therefore $x$ is a prime larger than $p$, a contradiction.

$\endgroup$
0
$\begingroup$

I'll add some steps to make it very clear. You want to prove q.

You can take any statement s, then say "either s or not s is true", and then prove "if s is true then q is true" and "if not s is true then q is true". That happens actually quite often; you might have the statement "x ≤ 1" and you can prove that if x ≤ 1 then q is true for some reasons, and if x ≥ 1 then q is true for totally different reasons.

Instead of taking any statement s, you can take the statement q itself. Then you say "either q or not q is true". Then you prove "If q is true then q is true" which is very, very obvious, and you prove "if q is not true then q is true". That's just a normal proof, you don't even have to call it "proof by contradiction".

$\endgroup$
1
  • $\begingroup$ If q is not true, how can we prove it to be true? $\endgroup$
    – Kashish
    Oct 13 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.