Fork me on GitHub
Math for the people, by the people.

User login

contradiction

Defines: 
proof by contradiction, reductio ad absurdum
Type of Math Object: 
Definition
Major Section: 
Reference

Mathematics Subject Classification

03F07 no label found03B05 no label found

Comments

Can you support the claim that

"some mathematicians go so far as to reject proof by contradiction as a valid proof technique."

by naming one such mathematician?

how about Brouwer, of "Brouwer fixed point theorem" fame? I think he would have objected to it. See
http://en.wikipedia.org/wiki/Luitzen_Egbertus_Jan_Brouwer

I am talking about present mathematicians; the claim made in the entry is phrased in present time and is in my oppinion misleading.

Regarding Brouwer, do you know how to prove his famous Fixed Point Theorem without contradiction? Do you know any present mathematician that refuses to accept Brouwer's theorem because of this?

I've no idea whether you can prove the fixed point theorem without using proof by contradiction, and I don't know a single living mathematician who rejects proof by contradiction. But to do so has been a position taken by "legitimate" mathematicians, even if most people disagree with it (I certainly do), so I think it ought to be mentioned in the entry, though perhaps with the warning that constructivism/intuitionism is a very minority perspective.

Intuitionistic logic does not accommodate proof by contradiction. My opinion regarding the question of whether or not proof by contradiction is "accepted", is that the modern synthesis is renders this question somewhat moot. More important is a clear understanding of what is needed for a particular proof. An intuitionistic proof is regarded as "stronger" than a proof in classical logic. A finitary, constructive proof with computational complexity bounds would be considered even stronger. On the other side of the spectrum, one might ask "does the proof require the axiom of choice"? If it doesn't, the proof is "stronger".

I am not sure about "famous" mathematicians, but one of my own math professors that I had about four years ago absolutely rejected proof by contradiction. I do not agree with him of course, but I usually do not use proof by contradiction unless I feel it is absolutely necessary or it makes the proof shorter. The professor of whom I speak claimed that there were other mathematicians who reject proof by contradiction.

Perhaps I ought to reword this entry by saying something like "a small minority of mathematicians reject proof by contradiction". Would that be better?

>Perhaps I ought to reword this entry by saying something like "a small >minority of mathematicians reject proof by contradiction". Would that >be better?

No. I absolutely disagree with having such claim in the enciclopaedia.
There are mathematicians who make wrong or obscure claims; that should not be a good reason to mention those claims to mislead the reader.

This makes me think of the whole theory of evolution debate. Claims such as "many scientists say that the theory of evolution is all wrong", only contribute to the general confusion.

But there's nothing "wrong" in itself about rejecting proof by contradiction. It's entirely different to making false claims to have proved something (or being a creationist!). Intuitionism/constructivism is definitely non-mainstream mathematics, but as far as I know it's just as self-consistent as "normal maths".

It's simply a fact that there are respectable mathematicians who have rejected the idea of proof by contradiction (etc.) and that there's a big literature on alternative logics/philosophies of maths. I don't think we should go mentioning them all over the encyclopedia, but surely they have a place in an article specifically about contradictions.

I have to generally agree with silverfish that there is nothing wrong with rejecting "proof by contradiction" BUT only if you are prepared to reject the prinicipal of the excluded middle (PEM): ie that a well-formed statement is either true or false, and nothing in between. People who feel qweeze about proof by contradiction don't seem skeptical about PEM in my experience, but I had a logician once show me PEM implies the validity of proof by contradiction. So if you have PEM as an axiom logic, you have proof by contradiction.

But I really think rmilson has the best point on this: proof is not about being correct, it is about convincing someone else that you are correct. And to the extent that proof by contradiction confusses people, then it is a weaker proof. So a mathematician is well within his rights, and perhaps prudent, to reject one proof technique over another, if he/she feels this better explains it to a someone.

I did once discuss with a colleague the idea if removing PEM as an axiom would make Godel's incompleteness theorem fail, (these proofs are carefully balanced on PEM) or would an alternate version of the problem appear. The real problem was, with middle ground between true and false, nothing made sense! So live in the world we've made, pitfalls and all.

:) I once had a professor say "If you don't assume the axiom of choice, you will prove less theorems." My answer (which I kept to myself wisely) was "Well heck, why not just assume all theorems then!"

In my experience theorems which "depend" on the axiom of choice are one of two types: equivalent to the axiom of choice so you might as well assume the theorem as an axiom/definition of your object (such as every vector space has a basis) or no worse off without the assumption as for example that every ring has a maximal ideal.

So instead of "proving" every ring has a maximal ideal, just use rings which do have a maximal ideal. Logically you are in the same place because you can never find a ring without a maximal ideal because this would contradict the axiom of choice, which you cannot do, and you cannot prove every ring has a maximal ideal without assuming that it is true by means of assuming something equivalent to the axiom of choice. So just as we typically consider only rings with a 1, consider only rings with a maximal ideal in our proofs and no harm is done, and no axioms are added and controversy is averted.

In short, it seems that the majority of us are "okay" with leaving the statement about rejecting proof by contradiction in. I will qualify that statement more.

I think that people ought to be aware that some (albeit seemingly a tiny minority of) mathematicians reject proof by contradiction. In my opinion, whether this proof technique is correct is for the reader to decide. I also think that these posts have made us think more about our mathematical backgrounds and beliefs, which is important to do every once in a while. I am glad that Koro brought up the question to begin with, and I definitely enjoyed reading all of the posts thus far about it.

I seem to have a knack at stirring up controversy here at PM inadvertently. :-) I sincerely hope that I do not make anyone angry with me.

Well, I am off to edit this object. Keep up the intriguing posts. I enjoy reading them.

I would not like to see this left in without a supporting reference.
Further, if ONE mathematician rejects proof by contradiction
i don't think it should be left in.

http://www.cs.man.ac.uk/~pt/Practical_Foundations/html/s18.html

Taylor, Paul
_Practical Foundations of Mathematics_, Cambridge University Press, 1999

My point, which I still mantain, was that the way it is phrased in that entry is misleading. I don't agree at all with entries having claims like "some people agree with this, some people do not" because it gives the wrong idea of mathematics.

A claim like "there are a few mathematicians prefer to work without the principle of the excluded middle" or the like would be less controversial. By the way, I am willing to bet that in no branch of mathematics (except perhaps those which are close to foundations of mathematics) the community works without the PEM; this is only to remark the fact that the claim in the entry is misleading.

A possible fix is to incorporate some of the things mentioned in this discussion to the entry in order to clarify the situation; e.g. some historical remark, or some emphasis in the fact that virtually all of the current mathematics community assume the PEM, and in fact only a tiny amount of the information displayed in the enciclopaedia (or anywhere else) remains valid if you decide to 'reject' it.

Since we have no poll on the distribution of mathematician or their works that do or don't use PEM or contradiction we shouldn't pretend we do. Why bias the reader who may be looking for precisely the mathematics that doesn't use contradiction?

Perhaps we can get away with being mathematicians about it and just describing the facts: PEM implies contradiction. PEM is part of the Principia Mathematica by Russell and Whitehead which is a often cited reference for foundations (there is data on that.) Then say that there are axiomatic constructions of mathematics that do not include PEM but because of the varied axioms the theorems which use PEM may not transfer identically to these other systems. Give an example of that, basic one if you can find it, for instance, can one still prove there are an infinite number of primes? If you give a concrete example like that, then you probably are giving away the bias that we secretly want to give: without PEM, things might be a little to strange .. but maybe the reader will be looking for too strange. But we aren't intimidating the reader with vague "a number of" or "most of" comments.

...Sorry this article is not jammed full of posts. Maybe it needs to be rewritten incorporating the ideas as a completely new article.

Hi all,
I cannot understand that long discussion about this subject. If I can reject a theory with a counter-example, why do I must reject a proof by cotradiction? Someone can explain me that? I think that people rejecting a proof by contradiction, would have to throw mathematical logic into a basket.
perucho
PS. Almost all concerning propositions about the second law of thermodynamics is proven by contradiction. In fact that law is a ``rejecting'' sentence.

Perucho my friend, I thought you, someone grounded in applied theory, would appreciate the freedom of not having just true and false -- aren't the mechanical engineering applications what drove the invention of fuzzy logic? [Fuzzy logic is an honest math in which true and false are 1 and 0 but statements can take on any value in the continum [0,1]. It is really useful in practice.]

A counter-example to a statement P, in logic, is a proof that determines P is false, or more precisely, that there exist an x for which P(x) is false, that is, that it is not true that for all x, P(x) is true. This is not using PEM because it is a proof that P is false. (true and false still exist without PEM, but they may not be the only values.)

However, a proof by contradiction requires PEM. So you can have one without the other.

It is all axiomatic, so a belief is involved somewhere. By default we assume everyone believes the same axioms, until they specify otherwise. It is not different that assuming + is a commutative. Some people will use + for non-commutative, they are out of the ordinary, and so they, not the rest us, should specify how and why they want to use + in a different manner, but they are within their mathematical rights to do so and it doesn't result in throwing out anything.

Actually, to the contrary, it adds to the subject to see alternate proofs to things that don't use contradiction, or better yet, to see problems that simply require such a proof. It tells us what fundamental assumptions must be made (or can be omitted). It makes the subject more general and robust to future changes.

[Just doing my part to make the discussion go on even longer! Sorry.]

Now I can see the point, James. I never had heard about fuzzy logic and what PEM means neither (It's an acronym? It appears neither in the Wiki nor in PM). Coincidently searching at the WEB I found this:
``Modelling and Fuzzy Logic Control of DC-DC Converter for Proton Exchange Membrane Fuel Cell''
So, what a confusion for me!!! I couldn't believe that almost all the PM people discussing about this subject through a lot of replies! I couldn't understand that!
Thanks a lot my friend! (I'll appreciate if you explain me about PEM)
Cheers,
perucho

PEM = Principal of the Excluded Middle, the principal that for a statement S, either S or not-S is true.

For any S, $ S \wedge ¬ S$ is a theorem of the usual propositional logic, but not of intuitionist logic, just like $¬¬S → S$ --- this is why the PEM and proof by contradiction are rejected by intuitionists.

See
http://en.wikipedia.org/wiki/Law_of_excluded_middle
...maybe we should be calling it "LEM"!

You raised a good point here:

>It is all axiomatic, so a belief is involved somewhere. By default
>we assume everyone believes the same axioms, until they specify
>otherwise. It is not different that assuming + is a commutative. Some
>people will use + for non-commutative, they are out of the ordinary,
>and so they, not the rest us, should specify how and why they want to
>use + in a different manner, but they are within their mathematical
>rights to do so and it doesn't result in throwing out anything.

In current mathematics, there are standards, implicit or not, which are adopted by almost all areas. The few mathematicians that adopt different axioms are out of the ordinary among all the existing mathematics. They are very specific cases of specific areas. It is good to have specific information in PM; sure. But this is not the case of the general entry which originated this discussion.

To adopt the PEM is a standard. If you claim that 'some mathematicians reject the PEM' this is suggesting (for the layman) that it is common in mathematics, even if rare, to reject proof by contradiction. I see that as a problem.

I think there has been some confusion in this thread about what the Principle of Excluded Middle is.

silverfish wrote:

> PEM = Principal of the Excluded Middle, the principal
> that for a statement S, either S or not-S is true.

That's what I think it is too. But Algeboy was using it to mean that for a statement S, either S is true or S is false.

Algeboy said that a logician showed him that PEM implies the validity of proof by contradiction. But I don't think the logician could have been using Algeboy's definition of PEM! If I want to prove S by contradiction, I show that not-S is false, and conclude (using PEM, in the form that silverfish gives it) that S is true. But with Algeboy's "PEM" all I could conclude is that S is either true or false, which I already knew before I started.

I wrote:

> silverfish wrote:
>
> > PEM = Principal of the Excluded Middle, the principal
> > that for a statement S, either S or not-S is true.
>
> That's what I think it is too.

Well, except that I think it's a principle, not a principal. It could, however, be the principal principle of classical logic.

ohhhh how embarrassing. And there's a spellcheck button too.

I need to go to PlanetSpelling.

Yes, we should use Law because it is easier to spell!

As for my abusive use of this law/principle, I meant no harm, and I'm certain my logician friend used it correctly when we discussed it. In my mind I don't see any harm done by my cowboy definition (I wasn't writing an article on it). Perhaps you can spot the flaw in my following reasoning though:

If (S or not S) is true then either S is true or not S is true, that is, S is false. So the Law of Excluded Middle implies in part that S is either true or false. So LEM -> S is true or false.

Moreover, if S is true then (S or not S) is true. If S is false then not S is true so that (S or not S) is remains true. So if I assume S must take a state of true or false and no middle value then I get the LEM. So S is true or false implies LEM. So the two statements are equivalent.

It is only if S can have some middle value that I cannot use LEM as logical assumption.

... in any case, fuzzy logic is worth mentioning, even at the expense of my idiocy.

Yeah, I was right, wikipedia said and so was Yark.

http://en.wikipedia.org/wiki/Principle_of_bivalence

I was using the principle of bivalence (interesting we are back to prinicples now) which implies the law of the excluded middle.

Thanks for cleaning up my use of the terms yark.

Thanks Silverfish for clear me the PEM meaning. I did mention about the subject by simple curiosity (all that lot of replies!). I'm really not interested in that area.(engineers we are not mathematicians!)
perucho

> Yeah, I was right, wikipedia said and so was Yark.
>
> http://en.wikipedia.org/wiki/Principle_of_bivalence

IMHO the Wikipedia seems a bit confused in that article,
in that it describes "undecidable" as the middle that is
excluded between "true" and "false". In mathematics,
"undecidable" is more often paired with "provable" and
"disprovable" (negation is provable), i.e., it describes
the status of a proposition with respect to a theory
($\vdash$) rather than with respect to a model ($\models$).

I suppose one way of viewing the whole thing is to say that
the principle of bivalence applies to models, whereas the
law of the excluded middle rather applies to theories, since
anything used in proofs have to happen on the theory side.
A derivation of LEM from PB would then have to take place
in the metatheory, which of course opens up a whole range
of possibilities to get it wrong by confusing the levels, but
this discussion is probably there already anyway.

One way of deducing LEM from PB could be to argue that
any formula of the form $P \vee \neg P$ under any bivalent
interpretation will be true, so it is a natural theorem and
harmless to add as an axiom. (Whether this is the "logician
friend's proof" referred to above is of course another matter.)
I can imagine intuitionists objecting to such a derivation of
LEM from PB, however -- just that something never is wrong
doesn't necessarily mean everybody thinks it is always right.

'''But there's nothing "wrong" in itself about rejecting proof by contradiction.'''
Neither is there anything wrong with rejecting the existence of infinite sets.
However, the vast majority of living mathematicians choose to believe otherwise.

I think intuitionism merits an article of its own, which this article should refer to, rather than making vague claims about "some mathematicians". Unfortunately, no such article exists, and I don't feel qualified to provide one.

I agree. I think it would also be nice to have an overview of logic, where classical and non-classical logical systems are listed.

I'm just curious for an example of a valid proof by contradiction which contains (perhaps as the proof to one of its lemmas) another proof by contradiction.

Although there is nothing in principle to prevent such a situation from arising, proofs by contradiction aren't all that informative and can be dangerous pedagogically (since they rely on assuming that if you seek a contradiction and find one that you also haven't made a subtle mistake)--also I've seen a lot of proofs by contradiction which were really proofs of the contrapositive in disguise. Is there a context in which this question arose?

> I'm just curious for an example of a valid proof by
> contradiction which contains (perhaps as the proof to one of
> its lemmas) another proof by contradiction.

The proof of the Feit-Thompson Theorem (http://planetmath.org/encyclopedia/FeitThompsonTheorem.html)is a proof by contradiction that includes countless lemmas proved by contradiction.

Browse the proof here (after gluing the two parts of the url together):
http://projecteuclid.org/DPubS?service=UI&version=1.0
&verb=Display&handle=euclid.pjm/1103053941

Is there a context in which this question arose?

Yes, Wkbj79's entry on proof by contradiction. An earlier version of the entry had set off a firestorm of questions regarding what professional mathematicians disapprove of proof by contradiction. Paul Nahin names two in his book on Euler's relation, (he does not count Marylin Vos Savant as such). The current version of the entry reads:

"Proofs by contradiction can become confusing. This is especially the case when such proofs are nested; i.e., a proof by contradiction occurs within a proof by contradiction."

It was that last sentence specifically which made me wonder.

Me personally, I'm not a professional. Amateurs are almost certain to encounter proofs by contradiction very early on (quite likely Euclid's proof that there are infinitely many primes). My first impression was that they were somehow very fair-minded. Pros can be notorious for dismissing things out of hand with great speed (a few cranks make them suspicious of all strangers). A proof by contradiction, in my opinion, shows a willingness to consider a possibility other than the one one is trying to prove. Instead of just dismissing the other, a proof by contradiction, at least a valid one, gives the other a fair shake, not dismissing it until conclusively proving why it's wrong.

Of course an attempted proof by contradiction can fall prey to a subtle mistake that invalidates the whole thing. But so can an attempt at a proof by construction, especially if one does not properly check that a specific example of the construction is indeed valid.

Thanks for the example. Our PM entry here says the proof is 255 pages long. The link you provide to Project Euclid leads to a document that is not that long, but it does look quite convoluted.

> Thanks for the example. Our PM entry here says the proof is
> 255 pages long. The link you provide to Project Euclid leads
> to a document that is not that long, but it does look quite
> convoluted.

Sorry, the correct url is:

http://projecteuclid.org/DPubS?service=UI&version=
1.0&verb=Display&handle=euclid.pjm/1103053941

Oh I see now.

I basically agree with you. But I'd add that one pitfall is a feeling that proving "If A, then B" is easier using a contradiction argument, because you get to assume more A _and_ not B (which somehow sounds more fun), than a direct argument where you only get to assume A (or not B if you wish to prove the contrapositive). All of this is utterly separate from the philosophical question that led to the firestorm, in which I have no pony since I'm the type to see math as a formal system so that axioms can either be taken or left based on personal preferences and pragmatic goals.

I've heard it said that proofs by contradiction are usually draft proofs, because of exactly this freedom found in assuming more, but that in the polishing process one hopes to tighten the idea of the proof to the point that you can show the nuts and bolts of "why" there was a contradiction, i.e. find a direct argument.

I typically get confused on some mathematician's contradiction proofs, because many fail to announce what they are attempting to do. When I start contradiction proofs, I state explicitly "To prove that P implies Q I shall obtain a contradiction by assuming that P does not imply Q." I find that many mathematicians leave it to implicit statements that this is what they are attempting to do, and it really confuses me when I read some proofs.

I'm a few steps below an amateur in this regard, but I find it frustrating because some contradiction arguments aren't as blunt as merely assuming the negation of some given premise. Sometimes what I see is someone will work the proof down a few steps and arrive at a fact, and make a restatement of the desired conclusion that is equivalent with the one given. THEN they assume the negation of that. This is where the process gets confusing, especially if they don't announce explicitly what it is they are doing.

Philosophically, I find nothing wrong with contradiction arguments. To quote Atlas Shrugged, "Contradictions don't exist in reality, if you find one check your premises."

Forgot to mention! If you've done any work with symbolic logic (specifically using Natural Deduction) then many theorems are deduced by nested contradiction arguments. Most notably the law of excluded middle.

There might be another way to do that one without nested contradiction arguments, but that's the way I've always done it.

Of course if you're into that intuitionism thing, then you'd bark at me for equating reductio ad absurdum with proof by contradiction. Just thought I'd add that little thing.

I think I may have seen one or two contradiction proofs like that.

Now I can't remember who it was here who said that it's always possible to turn a proof by contradiction into a direct proof. I've thought of trying to do that to Euclid's classic proof that there are infinitely many primes. What I came up with just didn't have the same punch to it, and maybe I didn't even succeed in deriving the direct proof. (I've also thought about doing that to a proof that a given number is irrational, but with that I haven't gone beyond just thinking).

The ability to turn a contradiction proof into a direct proof rests on a property of logic called completeness. Making that extra assumption (for a contradiction) makes things easier in most cases, but in theory you shouldn't have to.

If you're working in formal mathematical systems, then making such a claim about contradiction proofs is unfounded, thanks to the famous incompleteness theorems.

In any other setting the same statement is always unfounded. If you're using normal reasoning then you have no tools with which to make a completeness theorem about your everyday reasoning abilities, lest you beg the question. Sure in theory you 'should' be able to make the direct argument, but that's not a known fact until you DO it.

That said, I love contradiction arguments :) Especially old ones, I really like to look at Euclid's arguments. Glancing back into the past is a great thing to see, deductive proof was one of the best things left by the Greeks. Also the discovery of the irrational numbers I guess, since that's what most of our real numbers are.

Not so long ago, there is Cantor's famous diagonal proof and
it's descendants, Turing's halting theorem and Goedel's
incompleteness theorem. All three of these are examples of
proof by contradiction raised to a fine art form!

It would be really neat if someone around here would write up
a popular article about famous impossiblity theorems:

Irrationality of square root
Infinitude of primes
Irrationality of pi
Impossibility of trisecting angles
Cantor's diagonal argument
Turing's halting problem
Goedel's incompleteness theorem

The nice thing about these is that, whilst they are deep
results which have had a profound impact on the course of
mathematical history, at the same time, their proofs do not
require elaborate machinery, so can be explained to the
person on the street without first having to require that
person to take a few classes in math. To me this is one
of the surest signs of the sublime in mathematics --- not
only is a result deep and has profound philosophical
ramifications, but the proof is elementary and based on
a few simple, but subtle, concepts even if working out and
checking the details may involve some tedium.

Subscribe to Comments for "contradiction"