6

I'm struggling with understanding proof by contradiction. So, I understood proof by contradiction as written below.

Want to prove "$p$ is true". First, assume that "$p$ is false". Show that this assumption leads to a contradiction e.g. $q$ is true and $q$ is false at the same time. Therefore, "$p$ is true".

So I understand "$p$ is false" leads to a contradiction and therefore "$p$ is false" cannot be true. But I don't understand why this has to lead "$p$ is true" i.e. I'm confused why "$p$ is false" being wrong has to mean "$p$ is true". Is it just nature of mathematics that has to be either true or false? Why can't it be like "$p$ is false" is wrong but "$p$ is true" is also wrong?

whwjddnjs
  • 663
  • https://imgur.com/a/8Q7HjMr This might help you. It is taken from Harold R. Jacobs' Geometry book. – yh05 Jul 19 '19 at 09:11
  • 1
    This rule is often part of the definition of (a proof system for) classical propositional/first-order logic. It is not "just [the] nature of mathematics". In the scenario I just described, it is simply assumed. Truth table or Boolean algebra semantics validate it. Contrarily, constructive logics explicitly do not have this rule, and, correspondingly, they have different notions of semantics (e.g. Heyting algebra semantics) which don't validate it. – Derek Elkins left SE Jul 19 '19 at 22:47

3 Answers3

2

"Is it just nature of mathematics that everything has to be true or false?"

Yes. This is the principle of bivalence.

ViktorStein
  • 4,838
2

You use the assumption that $p$ is false to prove something you know is false, a contradiction. Thus the assumption that $p$ is false is wrong.

The only remaining possibility is that $p$ is true.

$p$ is a statement, it can only be true or false but not both. The sentence, "She is a student." (with no reference to a specific person) is not a statement.

yh05
  • 363
1

Well, the assertion $P$ is logically equivalent to $\neg P\Rightarrow false$. Thus instead of proving $P$ you prove $\neg P\Rightarrow false$; you assume that $\neg P$ holds and then show that this leads to a logically false assertion which amounts to the contradiction.

For instance, show that $\sqrt 2$ is irrational. To prove this, assume the contrary, $\sqrt 2$ is rational. Then $\sqrt 2 = p/q$ where $p,q$ are relatively prime integers. From here one can derive a contraction, an assertion which is logically false.

Wuestenfux
  • 20,964
  • 1
    Your example is not a proof by contradiction in the sense that the OP means or that you describe. Your example is something else often called negation introduction. You are showing $\neg P$ given $P\to\bot$, not $P$ given $\neg P\to\bot$. "Irrational" means "not rational". To give an idea as to the difference, negation introduction is often taken as a primitive rule in constructive logic whereas adding proof by contradiction produces classical logic, so these are very different rules. – Derek Elkins left SE Jul 19 '19 at 22:47