2

... where a trivial proof by contradiction means effectively using a different proof technique to establish that the statement is true, and since you've assumed it's false, it's a contradiction.

Aside from that, the title pretty much says it all: do true mathematical statements exist which can only be proved with methods other than contradiction? It seems plausible that a statement that says anything worth saying would have logical implications which could eventually be made to show inconsistency, assuming the statement is provable one way or the other.

Trevor
  • 6,022
  • 15
  • 35
  • It seems your question is whether there is a P such that there is a proof q : (P -> false) -> false and each such q is in some suitable sense equal to some p^ where p : P and p^ : (P -> false) -> false is defined by p^ r = r p. If you use extensional equality, then the answer is trivially "yes", since false is a subsingleton. If you use intensional equality, then the situation could be more interesting. Intensional equality is the syntactic equality of normal forms. So your question is whether each such lambda term q reduces to something of the form p^. – Joel Sjögren Jul 30 '19 at 00:33

2 Answers2

2

In any of the "classical" mathematical systems that include the usual propositional logic, you can (in principle) turn a "direct" proof into a proof by contradiction, essentially by reversing the steps. Thus if your direct proof consists of statements $S_1, S_2, \ldots, S_n = P$, where each $S_i$ is either an axiom or follows by an axiom from its predecessors, you can start from $\neg P$ and deduce $\neg (S_1 \wedge S_2 \ldots \wedge S_{n-1})$, then $\neg (S_1 \wedge S_2 \ldots, \wedge S_{n-2})$, and so on until $\neg S1$ which contradicts an axiom.

However, in intuitionistic logic, where the law of the excluded middle is not included, this does not work, and in fact you can't e.g. prove that something exists by proving that its non-existence would lead to a contradiction.

Robert Israel
  • 448,999
0

Any proof can be turned into a proof by contradiction: to prove $\phi$, you can always assume $\lnot\phi$, ignore that assumption until you have proved $\phi$ and then complete your proof by claiming that you have arrived at the contradiction $\phi \land \lnot\phi$. But this is a dumb way to go about proof: use proof by contradiction as a last resort.

Rob Arthan
  • 48,577