3

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?

  • This question seems to broad to be answerable, because it's asking if it is always possible to do an RAA proof (proof by contradiction in a sub-proof) without RAA. – virmaior Nov 18 '18 at 2:31
  • @virmaior I don't think that's too broad of a thing to ask, and if it is too broad, then that's why the second question is there. The second question basically asks "If we can't do it for every RAA proof, which RAA proofs can't we do it for?" – Pro Q Nov 18 '18 at 4:07
  • 2
    You want a proof a positive universal claim about all proofs that can be accomplished by following a certain method could be accomplished without using this method. That's an amazingly robust thing to ask for... – virmaior Nov 18 '18 at 4:44
  • 1
    I made an edit to emphasize the three questions. You may roll this back if you think it was inappropriate. – Frank Hubeny Nov 18 '18 at 21:53
  • The answer is yes in a trivial sense, one can avoid the specific scheme of contradiction by rephrasing it as a combination of cases and contrapositive, for example, or using a disjunctive syllogism. In the substantive sense the answer is no, if one blocks all rephrasings of contradiction then one weakens the logic from classical to intuitionistic, and many classical theorems are known to be unprovable intuitionistically, see intuitionistic logic. – Conifold Nov 18 '18 at 22:08
3

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/

3

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.
  • I'm a little confused by the proof by cases at the end. I interpreted "Either" as meaning "we assume that", but that can't be right because then "Either ~A" would mean "~A => True", which contradicts what you say. – Pro Q Nov 30 '18 at 6:26
  • 1
    @ProQ Oh... Sorry. It's a mistake. I wanted to write A => False ! – Boris E. Nov 30 '18 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.