7 ms·
When is proof by contradiction necessary?
- ikeboy 12y agoWhy can't you prove irrationality as follows: All rational numbers have the property that their square is not 2. (Should be a simple proof by induction on the denominator.) The square root of two does not have that property, and is therefore not rational. Is the contradiction hiding in my implied definition, my implied induction proof, somewhere else?
- mjcohen 12y agoIf the proof is simple, give it.
- ikeboy 12y agoI've got something much simpler than what I was thinking not involving induction, so I'll give that instead. Assume n,m,x integer, and n^2/m^2=x. I claim x!=2. Proof: Write out both n and m's prime factorizations. Their squares' prime factorizations each contain an even number of all primes (zero is even). Therefore, for every prime, x's prime factorization contains an even number of it as well. Therefore x is not 2.
- gamegoblin 12y agoThat is a proof by contradiction that the square root of any prime is irrational.
- ikeboy 12y agoWhere is the contradiction? I don't see any false assumptions that then result in contradiction.
- gamegoblin 12y agohttps://proofwiki.org/wiki/Square_Root_of_Prime_is_Irrational https://proofwiki.org/wiki/Square_Root_of_Prime_is_Irrationa... Your proof hinges on the not-directly-stated words "so, if x were 2, we would reach an impossibility" where impossibility == contradiction.
- ikeboy 12y agoBut that's not the proof I used. My proof was positive. They may be equivalent, but not if we count proof by contradiction as special. In response to edit: No, it doesn't. Having proven that x contains an even number of 2s as factors, it follows that x is not two. 2 does not have an even number of 2s as factors, x does, therefore they are different. No contradiction required.
- Retra 12y agoI can't see the difference between your proof and the given one, except that you didn't write yours out with the same degree of formality. If you wrote your proof using only applied axioms and theorems, it would be essentially identical. The key point here is that you are partitioning the possibilities in a binary fashion: either x has even number of prime factors or it does not. You've shown that it must not have an even number of prime factors. You haven't shown that it isn't 2. You implied that if it were true, that would contradict what you have shown. How you go from "X has an even number of prime factors" to "X can't be 2" is important.
- ikeboy 12y agoTake two cases. One where x has no factors of two, and one here it has at least 2. In the first case, x is not divisible by 2, while 2 is divisible by 2, therefore x is not 2. In the second case, x is divisible by 4, while 2 is not, therefore x is not 2. You're right that they are "essentially" the same proof, but excluding contradictions is weird, a bit like excluding the letter e. Rephrasing a proof to not use it may be possible in some cases.
- masterjack 12y agoHow does your induction step begin if not "assume m/n squared to 2"
- gamegoblin 12y agoAll rational numbers have the property that their square is not 2 == 2 not in {r^2 for r in rationals} == sqrt(2) not in {r for r in rationals} == sqrt(2) not in rationals It seems to me that you handwaved away the entire proof in your first sentence, without really proving anything.
- ikeboy 12y agoI did, although the statement I gave can be proven without contradiction. I gave a proof in a different reply.
- deckar01 12y agoI'm not sure "try not to use [proof by contradiction] unless you really need it" is the optimal conclusion. In "Meta Math"[1], Gregory Chaitin explores the question: "What makes a mathematical concept desirable?" Simplicity was the solution. The best theorems seem obvious in retrospect, because they are reduced into relationships between existing concepts. I would recommend trying all angles of attack when searching for a proof. If it starts to take too long or you hit a dead end, try a different angle. Even if you discover a proof, try your other opening moves, look for a more elegant solution. I believe Wolfram Alpha converges on this solution by performing some sort of weighted, breadth-first search on the permutations of an equation. I highly recommend "Meta Math"[1] if you are interested in theories about entropy and algorithms that generate proofs. [1] ("Meta Math", Gregory Chaitin, http://arxiv.org/pdf/math/0404335.pdf http://arxiv.org/pdf/math/0404335.pdf)
- eru 12y ago> I'm not sure "try not to use [proof by contradiction] unless you really need it" is the optimal conclusion. Oh, that's only a guideline for presenting your proves. Not for coming up with them in the first place. Mathematicians do exactly what you are suggesting already. The first prove one finds is usually quite ugly, and then comes the simplification. Writers call it editing, programmers refactoring.
- EGreg 12y agoMany proofs by contradiction are simply results of wrapping a constructive proof: Suppose premises/axioms (B, C, ...) which don't depend on the value of A. Then, B=true AND C=true ... implies A=true by some logical argument, such as A Or Not (B And C And ...) = True In this case, the proof by contradiction is Assume A=False But B=True, C=True, ... (Since they dont depend on A) Apply above constructive argument So A is true, A CONTRADICTION Proofs by contradiction can often be of this type so the first and last lines can be removed. The question is, what other types can there be?
- vilhelm_s 12y agoSee also Andrej Bauer's "reply article", Proof of Negation and Proof by Contradiction: http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ http://math.andrej.com/2010/03/29/proof-of-negation-and-proo... In short, there are two different logical principles, and ordinary mathematicians call both of them proof by contradiction. However, constructivist (aka intuitionist) mathematicians make a distinction between them: they "believe in" proof of negation, but not in proof by contradiction. A lot of work has been done about formalizing mathematics in constructive logic. One big component of this is figuring out which uses of proof by contradiction are avoidable, and which one are essential (in the latter case the theorem statement has to be weakened for the constructive version). But this is all about proof by contradiction in the narrow sense. The usual proof about the irrationality of √2 is valid constructively.
- monochromatic 12y agoThe "problem" is basically that constructivists don't believe that this is a valid inference: ¬¬ϕ ⇒ ϕ
- iamcurious 12y agoAnd even that is less of a problem if you take into account that they still accept: ¬¬¬¬ϕ ⇒ ¬¬ϕ
- monochromatic 12y agoDo they really? Why?
- tel 12y agoproof : ¬¬¬¬ϕ ⇒ ¬¬ϕ proof (f : ((((a -> False) -> False) -> False) -> False)) = \ (z : a -> False) -> f (\afff -> afff (\aff -> aff z)))
- iamcurious 12y agoIt just follows from the axioms. They accept that a proof of ¬ p can be a proof that takes p and arrives to a contradiction. And that a contradiction is a formula and its negation. From that we can prove ¬¬¬¬p => ¬¬p. We can assume ¬p and we have to prove a contradiction. So we have to prove: ¬¬¬¬p, ¬p => _|_ Now, we know* that alpha => ¬¬alpha. So from ¬p, we can get ¬¬¬p. And from ¬(¬¬¬p) and (¬¬¬p) we arrive to _|_. *To prove alpha => ¬¬alpha, we can assume ¬alpha and arrive at a contradiction, so we would have to rpove alpha, ¬alpha => _|_ and we are done. In Natural Deduction: [¬p]1 [¬¬p]2 --------------- _|_ ----------2 ¬¬¬p ¬¬¬¬p ----------------------- _|_ -----------------------1 ¬¬p This has been generalized to translate classical theorems into constructive theorems.[1] Just like this case, though, the resulting theorems are full of double negations. [1] http://en.wikipedia.org/wiki/Double-negation_translation http://en.wikipedia.org/wiki/Double-negation_translation
- crimsonalucard 12y agoOutside of math and logic, in the world of science, not only is proof by contradiction necessary, it is the ONLY way of proving anything.
- eru 12y agoI have a strong suspicion you are mixing up different categories.
- crimsonalucard 12y agoWhat categories? I'm differentiating between math/logic and science.
- eru 12y agoJust to clarify: I assume your original comment was an allusion to Popper's falsification?
- crimsonalucard 12y agoyes.
- pg_is_a_butt 12y agonever... because it should always be tested first as it's usually a quick proof.
- evitisopartnoc 12y agoI don't like the conclusion that students should avoid proving by contradiction unless they really need it. I almost always start with contradiction as my initial method of choice when taking exams because you don't always have time to completely rewrite your proofs. Contradiction helps with this since it naturally encompasses proving by contrapositive also. Because if you're trying to prove that p->q, you can assume p and ~q and getting to ~p is a contradiction since p^~p (and this is the same structure as a proof by contrapositive if you got to this line without assuming p). And of course if you find any other absurdities along the way sooner, you're done quicker. This is nice because a proof by contrapositive is more or less equivalent to a direct proof. So simply by always starting with proof by contradiction, you cover the cases where the theorem: - is simple enough for you to find out exactly why it's true (direct proof hidden in the contrapositive). - is complex and wide reaching enough for you to hit an absurdity quickly
- eru 12y ago> I don't like the conclusion that students should avoid proving by contradiction unless they really need it. Where is that conclusion drawn? This is an blog post for research (and armchair) mathematicians, not students trying to sit an exam.
- evitisopartnoc 12y agoLast paragraph: >In which case, perhaps the advice that I give to students — proof by contradiction is a very useful tool, but try not to use it unless you really need it — is, though not completely precise, about the best one can do.
- eru 12y agoOh, ok. I interpreted that as advice to students writing up their proves, not trying to find them.
- raymondh 12y agoFirst, let's assume that proof by contraction isn't necessary, ... :-)
- EGreg 12y agoWhen both X and Not X lead to contradictions, we have a paradox. But what if Not X leads to a contradiction and we can't seem to find a contradiction when we assume X, but we aren't sure there isn't one? Have we proven X by contradiction, or is it really a paradox and there is some nonsensical operation somewhere? I remember wondering something likethat before.
- ebola1717 12y agoIn that case, you have proven X by contradiction. If you're rigorous enough, you can rule out the 3rd option. As wondering if you're in a situation where your axioms are inconsistent, well that's actually the world mathematics lives in. Godel's Incompleteness Theorems show that, besides some weak axiom systems, the only systems of axioms that can prove they are consistent are the ones that are inconsistent. So we can only tell when systems are inconsistent, never when they are consistent. You just kinda hope it's not all inconsistent.
- madamepsychosis 12y agoMy intuition – proof by contradiction means we have to use one step that inverts the set of values for which the statement is true – so whether we need a contradiction step depends on the cardinality of this truth set. Perhaps it depends on the relationship between the ‘truth set’ of our premises and our conclusions (e.g. the square root of 2 is one number, but all of the rationals is infinite) Supporting this intuition, getting rid of proof by contradiction leaves us unable to construct uncountable sets. Maybe some proofs need several contradiction steps (i.e., when their truth set cardinality is aleph-2,3, etc.)
- mattxxx 12y agoYea, but, I mean, the isn't the diagonal argument just an extension of proof-by-contradiction into countable sets? The same way that induction is the extension of syllogism into countable sets?
- mattxxx 12y agoPretty unrelated, but proof by contradiction has been really useful for me in real life. It gives you a way to look at logical facts, and remove many axioms, because it relies on empirical evidence and a set of assumptions that you are trying to invalidate. In that way, it avoids issues with deducing things from a set of pre-prescribed beliefs. In fact, it fights against them.
- leephillips 12y agoAll difficult conjectures should be proved by reductio ad absurdum arguments. For if the proof is long and complicated enough you are bound to make a mistake somewhere and hence a contradiction will inevitably appear, and so the truth of the original conjecture is established QED. -- John Barrow
- brownbat 12y agoI especially liked the discussion under Example 1 about reformulating "negative" sentences into "positive" sentences. The briefest amount of work in mathematical deduction or symbolic logic will cause you to raise an eyebrow whenever anyone insists "you can't prove a negative." Every negative statement has a positive formulation buried within it. Or, no negative statement exists that lacks a positive formulation, and vice versa.
- lerpa 12y agoEmpirical sciences are based upon this, you can only prove theories to be false and you do that by demonstrating a contradiction regarding its predictions and the observations.
- eterm 12y agoMinor mistake in stating the theorem about p^2 = 2 q^2. As stated, p = q = 0 is a valid solution.
- nova 12y agoAnd then you have linear logic (which is to constructive logic what constructive logic is to classical logic), with its two kinds of conjunctions and two kinds of disjunctions, one of which is difficult to understand but does have excluded middle again.
- amelius 12y agoPersonally, I'd rather like to see a formal proof than a proof that is "optimal" according to some vague metric.