Ain't No Proof By Contradiction

[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.

 

[Hurkyl]

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?

 

[Cyrus]

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.

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.

 

[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.

 

[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

 

[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...

 

[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:

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...

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.

 

[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:

A proof of $\neg A$ is a procedure that transforms any hypothetical proof of $A$ into a proof of a contradiction."

 

[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

 

[LeBrad]

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.

"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?

 

[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?

 

[honestrosewater]

Okay, this is what I thought. It would be double negation that causes problems.
http://mathworld.wolfram.com/IntuitionisticLogic.html

"Intuitionistically, Reductio ad absurdum only proves negative statements, since ¬¬A → A does not hold in general. (If it did, LEM would follow by modus ponens from the intuitionistically provable ¬¬ (A or ¬A).)"
- http://plato.stanford.edu/entries/logic-intuitionistic/

 

[Hurkyl]

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.

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)

Obviously they do not accept the Axiom of Choice, since, obviously no one can constructively make these choices.

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

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

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

 

[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.

 

[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

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.

 

[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.

 

[Hurkyl]

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!

 

[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.

 

[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.

 

[Hurkyl]

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 modeled 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

 

[matt grime]

To use a phrase in some lecture notes i once saw in a footnote: that is "recall" in the mathematical sense of "see for the first time".
If I can check, since I don't understand this, why is not(A) the right half plane? Why is it not "the right half plane plus the y-axis"? This is just the Heyting thing, I suppose, where not(A) is something like the interior of the closure of the complement of a. Would that, or something like that, be why?

 

[Hurkyl]

that is "recall" in the mathematical sense of "see for the first time".

Hrm. It really is a bad phrase, isn't it? I should stop using it, I suppose.


The model for a Heyting algebra only uses the lattice of open sets of the space X, rather than an entire subset algebra of X. Since the right half-plane plus the y-axis is not open, it's not in the lattice. The right half-plane is as close as you can get.


In the definition of a Heyting algebra, the implication operator → is defined so that A → B is the maximum of the objects C such that (A and C) <= B. Negation is simply defined as (not A) = A → 0.

So, the negation (aka pseudocomplement) of a truth value A is the largest truth value B such that A and B = 0. Thus in the open set model, negation is the same as exterior.


I was sure I've read that any Heyting algebra can be modeled as the open sets of some topological space, but Wikipedia suggests that's not true. But the other way is certainly true -- the lattice of open sets on a topological space is a Heyting algebra.

Aha, I found what I read... I missed a word: Saunders-Mac Lane says the "typical" model is the open sets of a topological space.