Can something proved by contradiction always be proved without a proof by contradiction?

Question

Proof by contradictions work by assuming that something is true, and then using logic (along with other assumptions which you know are true) to show that that leads to a contradiction, thus proving that your assumption must be false.

1. If I can prove that a particular statement P is false via a proof by contradiction, can I always prove that P is false via some other method? (For example, by proving that not P is true without using a proof by contradiction.)

2. If so, can you provide some proof that every proof by contradiction can be turned into some other form of proof?

3. If not, is there any well-defined way of describing when a proof by contradiction is the only proof that will work?

Answer 1

The following answer will primarily follow the article by Kevin C. Klement, "Propositional Logic". Here are the questions which I numbered:

1. If I can prove that a particular statement P is false via a proof by contradiction, can I always prove that P is false via some other method? (For example, by proving that not P is true without using a proof by contradiction.)

2. If so, can you provide some proof that every proof by contradiction can be turned into some other form of proof?

3. If not, is there any well-defined way of describing when a proof by contradiction is the only proof that will work?

There is the semantic proof method of truth tables one could use to avoid a syntactic proof by contradiction entirely. To use this one would write the premises as conjuncts and make that sentence the antecedent of a conditional with the consequent being the goal of the proof. If there are no premises one just constructs a truth table on the goal.

A truth table would show if that sentence is a tautology or not and in the process provide a semantic proof of the goal, the consequent, given any premises, the antecedent, without using contradiction.

This method would allow a "yes" answer to question 1. Question 2 would ask if the two methods, a truth table semantic proof and a deductive syntactic proof, give the same results. A sketch of such a proof is found in Chapter 36 and 37 of forallx.

The OP, however, is perhaps looking for a syntactic proof method that avoids using an indirect proof or a proof by contradiction.

To see what might be available, consider the rules for a syntactic proof in natural deduction.

There are rules of inference which Klement lists as modus ponens, modus tollens, disjunctive syllogism, addition, simplification, conjunction, hypothetical syllogism, constructive dilemma, and absorption. Note that given statement(s) these rules of inference allow one to derive another statement.

There are also rules of replacement which allow one to make substitutions. They are called double negation, commutativity, associativity, tautology, DeMorgan's rules, transposition, material implication, exportation, distribution and material equivalence. Like the rules for inference these rules assume we are given statement(s) upon which a replacement can be made.

Together with premises, the rules of inference and the rules of replacement are what constitute direct deductions.

Conditional and indirect proofs form another group of rules. Klement has this to say about them:

Together the nine inference rules and ten rules of replacement are sufficient for creating a deduction for any logically valid argument, provided that the argument has at least one premise. However, to cover the limiting case of arguments with no premises, and simply to facillitate certain deductions that would be recondite otherwise, it is also customary to allow for certain methods of deduction other than direct derivation. Specifically, it is customary to allow the proof techniques known as conditional proof and indirect proof.

This provides a suggestion that indirect proofs may be needed for some syntactic proofs without premises. This may provide an answer to question 3. If the goal does not have premises and the goal is not itself a conditional allowing us to try a conditional proof, one may need to use contradiction in natural deduction to prove it.

Another way around this would be to consider axiomatic systems which Klement describes as follows:

The system of deduction discussed in the previous section is an example of a natural deduction system, that is, a system of deduction for a formal language that attempts to coincide as closely as possible to the forms of reasoning most people actually employ. Natural systems of deduction are typically contrasted with axiomatic systems. Axiomatic systems are minimalist systems; rather than including rules corresponding to natural modes of reasoning, they utilize as few basic principles or rules as possible.

It is with axiomatic systems rather than natural deduction where there may be the most interest in minimizing the rules. Klement describes "an axiomatic system for classical truth-functional propositional logic" (PC) as follows:

System PC consists of three axiom schemata, which are forms a wff [well formed formula] fits if it is axiom, along with a single inference rule: modus ponens.

---

Kevin C. Klement, "Propositional Logic" Internet Encyclopedia of Philosophy https://www.iep.utm.edu/prop-log/#SH5e

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/

Answer 2

To answer the question it is useful to understand the difference between classical and intuitionistic logic.

If I can prove that a particular statement P is false via a proof by contradiction, can I always prove that P is false via some other method? (For example, by proving that not P is true without using a proof by contradiction.)

In classical logic we have a set of statements which are all equivalent to each others. We call them classical laws. Example of classical laws :

• Proof by contradiction : for all A, if ~A leads to a contradiction then A
• Exluded Middle : for all A, A v ~A
• Peirce's law : for all A B, ((A => B) => A) => A
• Implication translation : A -> B is equivalent to ~A v B
• Some De Morgan's laws
• ...

What is provable by contradiction is always provable by the other laws. However, these laws form a quite independant part of Logic. If we remove all of them we get a logic called Intuitionistic Logic where some statements aren't provable anymore (including the classical laws themselves of course).

What is interesting is that Intuitionistic Logic is a logic where proof are justified by concrete constructions. We can only prove what we can "show/exhibit". If you want to prove A v ~A then you have to either provide a proof of A or ~A. We can avoid that in classical logic by using one of the classical laws.

If so, can you provide some proof that every proof by contradiction can be turned into some other form of proof?

We just have to take any classical law and show it does the same thing as proof by contradiction. I will take the law of exluded middle.

• Suppose I know that ~A leads to a contradiction, formally ~A => False (where False is a constant representing an unprovable statement) and we want to prove A. By the law of excluded middle, we know that either A or ~A. We do a proof by cases.

  • Either A. You're done.
  • Either ~A. We have A => False. By modus ponens, we can infer False. By the law of explosion also called Ex Falso Quodlibet which isn't a classical law, we can infer anything. Let's infer A. You're done.

Answer 3

This is an old post, but I figured I’d complement the existing answers since more can be said.

Usually, ‘Proof by Contradiction’ is restricted to the proof method by which ~A is assumed for the sake of a contradiction. Once a contradiction has been derived, we’re allowed to infer A. This is a classical proof technique, so it is invalid intuitionistically.

What the OP calls “Proof by Contradiction” is commonly called “Proof of Negation”. A proof of negation assumes A for the sake of a contradiction so as to derive ~A.

As far as I know ‘Proof of Negation’ is the only way to introduce a negation; this is exemplified by the fact that usually ~A is defined as A⇒⊥.

Related to OP’s question is that every proof of negation can be derived constructively, whereas proofs by contradiction are not constructively valid. This is why adding the Law of the Excluded Middle to intuitionistic logic makes everything classical again.