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.

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.