Could somebody please give me one scenario in which a proof by contradiction is the only proof possible or otherwise explain why it's good to learn proof by contradiction.
It's a very useful technique
Try to prove sqrt(2) is not rational without it
>>7921648
For all positive integers a,b we have:
[eqn] \left|\sqrt2 - \frac{a}{b} \right| = \frac{|2b^2-a^2|}{b^2 \left(\sqrt{2}+\frac{a}{b} \right) } \ge \frac{1}{b^2 \left( \sqrt2 + \frac{a}{b} \right) } \ge \frac{1}{3b^2} > 0 [/eqn]
>>7921658
How does that work?
>>Person who posted after >>7921727 ITT
Did you delete your own post?
If so why?
>>7921755
because the reason for discarding the theorem is not explicitly the refusal to apply the proof by contradiction, Even though, a few of the theorems on functions which try to find a particular value are by contradictions.
it depends how you phrase the OP.
>>7921755
>>7921765
here are other proofs where contradiction is used
https://en.wikipedia.org/wiki/Extreme_value_theorem
there are constructive versions of IVT
https://ncatlab.org/nlab/show/intermediate+value+theorem
same thing for the EVT
https://ncatlab.org/nlab/show/extreme+value+theorem
where it works in predicative constructive locale theory[=topology without points]
>>7921639
Euclid's proof that the list of prime numbers is infinite.
>>7921813
Euclid is often erroneously reported to have proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes.[3] Although the proof as a whole is not by contradiction (it does not assume that only finitely many primes exist), a proof by contradiction is within it, which is that none of the initially considered primes can divide the number q above.
>>7921818
>>7921813
>Filip Saidak gave the following proof which does not use reductio ad absurdum:.[6] It also does not use Euclid's Lemma that if a prime p divides ab then it must divide a or b.
For any n > 1, n and n+1 have no common factors, they are coprime.
Therefore N2=n(n+1) must have at least two different prime factors.
N2 and N2+1 are coprime and N2 has at least two prime factors
Therefore N3=N2(N2+1) has at least three prime factors.
By induction for any k, Nk=Nk-1(Nk-1+1) has at least k prime factors.
Therefore there is an infinity of primes.
As an aside, even in constructive mathematics, the proof by contradiction is valid as soon as we have decidable equality, which means it is valid up to Q.
by the way, there are logics which refute the principle of explosion. it means that you can have mathematics and logics where ''contradictions'' are permitted under conditions.
There is even a mathematical theory about the real line done in para-consistent logic.
>>7921658
Why is |2b^2 - a^2| >= 1?
once you found it, you can usually turn a proof by contradiction into a straightforward proof and vice versa
it is just simpler to find a proof by contradiction sometimes
btw id like to see a proof of pigeonhole principle without contradiction
>>7921648
Wikipedia says so. QED.
>>7921648
[eqn]
s_1 = 1
[/eqn]
[eqn]
s_{n+1} = \frac{s_n}{2} + \frac{1}{s_n}
[/eqn]
[math] \{s_n\} [/math] is Cauchy, but does not converge to a rational number
>>7921639
I couldn't imagine doing most uniqueness theorems without contradiction. Well, it'd be a waste of time to try anyway.
>>7921658
this is the same as proof by contradiction except you put it in a nice form where it's true if the value is zero and it's false if the value is greater than zero.
>>7922849
>Well, it'd be a waste of time to try anyway.
on the contrary, proof by contradictions are the waste of time since you learn very little by them
I've heard that all proofs by contradiction can be rewritten to not be proofs by contradiction. I know little about formal logic, but my guess is that it amounts to distributing some logical operations from the beginning of the proof over the rest of the proof.
>>7923341
I'm think switching between the two can be done by taking the contrapositive of all the implication statements of the proof. That is, taking the negation everywhere and reversing the order of statements.
In a proof by contradiction you demonstrate:
If the negation of the theorem then a known false statement.
Taking the contrapositives everywhere gets you:
If a true statement then the theorem.
