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):
Best Answer
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)).