Vrftsjtryk

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.

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,bnotin mathbb Q$ always implies $a^bnotin mathbb Q$. Then $u:=sqrt 2^{sqrt 2}notin mathbb Q$ and $u^sqrt 2=sqrt 2^{sqrt 2cdotsqrt 2}=sqrt 2^2=2notin mathbb Q$ - contradiction!

Indeed, an intuitionist would complain that we do not exhibit a pair $(a,b)$ with $a,bnotin mathbb Q$ and $a^bin 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 $uin mathbb Q$ or $unotinmathbb Q$.

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.

A few points from my (limited) experience:

• I love proof by contradiction and I have used it in graduate level classes and no one seemed to mind so long as the logic was infallible.


• For me, it's much easier to think about a proposition in terms of "What if this wasn't true?". That is usually my first instinct, this makes proof by contradiction the natural first choice. For instance, if I were to be asked to prove something like "Prove that a non-singular matrix has a unique inverse". My first instinct would be "What if a non-singular matrix had 2 inverses?" and from then on, the proof follows cleanly.


• Sometimes, however, contradictions don't come cleanly and proof by simple logical deductions would probably take 5 lines whereas contradiction will take millions. I could point you to specific proofs but I'll have to do some digging. Further, if you look at every proof and try using Proof by Contradiction, another problem you will face is that sometimes, you will state your intended contradiction but never use it. In other words, solve using direct proof.


• Another aspect about Proof by Contradiction (IMHO) is that you really must know all definitions and their equivalent statements fairly well to come up with a nice contradiction. Else, you will end up proving several lemmas on the way which looks clean in a direct proof but not so much in a Proof by Contradiction, but again, this might be a personal choice.

In summary, if you find it easier to think in terms of "What if not" then go ahead, use it but make sure your proof skills using other strategies are as good because $exists$ nail that you cannot hit with the PbC hammer that you'll carry.

What is a proof by contradiction? This is actually quite difficult to answer in a satisfactory way, but usually what people mean is something like this: given a statement $phi$, a proof of $phi$ by contradiction is a derivation of a contradiction from the assumption $lnot phi$. In order to analyse this, it is very important to distinguish between the statement $phi$ and the statement $lnot lnot phi$; the two statements are formally distinct (as obvious from the fact that their written forms are different!) even though they always have the same truth value in classical logic.

Let $bot$ denote contradiction. When we show a contradiction assuming $lnot phi$, what we have is a conditional proof of $bot$ from $lnot phi$. This can then be transformed into a proof of the statement $lnot phi to bot$, which is the long form of $lnot lnot phi$ – in other words, we have a proof that "it is not the case that $lnot phi$". This, strictly speaking, is not a complete proof of $phi$: we must still write down the last step deducing $phi$ from $lnot lnot phi$. This is the point of contention between constructivists and non-constructivists: in the constructive interpretation of logic, $lnot lnot phi$ is not only formally distinct from $phi$ but also semantically distinct; in particular, constructivists reject the principle that $phi$ can be deduced from $lnot lnot phi$ (though they may accept some limited instances of this rule).

There is one case where proof by contradiction is always acceptable to constructivists (or at least intuitionists): this is when the statement $phi$ to be proven is itself of the form $lnot psi$. This is because it is a theorem of intuitionistic logic that $lnot lnot lnot psi$ holds if and only if $lnot psi$. On the other hand, it is also in principle possible to give a "direct" proof of $lnot psi$ in the following sense: we simply have to derive a contradiction by assuming $psi$. Any proof of $lnot psi$ by contradiction can thus be transformed into a "direct" proof because one can always derive $lnot lnot psi$ from $psi$; so if we can obtain a contradiction by assuming $lnot lnot psi$, we can certainly derive a contradiction by assuming $psi$.

Ultimately, both of the above methods involve making a counterfactual assumption and deriving a contradiction. However, it is sometimes possible to "push" the negation inward and even eliminate it. For example, if $phi$ is the statement "there exists an $x$ such that $theta (x)$ holds", then $lnot phi$ can be deduced from the statement "$theta (x)$ does not hold for any $x$". In particular, if $theta (x)$ is itself a negative statement, say $lnot sigma (x)$, then $lnot phi$ can be deduced from the statement "$sigma (x)$ holds for all $x$". Thus, proving "there does not exist an $x$ such that $sigma (x)$ does not hold" by showing "$sigma (x)$ holds for all $x$" might be considered a more "direct" proof than either of the two previously-mentioned approaches.

Can all proofs by contradiction be transformed into direct proofs? In some sense the answer has to be no: intuitionistic logic is known to be weaker than classical logic, i.e. there are statements have proofs in classical logic but not intuitionistic logic. The only difference between classical logic and intuitionistic logic is the principle that $phi$ is deducible from $lnot lnot phi$, so this (in some sense) implies that there are theorems that can only be proven by contradiction.

So what are the advantages of proof by contradiction? Well, it makes proofs easier. So much so that one algorithm for automatically proving theorems in propositional logic is based on it. But it also has its disadvantages: a proof by contradiction can be more confusing (because it has counterfactual assumptions floating around!), and in a precise technical sense it is less satisfactory because it generally cannot be (re)used in constructive contexts. But most mathematicians don't worry about the latter problem.

As "Inquest"'s answer mentions, it's often easier to find a proof by contradiction than a direct proof. But after you do that, you can often make the proof simpler by rearranging it into a direct proof. It is not good to make a proof appear more complicated than it really is.

To see another disadvantage of some proofs by contradiction, consider this:

Proof: To prove $A$, assume not $A$. [insert 50 pages of argument here] We have reached a contradiction. Therefore $A$. End of proof

Now ask yourself: Which of the propositions proved in those 50 pages are erroneous and could be proved only because one relied on the false assumption that not $A$, and which are validly proved, and which are true but not validly proved because the assumption that not $A$ was relied on? It's not so easy to tell without a lot more work. And if you remember a proof of one of those propositions, you might just mistakenly think that it's been proved and is therefore known to be true. So it might be far better to limit the use of proof by contradiction to some portions of those 50 pages where no other method works.

Perhaps proofs of non-existence can be done only by contradiction. Here I might offer as an example the various proofs of the irrationality of $sqrt{2}$, but for the fact that I've seen it asserted that if $m$, $n$ are integers, than $m/n$ differs from $sqrt{2}$ by at least an amount that depends on $n$ --- I think it might have been $1/(3n^2)$. Here's another example: How would one prove the non-existence of a non-trivial (i.e. $>1$) common divisor of $n$ and $n+1$?

I've seen a book on logic asserting that a proof by contradiction of a non-existence assertion does not constitute an "indirect proof", since the assertion is inherently negative. I don't know how conventional that is.

Another example of a contradiction proof that provides no idea on a constructive proof is the strategy-stealing argument. For certain symmetric games, the second player cannot have a winning strategy. If he did, the first player could "pretend" to be the second player and steal his winning strategy, stealing it from him, a contradiction.

An interesting example is the game Hex. It is easy to show that Hex cannot end in a tie, and the strategy-stealing argument does apply to it. Therefore, it is a first player win. But for symmetric $n$ x $n$, the actual winning strategy is still not known. Thus, this is an example of something that has been proven using contradiction and not constructively (yet).

There is nothing wrong with proof by contradiction. You can show that they work using a truth table. In the end, that's all that really matters, right?

As far as I know, you can't know for certain that something is not provable by a direct proof. However, a proof by contradiction might be an easier way to prove some things, like the irrationality of certain numbers. For example, I have never seen a direct proof of the irrationality of $sqrt{2}$.

EDIT: As Carl Mummert said in his answer, the above part in italics is not true. There are propositions which are only provable by contradiction.

A proof by contradiction can be also be formulated as a proof by contrapositive. If we know $Q$ is false, if we can show $PRightarrow Q$ then we have proved that $P$ is false. Whether you view this as "proof without contradiction" or not is up to you. In any case, they are logically equivalent.

I do believe there are some proofs that are only demonstrable through contradiction, and I'm going to attempt to describe them logically:

Let X be a logical statement such that: X $rightarrow$ y, where y is a known contradiction (such as 2+2=5 in the normal arithmetic structure). Without knowing anything else of X, $neg$X implies nothing and nothing implies $neg$X (and hence is not provable). But, of course, assuming X implies a contradiction, and thus, $neg$X.

This form of statement X is isolated, in that it only relates to itself and the contradiction. I do believe they can be constructed though, for it seems it they can be described.

With that said, in real math and logic, or in general real world scenarios, I don't believe any statements of this form exist, except possibly ones that are constructed to meet this criteria and otherwise meaningless. The proof of the primes was eventually proved without contradiction, to my understanding; until math had been more developed, I think that the statement "the number of primes is $infty$" was basically an isolated logical statement at Euclid's time and for many years after probably, in that there were no other things known to imply it and it didn't imply anything else useful towards its proof.

First of all, this is not an answer to the title but to the aside question and is just an example of why you would prefer a constructive proof to a proof by contradiction. Consider the example below,

Prove that $x^2 = 1$ has a root.

Proof by contradiction: Assume that $x^2 = 1$ has no root. Let $f(x) = x^2 - 1 $ then $x^2 = 1$ has a root if and only if $f(x_0) = 0$ for some $x_0$. By assumption $x^2 =1$ has no root and thus, $f(x) neq 0$ for every $x$. Note that $f$ is continuous and $f(0) = -1$ and $f(2) = 3$. Hence, by the intermediate value theorem, $exists x_0$ such that $f(x_0) = 0$ which is a contradiction. Therefore, $x^2=1$ has a root.

Constructive proof: For $x^2=1$ if and only if $x^2-1=0$ iff $(x-1)(x+1)=0$. Hence, for $x=pm 1$ the equation is satisfied, namely the roots are $-1$ and $1$.

The difference is not about the length of the proofs but the information you have. In constructive proof, you know what the roots are but not in the proof by contradiction. Of course, in proof by contradiction, you could have said "let $x_0 = 1$, then $x_0^2=1$ which is a contradiction since $1$ is a root." but then, it is not a clear distinction between the two types of proofs.

My non-mathematical response.

A == B equals !(A != B)

You always end up with a binary decision, is or is not. And in any language is = !(is not).

But I guess it is too simple to be ok.

Whether a proof is "by contradiction" really just depends on the statement you started with. If your inital statement is $P rightarrow Q$, then showing the equivalent $neg Q rightarrow neg P$ is "proof by contradiction". But in reality, the "direct" proof for $ P rightarrow Q$ is just a proof "by contradiction" for $neg Q rightarrow neg P$. The only reason why we started with $P rightarrow Q$ instead of $neg Q rightarrow neg P$ is our intuition.

This is just my opinion, but also remember that sometimes, it is also very valuable to know what holds if $Q$ does not hold.

An interesting example of this is the entire study of Smooth Infinitesimal Analysis. It relies on not having the law of the excluded middle (i.e. no proof by contradictions are accepted) in order to be valid. Thus if everything provable by contradiction was also able to be proven directly, then there could not be smooth infinitesimal analysis! Look at Bell's book for more details, though the wiki gives a good example.