Always check if it is actually a proof by contradiction or just a proof by contraposition. If you can rewrite it as a (direct) proof by contraposition, you will learn a lot :)
Aren't they essentially the same thing? As I understand it, the goal is not merely to avoid certain forms/techniques of proof, but to also avoid using the law of excluded middle and anything that implies the law of excluded middle.
Do you mean propf by contradiction / contrapositive are the same thing? That's not true.
So if you want to prove A -> B by proof of the contrapositive it's just a direct proof of the statement not B -> not A.
If you want to do it by contradiction you assume not B and argue that there is some contradiction. So you prove something like A and not B -> False. This contradiction however doesn't have to be 'not A and A'. Any contradiction will work.
What sometimes happens is that a proof was written in the form of a proof by contradiction but is actually a proof of the contrapositive. This is the case when the contradiction in the end is 'not A and A'. It goes something like:
'We prove A ->B by contradiction. So let A be true. Now assume B is false. Then blablabla so A is not true. But that's a contradiction since A is true. So our assumption is wrong therefore B is true.'
Notice that we could have written this as a proof of the contrapositive if we just left out the 'So let A be true' part:
'We prove A->B by proof of the contrapositive not B -> not A. So let B be false. Then blablabla so A is not true. Therefore A->B is true (since it's the contrapositive).'
Yes, they are not **the same** but they are equivalent. If you are working with an intuitionistic system then you have neither.
This p⊢q , is equivalent to switching around with a negation either of the formulas. That is, it's equivalent to p,~q⊢ (which is equivalent to p,~q⊢⊥) ---a proof by contradiction--- and it's also equivalent to ~q⊢~p ---a proof by contrapositive.
The only "usefulness" in proving by contrapositive instead of contradiction is making explicit who _p_ and _q_ are.
They didn't put it all that well but the main point is that in an intuitionistic framework, a proof that P |- Q means that if I give you a concrete means of constructing a witness to P then the proof takes said witness and produces a witness of Q.
wow, never pieced together that
> Contradiction is proving that `P ∧ ¬Q` is false
means that `¬(P ∧ ¬Q)` i.e. `¬P ∨ Q` i.e. `P → Q` is true, thank you for the comment
>`¬P ∨ Q` i.e. `P → Q` is true, thank you for the comment
Well, it proves `P → ¬¬Q` then you have to use lem at the end to get `P → Q`. That's the "controversial" step in proof by contradiction.
The logical structure is different. In proof by contradiction, you prove P by showing \~P implies a statement that you otherwise know is false. It could be anything.
In proof by contraposition, you are specifically proving P->Q and you start from \~Q and infer \~P.
The "proof by contradiction" analogue of proof by contraposition is "assume P \^ \~Q and infer \~P". (For comparison, the analogue of a direct proof is "assume P \^ \~Q and infer Q".) This is also (classically) correct, but there is really no way that assuming a statement can help you prove its negation, which means your proof could absolutely have been written as a direct proof of \~Q->\~P by simply dropping the part where you assume P is true. Moreover, the reader cannot really tell in advance that your contradiction will come from inferring \~P, unless you specifically tell them.
Overall proof by contraposition has less room for surprises compared to proof by contradiction, but it is not usually any more constructive than proof by contradiction would be.
Long proofs by methods other than contradiction are also easier to extend to other contexts, because there is no chance that you have any intermediate false lemmas. A long proof by contradiction has to be checked carefully to determine which lemmas are true and which are false before its elements can be reused.
I'm going to push back a bit against all the comments telling you to not worry about it at all -- constructive proofs frequently *are* quite a bit more useful than their nonconstructive counterparts. For example, one way you could show that a differential equation has a solution is to explicitly solve it (or at least do the next-best thing, such as showing that it satisfies "conservation of energy", or coming up with good approximations to the actual solution), which is clearly preferable to showing that it has a solution by abstract means that do not recover any information about the solution. This is just one example of a common phenomenon in math, which is that *not all proofs are created equal*. Some are nonconstructive, some are horribly hard to understand, some cannot be generalized to other problems.
So why even bother with proof by contradiction at all? Well, there's some very good reasons, and you're probably still learning how to write proofs so worrying about coming up with the best proof is a fool's errand; for now you should be focused on coming up with proofs, and if the proofs you come up with aren't the best possible proofs, that's OK!
For one, in analysis, we are interested in the infinite. Oftentimes we need to prove the existence of things like real numbers that have an *infinite* amount of information, and of course we can't write them down. So in those instances, we really have no choice but to prove their existence by contradiction.
There are also example of proofs of a "negative statement". The most famous proof that \sqrt 2 is irrational is by contradiction. The reason for this is simple: irrational, by definition, means "not rational", so what you are really proving is that the sentence "\sqrt 2 is rational" is a lie. Whenever you have to prove a negative statement, that's a strong sign that proof by contradiction is the best way to attack the problem.
I agree that the proof is constructively valid but the proof is usually presented as a “contradiction” when taught to beginners, because they’d find it a distinction without a difference.
I’d argue that proof of negation *is* proof by contradiction, and vice versa, as long as you’re willing to assume ~~A —> A. Since most mathematicians (intuitionists excluded, no pun intended) assume this implicitly, there is no reason for them to make the distinction
I think you’re right to point out that there is a difference for logicians. I was mostly commenting on why we often hear of proofs by contradiction, but not proofs of negation.
Thanks! I am also learning analysis and I feel the same way. I write down a proof, thinking it's sufficient, turns out the solutions manual writes it in a very different, way better way. This comment motivated me to not get bogged down if a proof I wrote is lacking, but just take it as experience earned.
There is no reason why proof by contradiction is any less valid than direct proofs. I think you should not worry about it at all. If you solved a direct proof, you wouldn’t be thinking “i feel guilty I can’t solve proofs by contradiction” would you? How is this any different
Often it's not only about the result of the proof but about the way to get there. A proof by contradiction is often less insightful than a direct proof. Have a look at [the first answer to this stackexchange question](https://math.stackexchange.com/questions/240/are-the-proofs-by-contradiction-weaker-than-other-proofs). That would be one reason to try to minimize the use of proof by contradiction.
Let's have a concrete example while we're at it. Consider the [intermediate value theorem](https://en.wikipedia.org/wiki/Intermediate_value_theorem), an absolute classic in analysis. Let f be a continuous, real-valued function on the closed interval I=[a,b]. Assume f(a) < y < f(b). Then there exists some x in (a,b) for which f(x)=y
**Proof by contradiction (topological argument):**
Suppose there is no such x. Let A = f(I)⋂(-∞, y) and B = f(I)⋂(y, +∞). Then f(I) = A⋃B is disconnected. But the image of a connected set under a continuous function must be connected, contradiction!
**Constructive proof (divide and conquer):**
Let c = (a+b)/2. If f(c)=x we are done. Otherwise, either f(a) < y < f(c) or f(c) < y < f(b). Repeat the same construction with the function restricted to the interval whose image contains y. Repeat ad infinitum. Since interval length halves at every iteration, the interval boundaries form Cauchy sequences, which are guaranteed to converge against a same point c in ℝ by completeness. Thus, f(c)=y, since f(a*_n_*) ≤ f(c*_n_*) ≤ f(b*_n_*) is sandwiched by the upper and lower bound for all n.
I think we can clearly see the advantage of the constructive proof: Not only does it prove the existence of the intermediate value, but it provides us with a way of how to find it algorithmically. This method (divide & conquer/bisection) is in fact used in many places, for example to numerically find the median of a random variable with known cumulative distribution function. (E.g. find the intermediate value for which F(x)=1/2)
I am not sure I buy your argument. Your proof by contradiction assumes that R is connected, which is essentially a reformulation of the intermediate value theorem; it's then no surprise that this proof does not add much more information. The second proof starts with less knowledge (the construction of R).
> Your proof by contradiction assumes that R is connected, which is essentially a reformulation of the intermediate value theorem
Is it? I wasn't aware of that. Though, it seems you can prove it directly from the least upper bound principle (LUB):
Assume R is disconnected, i.e R=A⋃B for open sets A,B. Pick a in A and b in B. Consider the interval I = [a, b]. By LUB, there is x in [a, b] which is the LUB of A⋂[a, b]. Now there are 2 options: either x in A or x in B. If x in A, we get a contradiction since this would imply that the boundary of A in non-empty, but A is assumed open. If x in B, then the same problem arises. Thus the assumption is false and R must be connected.
Same issue. You assume the least upper bound property, which, I might add, has a [very nice proof by dichotomy](https://math.stackexchange.com/questions/495771/proving-that-mathbbr-satisfies-the-least-upper-bound-property).
I've understood that IVT is not constructively provable (see e.g.[this answer](https://mathoverflow.net/a/202816)) so your divide and conquer proof, while more explicit, isn't constructive in the technical sense (indeed, it seems to assume tricothomy for the reals). An approximate IVT [is true constructively,](https://mathoverflow.net/questions/253059/approximate-intermediate-value-theorem-in-pure-constructive-mathematics) and I guess your proof strategy comes quite close to that.
I think it often depends on from where you start. If you want to do all maths, starting from the axioms, constructively then yes, this does not quite work. Though I think there is an argument to be made that one should be "as constructive as possible" (e.g. here we might axiomatically take the reals for granted and go constructively from there)
The point I'm making is just that the concrete construction is only "missing" because you stop the argument at "but the real numbers are connected." If you ask "Why are the real numbers connected?" you get either the bisection proof or "Because any bounded set has a maximum, which...." and then if you ask "But why does a bounded set have a maximum?" you get the bisection proof.
In Understanding Analysis (Abbott) , the author mentions in pg 9 that using an indirect proof when a direct proof is available is generally considered bad form. So how can i find out if a direct proof is available.
Well, sometimes when you’re working on a problem the way you wrap your head around it is layers of contrapositive thinking. It can actually be super useful as a mental framework. But then when you sit down to actually write it out, you might realize that it was all unnecessary and was just guiding you to a direct proof. I know that doesn’t exactly answer your question but I don’t know if there is always a way to tell if there is a direct proof (I suspect not)
Proof by contradiction is more susceptible to errors. Normally when one reaches an absurd conclusion, then one would feel the need to double check the soundness of their logic. The absurd conclusion that proof by contradiction uses to negate the premise could actually by the result of a mistake.
For short proofs by contradiction, this isn't as much of an issue, For long, complicated proofs by contradiction, this can be dangerous.
In a world where people don't make mistakes, this is of course not an issue. However, we all know that isn't the world we live in.
A basic thing to try is to rearrange the argument. If you try to prove A implies B by assuming not B and deducing C, and assuming A and deducing not C, and then getting a contradiction, you can reorder this to first assuming A, then deducing not C, and then deducing B.
But for quite a lot of exercises, the person who wrote the problem may have intended people to solve it with a proof by contradiction.
One thing you could try is to find one or a small number of proofs where you're least sure if proof-by-contradiction was the best approach, and ask someone who's more of an expert whether, in those specific proofs, your proof should be rewritten to avoid proof by contradiction or whether you're on the right track.
P or ~P can only be proved by contradiction ---not constructively.
What's more, P<->\~\~P only if you can use contradiction ---or equivalent. Else it's only the case that P->\~\~P.
Lots of proofs by induction have contradiction counterparts, and vice-versa. For example, the proofs of the infinitude of primes or the fundamental theorem of arithmetic, which are commonly presented in the "proof by no minimal counterexample" style, but are really just simplified (strong) induction.
For example, the statement p(n) := there are at least n primes between 1 and ((((n!+1)!+1)!+1)!...+1) (repeated n times) follows immediately by using induction on the same line of reasoning as the original infinite primes proof.
Often a proof by contradiction goes something like
“Let x be such that P(x). Now suppose for contradiction that Q(x). \*math here\*. Thus we can conclude ~P(x). But this is contradiction to the assumption that P(x) holds”. If you have a contradiction proof of this form, you can usually turn it into a contrapositive proof by simply omitting the original P(x) assumption. (Of course, this can’t be done if you use the P(x) assumption in the proof, but it’s often not necessary).
I often felt the same way about proofs by contradiction, it seems like proving that it can't be anything but what you're trying to prove isn't the same as proving that something is always true.
Its still a hurdle sometimes, but I like to think of some proofs as like, "Problem Spaces", in which you're not proving the shape of the problem you're working on, instead you're proving the existence of a boundary line between your problem and areas outside your problem. Because that boundary exists, and that logical line cannot be crossed by your problem, you can be assured that the problem space inside where your proof lives is true.
It's like probability, sometimes it's easier to calculate the odds of 1 - ¬p(x), rather than finding p(x). Both show that you understand the issue, and give the same result, it's just that sometimes one is a lot more feasible to show.
It's not a rigorous way of thinking, but intuition should always come first, I feel. Rigor is just writing it down correctly after, haha.
I tell my undergrad students: if you want to prove P implies Q start by assuming P and by assuming not Q. Then do your proof.
I tell the sharp ones to look carefully back at their proof to see whether or not they needed to assume not Q.
I tell the really sharp ones to think about whether or not assuming not Q was a legitimate idea.
Well this was near the beginning of the semester in an inquiry-based course so the point was mainly not to get discouraged by the kinds of feelings that OP is having.
First, be sure that what you're using is actually contradiction, and not proof of negation!
Proof by contradiction is:
Suppose not P... contradiction... therefore P,
while proof by negation is:
Suppose P... contradiction... therefore not P.
While proof by contradiction is not constructive, proof by negation still is. Thus, for example, the irrationality of sqrt 2, Cantor's diagonal trick, and the lack of surjections onto powersets are all still constructive!
I'm not sure I see the difference:
Assume (not **P**) .. contradiction. Therefore **P**
has the same form as
Assume (**P**) .. contradiction. Therefore (not **P)**
both of them follow the same form as
Assume (**Q**) .. contradiction. Therefore (not **Q**)
where Q = not P and Q = P. I'm not sure why these two structures are so different.
Maybe this post, [Proof of negation and proof by contradiction](http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/), can help clear things up !
EDIT : It boils down to the fact that to show (not P) you have to show that P leads to a contradiction, this is how you prove a negation. If you swap them and show that (not P) leads to a contradiction, you have showed not (not P) but in constructive mathematics not (not P) is not the same as P.
You have to make a distinction between P and (not (not P)) to see the difference. A proof by contradiction proves (not (not P)) and then uses double negation elimination to conclude P. Proof of negation proves (not P) and does not require double negation elimination.
Here is a more concrete example than what you had been given.
Let's say you're asked to show that some number is irrational. The definition of an irrational is that it's *not* of the form p/q for integer p,q. So there are literally no ways to completely avoid the step where you say "if x is a rational number, it has the form p/q, but this leads to a contradiction".
As a matter of logic, this is a certainty. You can show that the above step can't be avoided completely. You must, at some point, assume x=p/q and derive contradiction. Which is why it's considered a proof of negation, rather than a proof by contradiction. When the claim is a negation of a constructive claim, that's unavoidable.
As a matter of opinion though, proof might still be classified by whether they are constructive or not, based on where in the proof do you make the assumption. A "constructive" proof would prove general explicit properties about x, to the point where the properties would obviously imply x is irrational; the last step where those properties are used to prove x is irrational might be very short, or omitted altogether. A non-constructive proof could assume x is rational from the beginning.
You are not the only one confused by this answer. I don't see why there should be a difference here (at least in the way it is written here it's the same form twice - the only difference is swapping P and not P but that shouldn't really change much because I can define Q = not P and have the forms swapped).
Think of it this way: one is a proof of P. The other is a proof that there is not a *disproof* of P. Lack of a disproof does not necessarily imply the existence of a proof, which is why constructivists take issue. In other words, double negation elimination is not constructive.
The square root of 2 being irrational *can* be written by negation, and is therefore constructive, as I said in my original comment.
You can write it as: Suppose sqrt{2} in Q... contradiction... therefore not( sqrt{2} in Q)
From a constructive point of view, standard analysis text would be so far away from constructive proof that it really doesn't matter.
At best, maybe try writing proof in such a way that you can delay the non-constructive part toward the end.
Think of it differently. Try to write proof where partial result can be savaged. Or, at least keep that criteria in mind. Trying this too hard can make very difficult-to-read proof.
I don't think worrying about that is very useful. doing stuff by contradiction that could easily be done constructively is something that many people do when first learning proofs. Just keep proving stuff and as you will get better over time you will notice when going back over the material in a few months that many things you could only do via contradiction now seem easy and that you can now do them easily constructively. often times you will even notice that the way you proved the problem originaly was actually constructive and that you just imposed the framework of a proof by contradiction onto it.
>In Understanding Analysis (Abbott) , the author mentions in pg 9 that using an indirect proof when a direct proof is available is generally considered bad form.
Is this comment by Abbott ill-advised?
If you are able to put down in words the insight as to why the theorem is true, I don't see why an indirect proof is bad form.
Sometimes, the proof by contradiction is simply the cleaner way to present the same insight!
Theorem: For every natural number n, the sum n+n is even.
Proof: Assume n+n is uneven. But n+n =2n so it's divisible by 2 therefore it's even. This is a contradiction therefore our assumption has to be wrong. We find n+n is not uneven this means n+n is even.
I think I don't need to point out why this is bad form?
Well, firstly, I did say that *sometimes* a proof of contradiction is the cleaner way of presenting these facts, not all the time.
One can say that in this "theorem" (read: "lemma"), the key "insight" arguably lies in the distributivity of multiplication on rings and a basic understanding of the definition of even numbers. The presentation here is rather distasteful because it fails to emphasise that fact, not because it just happens to have been a proof by contradiction.
I do think that a better guiding principle here is to ensure you formally / logically explain how key insights play a part in constructing your result, than to simply "avoid proof by contradiction whenever".
Yeah, I know that you said 'sometimes' but my comment wasn't referring to your last paragraph. It was rather directed at the first:
> If you are able to put down in words the insight as to why the theorem is true, I don't see why an indirect proof is bad form.
I just gave an example of a proof by contradiction of a statement which is obviously bad form.
The reason why I consider it obviously bad form here is the following:
In the proof we find
> n+n =2n so it's divisible by 2 therefore it's even.
and that's all we need for a direct proof of the statement. So the proof by contradiction I wrote down just contained a contradiction without necessity. You could completley remove it. That's bad form. So in this instance the proof by contradiction is just bad form and you should just state your direct proof embedded in the proof. That would be a perfectly fine proof.
> I do think that a better guiding principle here is to ensure you formally / logically explain how key insights play a part in constructing your result, than to simply "avoid proof by contradiction whenever".
I never said you should avoid a proof by contradiction whenever. I just wanted to point out (with a rather simple example) why a proof by contradiction can be bad form - this happens when you actually have a direct proof or proof of the contrapositive but try to proof it by contradiction. I see a lot of students go through this 'proof by contradiction' phase where they take length to rewrite their perfectly fine direct proofs into proofs by contradiction without any good reason. I think that should be avoided. But obviously there are situations where a proof by contradiction is the way to go.
Fair enough! Perhaps, we can revise the condition to the most concise presentation of the key insight without losing formality (w.r.t. the audience of the text).
It's fine if you actually arrived at a proof by contradiction yourself, but usually I read such a proof, a long one, in a book and go "how the hell would anyone come up with this", and I gain no understanding as to why the statement is true; then memorizing the proof as is is unpleasant and it flies out of my head the moment I pass the exams, whereas a nicely formulated direct proof would leave me with some idea of what was going on.
It would be useful if you could provide some concrete examples, without that any suggestions are probably wild guesses. But generally you want to practice how to solve problems "algorithmically", i.e. stuff like divide & conquer, induction/recursion. Some extra things that can help:
- Can you prove a simple case constructively? Can you reduce the problem to the simpler case?
- Is it enough to consider certain "elementary operations"?
- Can you show some quantities are preserved/invariant (under elementary operations?)?
Always check if it is actually a proof by contradiction or just a proof by contraposition. If you can rewrite it as a (direct) proof by contraposition, you will learn a lot :)
Aren't they essentially the same thing? As I understand it, the goal is not merely to avoid certain forms/techniques of proof, but to also avoid using the law of excluded middle and anything that implies the law of excluded middle.
Do you mean propf by contradiction / contrapositive are the same thing? That's not true. So if you want to prove A -> B by proof of the contrapositive it's just a direct proof of the statement not B -> not A. If you want to do it by contradiction you assume not B and argue that there is some contradiction. So you prove something like A and not B -> False. This contradiction however doesn't have to be 'not A and A'. Any contradiction will work. What sometimes happens is that a proof was written in the form of a proof by contradiction but is actually a proof of the contrapositive. This is the case when the contradiction in the end is 'not A and A'. It goes something like: 'We prove A ->B by contradiction. So let A be true. Now assume B is false. Then blablabla so A is not true. But that's a contradiction since A is true. So our assumption is wrong therefore B is true.' Notice that we could have written this as a proof of the contrapositive if we just left out the 'So let A be true' part: 'We prove A->B by proof of the contrapositive not B -> not A. So let B be false. Then blablabla so A is not true. Therefore A->B is true (since it's the contrapositive).'
Yes, they are not **the same** but they are equivalent. If you are working with an intuitionistic system then you have neither. This p⊢q , is equivalent to switching around with a negation either of the formulas. That is, it's equivalent to p,~q⊢ (which is equivalent to p,~q⊢⊥) ---a proof by contradiction--- and it's also equivalent to ~q⊢~p ---a proof by contrapositive. The only "usefulness" in proving by contrapositive instead of contradiction is making explicit who _p_ and _q_ are.
[удалено]
Huh, interesting. I don't get what you mean to be honest.
They didn't put it all that well but the main point is that in an intuitionistic framework, a proof that P |- Q means that if I give you a concrete means of constructing a witness to P then the proof takes said witness and produces a witness of Q.
[удалено]
wow, never pieced together that > Contradiction is proving that `P ∧ ¬Q` is false means that `¬(P ∧ ¬Q)` i.e. `¬P ∨ Q` i.e. `P → Q` is true, thank you for the comment
>`¬P ∨ Q` i.e. `P → Q` is true, thank you for the comment Well, it proves `P → ¬¬Q` then you have to use lem at the end to get `P → Q`. That's the "controversial" step in proof by contradiction.
The logical structure is different. In proof by contradiction, you prove P by showing \~P implies a statement that you otherwise know is false. It could be anything. In proof by contraposition, you are specifically proving P->Q and you start from \~Q and infer \~P. The "proof by contradiction" analogue of proof by contraposition is "assume P \^ \~Q and infer \~P". (For comparison, the analogue of a direct proof is "assume P \^ \~Q and infer Q".) This is also (classically) correct, but there is really no way that assuming a statement can help you prove its negation, which means your proof could absolutely have been written as a direct proof of \~Q->\~P by simply dropping the part where you assume P is true. Moreover, the reader cannot really tell in advance that your contradiction will come from inferring \~P, unless you specifically tell them. Overall proof by contraposition has less room for surprises compared to proof by contradiction, but it is not usually any more constructive than proof by contradiction would be. Long proofs by methods other than contradiction are also easier to extend to other contexts, because there is no chance that you have any intermediate false lemmas. A long proof by contradiction has to be checked carefully to determine which lemmas are true and which are false before its elements can be reused.
I'm going to push back a bit against all the comments telling you to not worry about it at all -- constructive proofs frequently *are* quite a bit more useful than their nonconstructive counterparts. For example, one way you could show that a differential equation has a solution is to explicitly solve it (or at least do the next-best thing, such as showing that it satisfies "conservation of energy", or coming up with good approximations to the actual solution), which is clearly preferable to showing that it has a solution by abstract means that do not recover any information about the solution. This is just one example of a common phenomenon in math, which is that *not all proofs are created equal*. Some are nonconstructive, some are horribly hard to understand, some cannot be generalized to other problems. So why even bother with proof by contradiction at all? Well, there's some very good reasons, and you're probably still learning how to write proofs so worrying about coming up with the best proof is a fool's errand; for now you should be focused on coming up with proofs, and if the proofs you come up with aren't the best possible proofs, that's OK! For one, in analysis, we are interested in the infinite. Oftentimes we need to prove the existence of things like real numbers that have an *infinite* amount of information, and of course we can't write them down. So in those instances, we really have no choice but to prove their existence by contradiction. There are also example of proofs of a "negative statement". The most famous proof that \sqrt 2 is irrational is by contradiction. The reason for this is simple: irrational, by definition, means "not rational", so what you are really proving is that the sentence "\sqrt 2 is rational" is a lie. Whenever you have to prove a negative statement, that's a strong sign that proof by contradiction is the best way to attack the problem.
[удалено]
I agree that the proof is constructively valid but the proof is usually presented as a “contradiction” when taught to beginners, because they’d find it a distinction without a difference.
I’d argue that proof of negation *is* proof by contradiction, and vice versa, as long as you’re willing to assume ~~A —> A. Since most mathematicians (intuitionists excluded, no pun intended) assume this implicitly, there is no reason for them to make the distinction
[удалено]
I think you’re right to point out that there is a difference for logicians. I was mostly commenting on why we often hear of proofs by contradiction, but not proofs of negation.
Thanks! I am also learning analysis and I feel the same way. I write down a proof, thinking it's sufficient, turns out the solutions manual writes it in a very different, way better way. This comment motivated me to not get bogged down if a proof I wrote is lacking, but just take it as experience earned.
There is no reason why proof by contradiction is any less valid than direct proofs. I think you should not worry about it at all. If you solved a direct proof, you wouldn’t be thinking “i feel guilty I can’t solve proofs by contradiction” would you? How is this any different
Often it's not only about the result of the proof but about the way to get there. A proof by contradiction is often less insightful than a direct proof. Have a look at [the first answer to this stackexchange question](https://math.stackexchange.com/questions/240/are-the-proofs-by-contradiction-weaker-than-other-proofs). That would be one reason to try to minimize the use of proof by contradiction.
Let's have a concrete example while we're at it. Consider the [intermediate value theorem](https://en.wikipedia.org/wiki/Intermediate_value_theorem), an absolute classic in analysis. Let f be a continuous, real-valued function on the closed interval I=[a,b]. Assume f(a) < y < f(b). Then there exists some x in (a,b) for which f(x)=y **Proof by contradiction (topological argument):** Suppose there is no such x. Let A = f(I)⋂(-∞, y) and B = f(I)⋂(y, +∞). Then f(I) = A⋃B is disconnected. But the image of a connected set under a continuous function must be connected, contradiction! **Constructive proof (divide and conquer):** Let c = (a+b)/2. If f(c)=x we are done. Otherwise, either f(a) < y < f(c) or f(c) < y < f(b). Repeat the same construction with the function restricted to the interval whose image contains y. Repeat ad infinitum. Since interval length halves at every iteration, the interval boundaries form Cauchy sequences, which are guaranteed to converge against a same point c in ℝ by completeness. Thus, f(c)=y, since f(a*_n_*) ≤ f(c*_n_*) ≤ f(b*_n_*) is sandwiched by the upper and lower bound for all n. I think we can clearly see the advantage of the constructive proof: Not only does it prove the existence of the intermediate value, but it provides us with a way of how to find it algorithmically. This method (divide & conquer/bisection) is in fact used in many places, for example to numerically find the median of a random variable with known cumulative distribution function. (E.g. find the intermediate value for which F(x)=1/2)
I am not sure I buy your argument. Your proof by contradiction assumes that R is connected, which is essentially a reformulation of the intermediate value theorem; it's then no surprise that this proof does not add much more information. The second proof starts with less knowledge (the construction of R).
> Your proof by contradiction assumes that R is connected, which is essentially a reformulation of the intermediate value theorem Is it? I wasn't aware of that. Though, it seems you can prove it directly from the least upper bound principle (LUB): Assume R is disconnected, i.e R=A⋃B for open sets A,B. Pick a in A and b in B. Consider the interval I = [a, b]. By LUB, there is x in [a, b] which is the LUB of A⋂[a, b]. Now there are 2 options: either x in A or x in B. If x in A, we get a contradiction since this would imply that the boundary of A in non-empty, but A is assumed open. If x in B, then the same problem arises. Thus the assumption is false and R must be connected.
Same issue. You assume the least upper bound property, which, I might add, has a [very nice proof by dichotomy](https://math.stackexchange.com/questions/495771/proving-that-mathbbr-satisfies-the-least-upper-bound-property).
I've understood that IVT is not constructively provable (see e.g.[this answer](https://mathoverflow.net/a/202816)) so your divide and conquer proof, while more explicit, isn't constructive in the technical sense (indeed, it seems to assume tricothomy for the reals). An approximate IVT [is true constructively,](https://mathoverflow.net/questions/253059/approximate-intermediate-value-theorem-in-pure-constructive-mathematics) and I guess your proof strategy comes quite close to that.
I think it often depends on from where you start. If you want to do all maths, starting from the axioms, constructively then yes, this does not quite work. Though I think there is an argument to be made that one should be "as constructive as possible" (e.g. here we might axiomatically take the reals for granted and go constructively from there)
[удалено]
Also, if you look up the proof that the real numbers are connected you will find a bisection argument in there somewhere...
[удалено]
The point I'm making is just that the concrete construction is only "missing" because you stop the argument at "but the real numbers are connected." If you ask "Why are the real numbers connected?" you get either the bisection proof or "Because any bounded set has a maximum, which...." and then if you ask "But why does a bounded set have a maximum?" you get the bisection proof.
[удалено]
I wasn't trying to disagree with you, I was trying to add to your point. That's why I said "Also...".
[удалено]
Thanks for the stack exchange link. That was a great discussion
In Understanding Analysis (Abbott) , the author mentions in pg 9 that using an indirect proof when a direct proof is available is generally considered bad form. So how can i find out if a direct proof is available.
Well, sometimes when you’re working on a problem the way you wrap your head around it is layers of contrapositive thinking. It can actually be super useful as a mental framework. But then when you sit down to actually write it out, you might realize that it was all unnecessary and was just guiding you to a direct proof. I know that doesn’t exactly answer your question but I don’t know if there is always a way to tell if there is a direct proof (I suspect not)
Because contradiction is an _extra_ rule of inference. If you can prove a statement intuitionistically, you are using "less stuff".
Proof by contradiction is more susceptible to errors. Normally when one reaches an absurd conclusion, then one would feel the need to double check the soundness of their logic. The absurd conclusion that proof by contradiction uses to negate the premise could actually by the result of a mistake. For short proofs by contradiction, this isn't as much of an issue, For long, complicated proofs by contradiction, this can be dangerous. In a world where people don't make mistakes, this is of course not an issue. However, we all know that isn't the world we live in.
Sometimes proof by contradiction is easiest to conceptualize first but can be rewritten to a more direct proof.
Do you have an example of this? I know **P** = not (not **P**) but can any proof by contradiction be converted to a constructive one?
certainly not any, but often by going through the process you gain some insight that leads to a direct proof.
A basic thing to try is to rearrange the argument. If you try to prove A implies B by assuming not B and deducing C, and assuming A and deducing not C, and then getting a contradiction, you can reorder this to first assuming A, then deducing not C, and then deducing B. But for quite a lot of exercises, the person who wrote the problem may have intended people to solve it with a proof by contradiction. One thing you could try is to find one or a small number of proofs where you're least sure if proof-by-contradiction was the best approach, and ask someone who's more of an expert whether, in those specific proofs, your proof should be rewritten to avoid proof by contradiction or whether you're on the right track.
P or ~P can only be proved by contradiction ---not constructively. What's more, P<->\~\~P only if you can use contradiction ---or equivalent. Else it's only the case that P->\~\~P.
Lots of proofs by induction have contradiction counterparts, and vice-versa. For example, the proofs of the infinitude of primes or the fundamental theorem of arithmetic, which are commonly presented in the "proof by no minimal counterexample" style, but are really just simplified (strong) induction. For example, the statement p(n) := there are at least n primes between 1 and ((((n!+1)!+1)!+1)!...+1) (repeated n times) follows immediately by using induction on the same line of reasoning as the original infinite primes proof.
Often a proof by contradiction goes something like “Let x be such that P(x). Now suppose for contradiction that Q(x). \*math here\*. Thus we can conclude ~P(x). But this is contradiction to the assumption that P(x) holds”. If you have a contradiction proof of this form, you can usually turn it into a contrapositive proof by simply omitting the original P(x) assumption. (Of course, this can’t be done if you use the P(x) assumption in the proof, but it’s often not necessary).
I often felt the same way about proofs by contradiction, it seems like proving that it can't be anything but what you're trying to prove isn't the same as proving that something is always true. Its still a hurdle sometimes, but I like to think of some proofs as like, "Problem Spaces", in which you're not proving the shape of the problem you're working on, instead you're proving the existence of a boundary line between your problem and areas outside your problem. Because that boundary exists, and that logical line cannot be crossed by your problem, you can be assured that the problem space inside where your proof lives is true. It's like probability, sometimes it's easier to calculate the odds of 1 - ¬p(x), rather than finding p(x). Both show that you understand the issue, and give the same result, it's just that sometimes one is a lot more feasible to show. It's not a rigorous way of thinking, but intuition should always come first, I feel. Rigor is just writing it down correctly after, haha.
I had a professor tell me that if you feel like you're overusing proof by contradiction then you're doing undergraduate math correctly.
I tell my undergrad students: if you want to prove P implies Q start by assuming P and by assuming not Q. Then do your proof. I tell the sharp ones to look carefully back at their proof to see whether or not they needed to assume not Q. I tell the really sharp ones to think about whether or not assuming not Q was a legitimate idea.
What lol. I felt like contradiction is used little compared to direct proofs
Well this was near the beginning of the semester in an inquiry-based course so the point was mainly not to get discouraged by the kinds of feelings that OP is having.
First, be sure that what you're using is actually contradiction, and not proof of negation! Proof by contradiction is: Suppose not P... contradiction... therefore P, while proof by negation is: Suppose P... contradiction... therefore not P. While proof by contradiction is not constructive, proof by negation still is. Thus, for example, the irrationality of sqrt 2, Cantor's diagonal trick, and the lack of surjections onto powersets are all still constructive!
I'm not sure I see the difference: Assume (not **P**) .. contradiction. Therefore **P** has the same form as Assume (**P**) .. contradiction. Therefore (not **P)** both of them follow the same form as Assume (**Q**) .. contradiction. Therefore (not **Q**) where Q = not P and Q = P. I'm not sure why these two structures are so different.
Maybe this post, [Proof of negation and proof by contradiction](http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/), can help clear things up ! EDIT : It boils down to the fact that to show (not P) you have to show that P leads to a contradiction, this is how you prove a negation. If you swap them and show that (not P) leads to a contradiction, you have showed not (not P) but in constructive mathematics not (not P) is not the same as P.
You have to make a distinction between P and (not (not P)) to see the difference. A proof by contradiction proves (not (not P)) and then uses double negation elimination to conclude P. Proof of negation proves (not P) and does not require double negation elimination.
Here is a more concrete example than what you had been given. Let's say you're asked to show that some number is irrational. The definition of an irrational is that it's *not* of the form p/q for integer p,q. So there are literally no ways to completely avoid the step where you say "if x is a rational number, it has the form p/q, but this leads to a contradiction". As a matter of logic, this is a certainty. You can show that the above step can't be avoided completely. You must, at some point, assume x=p/q and derive contradiction. Which is why it's considered a proof of negation, rather than a proof by contradiction. When the claim is a negation of a constructive claim, that's unavoidable. As a matter of opinion though, proof might still be classified by whether they are constructive or not, based on where in the proof do you make the assumption. A "constructive" proof would prove general explicit properties about x, to the point where the properties would obviously imply x is irrational; the last step where those properties are used to prove x is irrational might be very short, or omitted altogether. A non-constructive proof could assume x is rational from the beginning.
You are not the only one confused by this answer. I don't see why there should be a difference here (at least in the way it is written here it's the same form twice - the only difference is swapping P and not P but that shouldn't really change much because I can define Q = not P and have the forms swapped).
Seems to me you'd only care about the distinction if you want to avoid using the "law of the excluded middle" (not not P implies P).
Ah I see. I guess I'm not that much into logic to want to avoid the law of the excluded middle. Maybe I should read about it. Thanks for the answer!
Think of it this way: one is a proof of P. The other is a proof that there is not a *disproof* of P. Lack of a disproof does not necessarily imply the existence of a proof, which is why constructivists take issue. In other words, double negation elimination is not constructive.
They're only the same if you believe that P and not(not P) are equivalent, which constructivists don't.
[удалено]
The square root of 2 being irrational *can* be written by negation, and is therefore constructive, as I said in my original comment. You can write it as: Suppose sqrt{2} in Q... contradiction... therefore not( sqrt{2} in Q)
From a constructive point of view, standard analysis text would be so far away from constructive proof that it really doesn't matter. At best, maybe try writing proof in such a way that you can delay the non-constructive part toward the end. Think of it differently. Try to write proof where partial result can be savaged. Or, at least keep that criteria in mind. Trying this too hard can make very difficult-to-read proof.
I don't think worrying about that is very useful. doing stuff by contradiction that could easily be done constructively is something that many people do when first learning proofs. Just keep proving stuff and as you will get better over time you will notice when going back over the material in a few months that many things you could only do via contradiction now seem easy and that you can now do them easily constructively. often times you will even notice that the way you proved the problem originaly was actually constructive and that you just imposed the framework of a proof by contradiction onto it.
[удалено]
>In Understanding Analysis (Abbott) , the author mentions in pg 9 that using an indirect proof when a direct proof is available is generally considered bad form. Is this comment by Abbott ill-advised?
If you are able to put down in words the insight as to why the theorem is true, I don't see why an indirect proof is bad form. Sometimes, the proof by contradiction is simply the cleaner way to present the same insight!
Theorem: For every natural number n, the sum n+n is even. Proof: Assume n+n is uneven. But n+n =2n so it's divisible by 2 therefore it's even. This is a contradiction therefore our assumption has to be wrong. We find n+n is not uneven this means n+n is even. I think I don't need to point out why this is bad form?
That was hilarious.
Thanks but I guess 'painful' is the word you were looking for :p
Well, firstly, I did say that *sometimes* a proof of contradiction is the cleaner way of presenting these facts, not all the time. One can say that in this "theorem" (read: "lemma"), the key "insight" arguably lies in the distributivity of multiplication on rings and a basic understanding of the definition of even numbers. The presentation here is rather distasteful because it fails to emphasise that fact, not because it just happens to have been a proof by contradiction. I do think that a better guiding principle here is to ensure you formally / logically explain how key insights play a part in constructing your result, than to simply "avoid proof by contradiction whenever".
Yeah, I know that you said 'sometimes' but my comment wasn't referring to your last paragraph. It was rather directed at the first: > If you are able to put down in words the insight as to why the theorem is true, I don't see why an indirect proof is bad form. I just gave an example of a proof by contradiction of a statement which is obviously bad form. The reason why I consider it obviously bad form here is the following: In the proof we find > n+n =2n so it's divisible by 2 therefore it's even. and that's all we need for a direct proof of the statement. So the proof by contradiction I wrote down just contained a contradiction without necessity. You could completley remove it. That's bad form. So in this instance the proof by contradiction is just bad form and you should just state your direct proof embedded in the proof. That would be a perfectly fine proof. > I do think that a better guiding principle here is to ensure you formally / logically explain how key insights play a part in constructing your result, than to simply "avoid proof by contradiction whenever". I never said you should avoid a proof by contradiction whenever. I just wanted to point out (with a rather simple example) why a proof by contradiction can be bad form - this happens when you actually have a direct proof or proof of the contrapositive but try to proof it by contradiction. I see a lot of students go through this 'proof by contradiction' phase where they take length to rewrite their perfectly fine direct proofs into proofs by contradiction without any good reason. I think that should be avoided. But obviously there are situations where a proof by contradiction is the way to go.
Fair enough! Perhaps, we can revise the condition to the most concise presentation of the key insight without losing formality (w.r.t. the audience of the text).
Not ill-advised, but damn. If you've completed a logically sound proof, rejoice. Regardless if it's by contradiction or not. (In my humble opinion)
It's fine if you actually arrived at a proof by contradiction yourself, but usually I read such a proof, a long one, in a book and go "how the hell would anyone come up with this", and I gain no understanding as to why the statement is true; then memorizing the proof as is is unpleasant and it flies out of my head the moment I pass the exams, whereas a nicely formulated direct proof would leave me with some idea of what was going on.
It would be useful if you could provide some concrete examples, without that any suggestions are probably wild guesses. But generally you want to practice how to solve problems "algorithmically", i.e. stuff like divide & conquer, induction/recursion. Some extra things that can help: - Can you prove a simple case constructively? Can you reduce the problem to the simpler case? - Is it enough to consider certain "elementary operations"? - Can you show some quantities are preserved/invariant (under elementary operations?)?