4
$\begingroup$

I was given this explanation in my notes to understand Proof by Contradiction:

Proof by Contradiction

We want to prove that $\ P(n) \to Q(n) $ is true. In a proof by contradiction, we assume by contradiction that $\ P(n) \to Q(n) $ is false, that is, that: $\ \neg (P(n) \to Q(n)) $ is true.

The only way this might happen, is if $\ P(n) $ is true and $\ Q(n)$ is false. Thus we start with $\ P(n)$ true and $\ Q(n)$ false. If from there we deduce a contradiction, that is a statement of the form $\ C \wedge \neg C $, which is always false, what we have proven is :

$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$ , is true.

This is equivalent to $\ P(n) \to Q(n) $. To see that, set $\ S(n) = "P(n) \to Q(n)"$, and look at the truth table:

-

What I don't understand is this line: "$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$ , is true."

How is it true if previously stated that

$\ \neg (P(n) \to Q(n))$ is True

$\ C \wedge \neg C$ is False (a contradiction)

But we know that... $\ P \to Q $ is always False?

How am I interpreting this explanation wrongly? I am really confused right now... any help/explanation is very much appreciated, thanks!!!


Original screenshot (in case I formatted the equations wrongly... I'm new to mathjax/latex thing):

enter image description here

$\endgroup$
  • 3
    $\begingroup$ $C\land\lnot C$ is always false. Therefore, if through an assumption you can derive $C\land\lnot C$ is true, then your original assumption must have been false. The author isn't saying you get this for free. He is saying that if you can derive this contradiction from an assumption then the assumption is false. $\endgroup$ – John Douma Sep 18 at 5:03
  • 1
    $\begingroup$ "we know that...P→Q is always False?" You don't know it is always false. You just speculated that it might be true. And you got a contradiction. That means your speculation was false. So $P\to Q$ can't be false. Ex: If $n \ge 2$ then $n^3$ is composite. Is that true? I don't know, lets imagine it is false. The only way it can be false is if $n\ge 2$ and $n^3$ is prime. So $n^3$ is prime. If $n^3$ is prime than $\sqrt[3]n^3=n$ is irrational. So $n$ is both an integer and irrational.That's a contradiction. So our speculation that $n>2\implies n^3$ is composite being false... is false. $\endgroup$ – fleablood Sep 18 at 5:46
  • 1
    $\begingroup$ What a strange example with which to introduce PBC. Check other sources. It is not that complicated. The basic principle is that if you assume proposition P is true and subsequently obtain a contradiction (without introducing other assumptions) then P must be false. (It gets a little more complicated if you introduce multiple assumptions.) $\endgroup$ – Dan Christensen Sep 18 at 14:55
11
$\begingroup$

You're getting caught up on the word assume. You can make a pretend world by assuming a proposition is true when it's actually false. You're essentially breaking math. So, in this pretend world, ¬(P(n)→Q(n)), but also (C∧¬C). Since math has to be consistent, there was something wrong with our assumption, therefore the negation must be true, hence (P(n)→Q(n)).

$\endgroup$
5
$\begingroup$

What I don't understand is this line: "$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$ , is true."

Phrased another way, we hope to demonstrate that indeed, it "is true" that the negation of what we hope to prove leads to a contradiction. Therefore, the negation of what we hope to prove is false. Therefore, what we hope to prove is true.

You hope to prove $P(n) \to Q(n)$. Assume the negation. If it is true that the negation implies a contradiction

$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$

then $\ \neg (P(n) \to Q(n))$ is false. Therefore $P(n) \to Q(n)$ is true and our proof is complete.

You claim that if we stopped, you would fill the gas tank. We did stop and yet here we are on the side of the highway, gas gauge on E. How do you explain that Karen?

A famous example of proof by contradiction is the proof for the infinitude of the prime numbers. We hope to prove there an infinite number of primes. By way of contradiction, assume there are a finite number of primes. Then there must be a largest prime. Multiply all the primes together and add one. This new number is larger than every prime, and leaves a remainder of one when divided by any prime. Since it is not divisible by any smaller prime, it must be itself prime. But it is larger than the largest prime. This is a contradiction. Therefore, it is not true that there are a finite number of primes.

(There are a finite number of primes) $\to$ (there is a largest prime) $\land$ (there is a prime larger than the largest prime)

Therefore, there are an infinite number of primes.

$\endgroup$
4
$\begingroup$

It is not said that $\neg(P\to Q)$ is true but rather that we would treat it as if it were.

Logically it is not at all “taken to be true”, we simply make the deduction of $C\wedge \neg C$ from $\neg( P\to Q)$ via reasoning and the validity of that statement is not considered to begin with. The language of “taking it to be false” is English (for “we will begin with the negation of the statement”).

$\endgroup$
2
$\begingroup$

Using the simplified symbols, we have a proof of the statement

$¬S→(C∧¬C)$.

The text says :

"We want to prove that $S$. In a proof by contradiction, we assume by contradiction that $S$ is false, that is, that $¬S$ is true. If from there we deduce a contradiction, that is a statement of the form $C∧¬C$, which is always false, what we have proven is : $¬S → (C∧¬C)$."

If we have a proof of the said statement, this means that it holds (we have proved it) and thus we have to consider the lines in the truth table where the formula is flagged TRUE : the first two.

As we can see, in these lines $S$ is flagged TRUE ($¬S$ is flagged FALSE).

And thus, having proved the statement above, we are forced to conclude that $S$ is TRUE.

The issue is simply that the contradiction $C∧¬C$ is always FALSE, and thus, by the truth table for $\to$, the only way that the statement $¬S → (C∧¬C)$ is TRUE is when also the antecedent $¬S$ is FALSE.


The mechanism of logical deduction (as formalized by Modus Ponens) can be sumamrized with the principle (by courtesy of Bertrand Russell) :

"What is deduced from a true proposition is true".

Thus, being always false, a contradition cannot be deduced from a true proposition.

Conclusion : if we have a valid proof of a contradiciton from a certain statement $\lnot S$, that statement must be false.

$\endgroup$
2
$\begingroup$

The goal of proving a statement $S$ by contradiction is to prove the statement $$ \neg S \rightarrow (C\land \neg C) \hspace{20pt} (*) $$ for some statement $C$. This works because $C\land \neg C$ is always false, and $\neg S\rightarrow \bot\equiv\bot\lor S\equiv S$.

Now, let's suppose $S$ is of the form $P\rightarrow Q$. In a direct proof, we assume $P$ as an additional premise, and show that $Q$ follows from that assumption. In a proof by contradiction, we apply the same method to the statement $(*)$: we assume $\neg S$ (equivalently, $P$ and $\neg Q$) as an additional premise and show that there is a statement $C$ such that $C\land \neg C$ follows from that assumption.

$\endgroup$

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.