Ain't No Proof By Contradiction

1. Jun 3, 2005

LeBrad

I recently saw something that said some mathematicians won't acknowledge proof by contradiction. What is the reason for that? Could somebody elaborate on this for me.

2. Jun 3, 2005

Hurkyl

Staff Emeritus
I have no clue -- proof by contradiction is an essential mathematical tool.

Maybe it came from someone on yet another rant about how "obvious", say, treating 0 as a number leads to a contradiction, and since mathematicians wouldn't acknowledge his "proof", he leaped to that conclusion?

Last edited: Jun 3, 2005
3. Jun 3, 2005

Cyrus

I think what they meant was that by finding a contradictory case, they can reject a proof, thus they won't acknowledge proof via contradition. It just means there is an illogical step in the proof that gives anwsers that are not experimentally observed. If your proof says something is true, but you do the calculation and get a different anwser, we can logically say that something is wrong in your proof, and we have provided sufficient contradictory evidence to reject it.

Last edited: Jun 3, 2005
4. Jun 3, 2005

mathwonk

some people have trouble psychologically with an argument that does not even attempt to show any connection between the hypothesis and the conclusion. I call these "chicken little " proofs, and there are lots of them in my favorite subject differential topology: e.g. "if this theorem were not true then the sky would be falling, but the sky is obviously not falling, so the theorem must be true." yeah?? sooo?

e.g. if there is a never zero smooth vector field on a 2 - sphere, then there is also a smooth homotopy between the identity map and the antipodal map of the sphere, but that would imply by stokes theorem, and integrating the area form, that -4pi = +4pi, and that is false; so back there somewhere at the beginning of this argument, in fact there must be a zero of that vector field.

oh yeah??? well where is it??

that sort of thing bothers some people, i.e. proofs of existence of solutions that do not try to find them or even approximate them. but merely try to show that if there is no solution then dewey was actually elected president instead of truman.

Last edited: Jun 3, 2005
5. Jun 3, 2005

robert Ihnot

This is about the Intuitionists and their rejection of the logic of the excluded middle, that is, the acceptance of the "Either A or not A" case.

The reason for this was their dislike of Cantor's transfinite and a demand for constructive proofs. Obviously they do not accept the Axiom of Choice, since, obviously no one can constructively make these choices.

Of course, this reduces the amount of math that can be proved.http://cs.wwc.edu/~aabyan/Logic/Book/book/node70.html [Broken]

Last edited by a moderator: May 2, 2017
6. Jun 3, 2005

1+1=1

Proof by contradiction? This useful technique assisted me in all of my proofs classes while in college. To me, using a proof by contradiction is great. You set the proof up for contradiction and soon the proof comes tumbling down...

7. Jun 4, 2005

HackaB

It's funny that Brouwer was a constructivist, since the proof of his fixed point theorem is usually given as a proof by contradiction.

edit:

Yeah, I don't know what one would do without it. To me, some of the neatest proofs by contradiction are those where you can hypothesize a "least counterexample", and then proceed to construct a smaller one. Someone recently gave a proof like that here for Sylvester's line problem.

Last edited: Jun 4, 2005
8. Jun 4, 2005

honestrosewater

I've only met intuitionistic logic in passing, but I thought they were more concerned about positive existence proofs, rejecting a proof that x exists because it is impossible for x to not exist. So I don't see why they would have a problem with proof by contradiction. And look what I found in robert Ihnot's link:

9. Jun 4, 2005

robert Ihnot

HackaB: It's funny that Brouwer was a constructivist, since the proof of his fixed point theorem is usually given as a proof by contradiction.

This seems to be true. I have a reference which states for the fixed point theorem: "The case n = 3 was proved by E. J. Brouwer in 1909. Hadamard proved the general case in 1910, and Brouwer found a different proof in 1912. Since it must have an essentially non-constructive proof, it ran contrary to Brouwer's intuitionist ideals." http://www.absoluteastronomy.com/encyclopedia/B/Br/Brouwer_Fixed_Point_Theorem.htm [Broken]

Last edited by a moderator: May 2, 2017
10. Jun 4, 2005

LeBrad

"Intuitionists" sounds familiar, I'm pretty sure that's what it was talking about.

So do these people lose anything by thinking this way? Or can everything be proved in a different manner, with proof by contradiction just being a simple first choice in many cases?

11. Jun 4, 2005

Icebreaker

How would you prove a theorem about the nonexistence of solutions to an equation, like Fermat's last theorem, without proof by contradiction? I'm not saying to look at Wiles' proof, I'm just saying that, hypothetically, how would it be done?

12. Jun 4, 2005

honestrosewater

Last edited: Jun 4, 2005
13. Jun 4, 2005

Hurkyl

Staff Emeritus
Actually, proof by contradiction is partially valid in intuitionist logic:

$$P \rightarrow (Q \wedge \neg Q) = \neg P$$

is an identity in any Heyting algebra. (The problem with proof by contradiction in general is that $P = \neg \neg P$ is not generally true)

(Heyting algebra is to intuitionist logic as Boolean algebra is to ordinary logic)

Actually... the axiom of choice is the theorem of choice in constructivist mathematics.

He proved his theorem before he switched -- IIRC, his theorem is not valid in general intuitionist logic.

14. Jun 4, 2005

mathwonk

re brouwers mathematics: there is a difference between being able to give a non constructive argument and being satisfied with it. mathematicians are usually not like religious zealots. they are often willing to use methods they may not prefer.

I had a very sharp friend who kept struggling to perfect an almost finitistic proof of brouwers fixed point theorem. his idea was to diminish the role of the non intuitionistic part, or keep it confined to one final step in the argument.

i never understood why he did anything he did, but he definitely opened my eyes to distinctions that had never been visible before.

15. Jun 4, 2005

robert Ihnot

The intutionists, as I had thought, did object to the Axiom of Choice:

Zermelo gave the standard argument that the axiom of choice implies the well-ordering principle. He argued that the axiom of choice was self-evident. The reactions to the proof came immediately. At the end of a note sent to Mathematische Annalen in December 1904, Borel states:

It seems to me that the objection against it is also valid for every reasoning where one assumes an arbitrary choice made an uncountable number of times, for such reasoning does not belong in mathematics.

As for the constuctionists: Constructive mathematics can mean many different things. The common thread is that some attention is paid to the distinction between the actual construction of a mathematical object and an indirect proof of its existence. The term was often used to indicate an avoidance of the axiom of choice---a principle that asserts the existence of a function with certain properties in situations in which it is particularly unclear how such a function could be constructed. It is also used to refer to the construction and analysis of algorithms, more-or-less ready to implement on a computer, in various branches of mathematics.http://www.math.fau.edu/Richman/HTML/CONSTRUC.HTM [Broken]

On the law of the excluded middle from the above reference: In the present context, the characteristic property is the rejection of the law of excluded middle. It is somewhat remarkable how this one metamathematical move embodies the essence of constructivism. Constructivism suggests rejection of the law of excluded middle because there is generally no computational basis for asserting "p or not p". For example, consider the statement, provable using the law of excluded middle, that some digit appears infinitely often in the decimal expansion of pi. Here the existence of an integer is claimed to be proved, but no method for its computation is indicated by the proof. It is less clear, but born out by experience and theoretical constructions such as recursive realizability, that theorems proved without the law of excluded middle automatically have a computational interpretation.

Last edited by a moderator: May 2, 2017
16. Jun 4, 2005

mathwonk

actually theorems like the intermediate value theorem are to me something of a hoax. i.e. one claims such and such a continuous function has a "real" zero but one cannot find one. why not? because one cannot actually find most real numbers, due to the large (infinite) number of terms in their decimal expnasion.

so a more honest version of the theorem and entirely equivalent if you think about the meaning of "real numbers" and the proof of the IVT theorem, is to say directly that one can always find a rational number, or a finite decimal, at which the value of the function comes as close to zero as desired. that is really all that is proved. the rest is sleight of hand.

so in fact virginia there is no square root of 2, but there are arbitrarily close approximations. and if you then define the statement "there is a real square root of 2" to mean exactly the situation above, then you may say that sentence truthfully, but nonetheless tautologically.

i.e. it is really nonsense to claim that an infinite (Cauchy) sequence of rational numbers "is" a real solution to an equation, where the real solution is defined as the equivalence class of those rationals, in any sense other than that above.

i suspect this is where we lose the loyalty of most of our students when we started pretending this nonsense was the plain truth.

I.e. we should just admit that the language we use is a idealization intended to deal with the unfortunate state of affairs as they actually exist. Or perhaps more accurately historically, there is no satisfactory way to render all the points on a continuous line into computable "numbers".

hence many of us enjoy the axiomatic approach to real numbers, rather than the symbolic one, since it frees us entirely from any calculation at all.

[there chidren, i have proved there is a real solution to any equation of a certain kind but not only do i not display one, i do not even display any actual continuous functions, nor in fact do i ever show you a real number. my hands are entirely clean!]

I loved this sophistry as a young math major, but my students hate this sort of smoke and mirrors.

Last edited: Jun 4, 2005
17. Jun 4, 2005

Hurkyl

Staff Emeritus
In constructivism, or at least some flavors, the axiom of choice can be proven. I think the basic idea is that you can tweak whatever method you used to construct a given set to produce a choice function on that set.

Or, alternatively, you simply can't create anything so complicated you can't construct a choice function for it.

I'll admit I'm not speaking from experience -- a friend of mine's field is nonstandard analysis, a topic so dependent on the axiom of choice that you can't even get to square-one without it. The whole thing is somewhat magical in how it works, so some would view results he quoted with suspicion (especially those who distrusted the axiom of choice). He was talking to a constructivist, and was certain he'd get that treatment, only to hear the guy state that the axiom of choice was a theorem, so everything was fine!

P.S. I can't tell how much of that mathwonk believes, and how much of that is him relating beliefs of others!

18. Jun 4, 2005

mathwonk

for me math is not necessarily about belief, but includes the open consideration of logically equivalent options.

as i said, i myself liked the axiomatic approach (a real number is an element of a complete archimedean ordered field), but after trying for years to teach normal human beings, i.e. students who have still enough courage not to be cowed by what they are handed by their elders, I see other points of view as well.

I was able to remember how hard I worked as a student, to give up the desire to see a solution to a problem that had been "proved" to have one. I.e. it is an act of faith to accept a new meaning of the words one has always used, and to accept that a solution exists not because one is convinced of it, but because one has been force fed a new definition of the word "solution".

I think it would be useful in teaching, if we were more straightforward about how a concept changes when we move to an abstract treatment of it.

It is frustrating for meto talk about real numbers every year in a calculus class in which one never defines them. A comanion thread, has a vigorous discussion of whether or not 1 = .999... , showing clearly that many students who perhaps have studied calculus, would not know a real number if it asked them for an autograph.

does it make sense to claim to have convinced a student of the truth of a theorem, like IVT, that is true over the reals but not the rationals, if one has never explained the difference? And double that for todays students who think a real number is a decimal just long enough to fit on their calculator display.

astonishing as it may seem, every year i have students who reveal that they believe all real numbers are integers. yet they memorize the statement of the IVT and assert its correctness, because they were told it is so. Logical consistency plays no role at all in their allegiance.

so i guess i am finally saying the thread on 1 = .999..., as trivial as it seems, is actually addressing a key misunderstanding of todays calc students.

Last edited: Jun 4, 2005
19. Jun 5, 2005

matt grime

Another thing Brouwer came to think ought to be part of proofs (I think this is intuitionist, but I'm not sure) is that a proof that A or B holds is only acceptable if one can prove explicitly A holds, or, if not, then we can prove B holds. I suspect this is related to the rejection of proof by contradiction since we can not show that not(not(A)and not(B)) is A or B.

20. Jun 5, 2005

Hurkyl

Staff Emeritus
Right. We have $A \vee B \implies \neg(\neg A \wedge \neg B)$, but the other way we only have $\neg(\neg A \wedge \neg B) \implies \neg \neg(A \vee B)$

Here's a model in the plane that demonstrates these: (recall that values in a Heyting algebra, and thus intuitionistic logic, can be modelled as the open sets of some topological space)

A = left half-plane
B = right half-plane

A or B = plane minus y axis.

not A = right half-plane
not B = left half-plane
not A and not B = 0
not(not A and not B) = whole plane

not (A or B) = 0
not not (A or B) = whole plane

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook