Can every proof by contradiction also be shown without contradiction?
Are there some proofs that can only be shown by contradiction or can everything that can be shown by contradiction also be shown without contradiction? What are the advantages/disadvantages of proving by contradiction?
As an aside, how is proving by contradiction viewed in general by 'advanced' mathematicians. Is it a bit of an 'easy way out' when it comes to trying to show something or is it perfectly fine? I ask because one of our tutors said something to that effect and said that he isn't fond of proof by contradiction.
Solution 1:
To determine what can and cannot be proved by contradiction, we have to formalize a notion of proof. As a piece of notation, we let $\bot$ represent an identically false proposition. Then $\lnot A$, the negation of $A$, is equivalent to $A \to \bot$, and we take the latter to be the definition of the former in terms of $\bot$.
There are two key logical principles that express different parts of what we call "proof by contradiction":
The principle of explosion: for any statement $A$, we can take "$\bot$ implies $A$" as an axiom. This is also called ex falso quodlibet.
The law of the excluded middle: for any statement $A$, we can take "$A$ or $\lnot A$" as an axiom.
In proof theory, there are three well known systems:
Minimal logic has neither of the two principles above, but it has basic proof rules for manipulating logical connectives (other than negation) and quantifiers. This system corresponds most closely to "direct proof", because it does not let us leverage a negation for any purpose.
Intuitionistic logic includes minimal logic and the principle of explosion
Classical logic includes intuitionistic logic and the law of the excluded middle
It is known that there are statements that are provable in intuitionistic logic but not in minimal logic, and there are statements that are provable in classical logic that are not provable in intuitionistic logic. In this sense, the principle of explosion allows us to prove things that would not be provable without it, and the law of the excluded middle allows us to prove things we could not prove even with the principle of explosion. So there are statements that are provable by contradiction that are not provable directly.
The scheme "If $A$ implies a contradiction, then $\lnot A$ must hold" is true even in intuitionistic logic, because $\lnot A$ is just an abbreviation for $A \to \bot$, and so that scheme just says "if $A \to \bot$ then $A \to \bot$". But in intuitionistic logic, if we prove $\lnot A \to \bot$, this only shows that $\lnot \lnot A$ holds. The extra strength in classical logic is that the law of the excluded middle shows that $\lnot \lnot A$ implies $A$, which means that in classical logic if we can prove $\lnot A$ implies a contradiction then we know that $A$ holds. In other words: even in intuitionistic logic, if a statement implies a contradiction then the negation of the statement is true, but in classical logic we also have that if the negation of a statement implies a contradiction then the original statement is true, and the latter is not provable in intuitionistic logic, and in particular is not provable directly.
Solution 2:
If a statements says "not $X$" then it is perfectly fine to assume $X$, arrive at a contradiction and conclude "not $X$". However, in many occasions a proof by contradiction is presented while it is really not used (let alone necessary). The reasoning then goes as follows:
Proof of $X$: Suppose not $X$. Then ... complete proof of $X$ follows here... This is a contradiction and therefore $X$.
A famous example is Euclid's proof of the infinitude of primes. It is often stated as follows (not by Euclid by the way):
Suppose there is only a finite number of primes. Then ... construction of new prime follows ... This is a contradiction so there are infinitely many primes.
Without the contradiction part, you'd be left with a perfectly fine argument. Namely, given a finite set of primes, a new prime can be constructed.
This kind of presentation is really something that you should learn to avoid. Once you're aware of this pattern its amazing how often you'll encounter it, including here on math.se.
Solution 3:
It somewhat depends on whether you are intuitionist or not (or both? or neither? Who knows without the law of excluded middle). According to the Wikipedia article even intuitionists accept some versions of what one could call indirect proof, but reject most. In that sense, a direct proof would be preferable (and is often even a bit more elegant).
An example:
Theorem. There exist irrational numbers $a,b$ such that $a^b$ is rational.
Proof: Assume that $a,b\notin \mathbb Q$ always implies $a^b\notin \mathbb Q$. Then $u:=\sqrt 2^{\sqrt 2}\notin \mathbb Q$ and $u^\sqrt 2=\sqrt 2^{\sqrt 2\cdot\sqrt 2}=\sqrt 2^2=2\notin \mathbb Q$ - contradiction!
Indeed, an intuitionist would complain that we do not exhibit a pair $(a,b)$ with $a,b\notin \mathbb Q$ and $a^b\in \mathbb Q$. Instead, we only show that either $(\sqrt 2,\sqrt 2)$ or $(u,\sqrt 2)$ is such a pair. Converting the proof given above to a direct and constructive proof would in fact require you to actually prove one of the two possible options $u\in \mathbb Q$ or $u\notin\mathbb Q$.
Solution 4:
See this post: Are proofs by contradiction weaker than other proofs?.
There are some wonderful answers related to your question - and addresses, directly, your "aside": See, in particular, what JDH writes.
One of the advantageous to constructing direct proofs of propositions, when this is feasible, is that one can discover other useful propositions in the process. That is, direct proofs help clarify the necessary and sufficient conditions that make a theorem true, and provide a structure demonstrating how these conditions relate, and how the chain of implications imply the conclusion.
Indirect proofs, on the other hand (aka "proofs by contradiction") only tell us that supposing a proposition to be otherwise leads to a contradiction at some point. But such a proof doesn't really provide the sort of insight that can be gained from direct proofs.
That is not to say that indirect proofs don't have their place (e.g., they come in handy when asked to prove propositions during a time-limited exam!). They often help "rule out" certain propositions on the basis that they contradict well established axioms or theorems. Also, indirect proofs are sometimes more intuitive than direct proofs. For example, proving that $\sqrt{2}$ is not rational using a proof by contradiction is clean, and intuitive.
Sometimes an indirect proof will emerge first, after which one can seek to proceed with trying to construct a direct proof to prove the same proposition. That is, providing an indirect proof of a proposition often motivates the construction of direct proofs.
Edit:
I found this blog entry (Gowers's Weblog) When is a proof by contradiction necessary. from which I'll quote an introductory remark:
It seems to be possible to classify theorems into three types: ones where it would be ridiculous to use contradiction, ones where there are equally sensible proofs using contradiction or not using contradiction, and ones where contradiction seems forced. But what is it that puts a theorem into one of these three categories?
The post follows immediately with a nice reply from Terence Tao.