Logical limitations of Proofs by Contradiction

Question

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

Answer 1

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.

Answer 2

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."

Answer 3

"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).