How does proof by contradiction work? I just had a thought from looking at this answer in this thread: For every $\epsilon >0$ , if $a+\epsilon >b$ , can we conclude $a>b$? 
I understand Brian's proof, but I just thought of something. If you prove a hypothesis is untrue, then the logical negation of that hypothesis must be true via proof by contradiction. But why? Can't it be the case that if a hypothesis is false, the negation is also false?
 A: Let's say you want to prove $P \implies Q$.
There are some substeps $P \implies P_2 \implies P_3 \implies P_4 \implies Q$.
Assume that $P$ is true and $Q$ is false.
Since $P$ is true, we have $P_2$ is true.
Since $Q$ is false, $P_4$ is false (by contrapositive of the last implication).
Since $P_2$ is true, $P_3$ is also true.
Since $P_4$ is false, $P_3$ is also false (by contrapositive).
So, $P_3$ is both true and false. This is impossible.
So, when $P$ is true, $Q$ cannot be false.
A: If a hypothesis is false, then the negation of the hypothesis is true. The negation of any false statement is always true, and the negation of any true statement is always false.
It's because a statement can only ever be true or false, there's nothing in between.

The idea behind proof of contradiction is that you basically prove that a hypothesis "cannot be untrue". I.e., you prove that if the hypothesis is false, then $1=0$. You then conclude that it is therefore not true that the hypothesis is false, and in standard logic, that means the hypothesis is true.

More strictly, if you have a hypothesis $H$, and we use the label $\top$ for the trivial true statement and $\bot$ as the trivial false statement, then in a proof of contradiction, you are proving the statement
$$\neg H\implies \bot$$
and you then use the fact that the statement $A\implies B$ is equivalent to $\neg B\implies \neg A$. Using this on your statement, that means that you have proven the statement
$$\neg(\bot)\implies \neg(\neg H)$$
which is the same as
$$\top \implies H.$$
Now, you use the fact that if $A\implies B$ and $A$ are both true, then $B$ is true. So, since $\top\implies H$ is true, and $\top$ is true (by definition), then $H$ must be true.
