# Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows:

Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be true, we reach a contradiction, therefore we conclude that $(p \implies q) = F$

But this only applies to the proofs, where boolean logic applies. In simple English, it would only apply to proofs where concepts such as the following are meaningful:

• 'If it's not this, then it must be that'
• 'If it's not true, then it must be false'
• 'If our assumption is not right, then it must be wrong'

But what about proofs where this sort of logic doesn't apply? What about proofs where proving that we reach a contradiction doesn't prove anything? For example what about proofs where we need to show the existence or equality of something?

Take for example following property for integer exponents $a^{n} \cdot a^{m} = a^{n+m} \ \ \forall \ m,n \in \mathbb{Z}$, surely something like this could not be proven using Proof by Contradiction, in this case a Direct Proof is commonly used to show unequivocally/rigorously that the exponent property for integer based exponents is true.

From what it seems to me, proofs by contradiction, only work where boolean logic applies, where a contradiction leads to something meaningful. If a contradiction doesn't lead to anything meaningful, then it can't constitute a proof can it?

Where does one draw the line for where proofs by contradiction can or cannot be used? If there is no boundary to where proof by contradiction can be used, then how does one know if the proof is even valid?

P.S, I'm not a constructivist, in case any of you were wondering

• I'm curious with your example, is it not true that one possible solution of $4^\frac{1}{2} = -2$ and that one possible solution to $4^\frac{1}{2} = 2$ and thus $4^\frac{1}{2}\cdot 4^\frac{1}{2} = -2\cdot 2 = -4$ yet $4^{\frac{1}{2} + \frac{1}{2}} = 4^1 = 4 \neq -4$? May 25, 2016 at 23:33
• @Jared, My apologies, the example I gave was incorrect, I've edited it now. May 25, 2016 at 23:42
• Everything in mathematics is boolean (either true or false). It's either sometimes true (an existence proof) or always true (a universal proof). So all theorems are open to be proved by contradiction--it's just that sometimes it's not easy to prove by contradiction and sometimes it is. Sometimes the proof by contradiction requires construction--in which case proof by contradiction wasn't the correct pathway in the first place. Square roots of non-perfect squares being irrational is a perfect example where proof by contradiction is really the only (or at least best) way. May 26, 2016 at 0:13
• Proof by contradiction requires the assumption that the logical system used is consistent. For example, you can't prove a theory is consistent using a proof by contradiction. If the theory is inconsistent you can always derive a contradiction. May 28, 2016 at 4:18

"From what it seems to me, proofs by contradiction, only work where boolean logic applies, where a contradiction leads to something meaningful. If a contradiction doesn't lead to anything meaningful, then it can't constitute a proof can it?"

This is a correct statement. If the contradiction isn't universal, then this isn't a "proof by contradiction". Proof by contradiction must be done very carefully and is closely related to proof by contrapositive (they are essentially the same).

Whenever employing a proof by contradiction you must be very careful about what exactly you are trying to prove. You must be very careful about what is the hypothesis and what is the conclusion. You must show that the conclusion always negates the hypothesis, not just some times.

In your example (I'm going to restrict to integers because it's much easier). It's easy to say that $a^na^m = a^{n+m}$ but this isn't the actual theorem. The theorem is that:

$$\forall a> 0, n, m \in \mathbb{Z}: a^na^m = a^{n + m}$$

More specifically:

$$a> 0,n,m \in \mathbb{Z} \Rightarrow a^na^m = a^{n+m}$$

So perhaps it appears that a possible "proof by contradiction" is that I can show that $a = 4$, $n = m = \frac{1}{2}$ and thus that $4^\frac{1}{2} = \{-2,2\}$ and thus it's possible that:

$$4^\frac{1}{2}\cdot 4^\frac{1}{2} = -2\cdot2 = -4 \neq 4^{\frac{1}{2} + \frac{1}{2}} = 4^1 = 4$$

So I "assumed" that the conclusion was false which lead to a contradiction that $n, m$ was in the integers, "q.e.d.".

But this proof is invalid and not a proper proof by contradiction. All I have done is presented a counterexample--not an implication that if $a^na^m = a^{n+m}$ is false that $\{n,m\}$ must not be integers.

To be a proper proof by contradiction I must show that there are only non-integers for which $a^na^m \neq a^{n + m}$--i.e. that it is always the case that, if the conclusion is false, then the hypothesis is false (not just some times).

I believe proof by contradiction is readily used in fuzzy logic, which is not Boolean, so really the question depends on what is meant by "drawing a line."

In general, if we are trying to prove $p \Rightarrow q$ , then we do not assume it is true. Rather, we assume $p$ and, for contradiction, we also assume not $q$. Then we (hopefully) arrive at a contradiction. This means that our assumption of not $q$ was false, so we showed that $q$ is true.

If, as in your example, you are just trying to prove a statement (of equality, or whatever else), then you assume the statement is false, and again you (hopefully) arrive at a contradiction somewhere.

The limit of proofs by contradiction, in my eyes, lies in whether or not you can actually find a contradiction. Sometimes it can make for an easy proof, other times it can lead nowhere.