Tag Info

Hot answers tagged

80

One general reason to avoid proof by contradiction is the following. When you prove something by contradiction, all you learn is that the statement you wanted to prove is true. When you prove something directly, you learn every intermediate implication you had to prove along the way. More explicitly, if you want to prove that $p \Rightarrow q$ by ...


35

Another example: Euler's sum of powers conjecture, a generalization of Fermat's Last Theorem. It states: If the equation $\sum_{i=1}^kx_i^n=z^n$ has a solution in positive integers, then n ≤ k (unless k=1). Fermat's Last Theorem is the k=2 case of this conjecture. A counterexample for n = 5 was found in 1966: it's $$ ...


31

The wikipedia article on the Collatz conjecture gives these three examples of conjectures that were disproved with large numbers: Polya conjecture. Mertens conjecture. Skewes number.


22

I heard this story from Professor Estie Arkin at Stony Brook (sorry, I don't know what conjecture she was talking about): For weeks we tried to prove the conjecture (without success) while we left a computer running looking for counter-examples. One morning we came in to find the computer screen flashing: "Counter-example found". We all thought for ...


22

In my opinion the proof by contradiction is a bad habit, when there is a direct proof. I always have the feeling that proofs by contradiction aren't so elegant, as it is necessary to read them several times, to see how someone got the idea that the contradiction will work. A good proof does not only prove something but gives a way. In a direct proof you ...


18

For an old example, Mersenne made the following conjecture in 1644: The Mersenne numbers, $M_n=2^n − 1$, are prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and no others. Euler observed that the Mersenne number at $M_{61}$ is prime, so refuting the conjecture. $M_{61}$ is quite large by the standards of the day: 2 305 843 009 213 693 951. ...


18

The first example which came to my mind is the Skewes' number, that is the smallest natural number n for which π(n) > li(n). Wikipedia states that now the limit is near e727.952, but the first estimation was much higher.


16

$x^2=2(2y+1)$, so $x$ has to be even. Then, let $x=2k$ where $k\in\mathbb Z$. So we have $$(2k)^2-4y=2\Rightarrow 2(k^2-y)=1.$$ The LHS is even, and the RHS is odd, which is a contradiction.


14

A famous example that is not quite as large as these others is the prime race. The conjecture states, roughly: Consider the first n primes, not counting 2 or 3. Divide them into two groups: A contains all of those primes congruent to 1 modulo 3 and B contains those primes congruent to 2 modulo 3. A will never contain more numbers than B. The smallest ...


14

Another class of examples arise from diophantine equations with huge minimal solutions. Thus the conjecture that such an equation is unsolvable in integers has only huge counterexamples. Well-known examples arise from Pell equations, e.g. the smallest solution to the classic Archimedes Cattle problem has 206545 decimal digits, namely 77602714 ... 55081800.


14

The discussion here has been quite interesting! I wrote about Leibniz's notation in my Bachelor's Thesis in 2010 reading through major parts of Bos's 1974 PhD on higher order differentials in the Leibnizian calculus. I believe Bos is wrong at one point. Assuming one variable in the by Bos so-called arithmetic progression is never necessary - only convenient! ...


13

In a proof with multiple assumptions you have to choose one of them to be "blamed" for the contradiction. Think to your example in terms of assumptions; you start with a couple of them (they can be two Lemmas already proved, or two hypotheses) : $P→Q$ and $R→¬Q$. Then we proceed "formally" as follows (I'll use the Natural Deduction proof system; for a ...


13

I think your method is sound: if we assume by contradiction that $r=\frac{a}{b}$ with $a,b$ integers we get that $$\frac{a}{b}-\frac{b}{a}=5$$ since neither $b$ nor $a$ is 0, we can multiply by $ab$ and get $$(a-b)(a+b)=5ab$$ now there are three cases to investigate, i'll just point them out so you can finish it off: If $a$ and $b$ are both odd- look at ...


12

To complete your solution, note that you can, without loss of generality, set $a$ and $b$ to be coprime. So you have $a^2=b^2+5ab=b(b+5a)$. Hence $a$ divides $b(b+5a)$. Euclid's lemma now tells you that $a$ divides $b+5a$ (because $a$ and $b$ are coprime). But then $a$ must divide $b$, which is contradiction with the fact that $a$ and $b$ are coprime. ...


11

Think of the negation as follows: Suppose $\lnot (x \rightarrow z)$ $$\lnot(x \rightarrow z) \equiv \lnot (\lnot x \lor z) \equiv x \land \lnot z$$ This implies both $\color{blue} x$ and $\lnot z$, by simplification (and-elimination). $\lnot z$ along with $y \rightarrow z$ gives you $\lnot y$ by modus tollens. And $\lnot y$ along with $x \rightarrow y$ ...


11

To answer It also could have been that our first assumption, namely, P, was false. Or both of them could be false: yes, it could, but if you assume P, then R must be false, what you write $P\rightarrow\neg R$. You could have concluded $R\rightarrow \neg P$, of course (and it's the contraposition), by assuming $R$ instead of $P$. Notice that both of these ...


11

Note that you don`t want to prove or contradict $P$ or $R$ themselves. What you want to prove is the implication $P\rightarrow\neg R$. So you pick the assumption of this implication, in this case $P$, and use it for further argumentation. Now you can start your argumentation with another assumption like $R$ or with anything else. Important difference: now ...


11

I don't think they are similar. "Undefined" is something that one predicates of expressions. It means they don't refer to any mathematical object. "Complex infinity", on the other hand, is itself a mathematical object. It's a point in the space $\mathbb C\cup\{\infty\}$, and there is such a thing as an open neighborhood of that point, as with any other ...


11

The polynomial is simple enough that it’s no problem simply to multiply it out: $$\begin{align*} (4k+3)^2-(4k+3)&=16k^2+24k+9-4k-3\\ &=16k^2+20k+6\\ &=4\left(4k^2+5k+1\right)+2\;, \end{align*}$$ which is clearly not a multiple of $4$. This is perhaps a little less elegant than njguliyev’s solution, but it works just fine.


10

$(4k + 3)^2 - (4k + 3) = (4k + 3)(4k + 3-1) = (4k + 3)(4k + 2)=2(4k + 3)(2k + 1)$.


10

My favorite example, which I'm surprised hasn't been posted yet, is the conjecture: $n^{17}+9 \text{ and } (n+1)^{17}+9 \text{ are relatively prime}$ The first counterexample is $n=8424432925592889329288197322308900672459420460792433$


10

Below are six methods - whose variety may prove somewhat instructive. $(0)\ $ By the Parity Root Test, $\rm\: x^2-5\:x-1\:$ has no rational roots since it has odd leading coefficient, odd constant term and odd coefficient sum. $(1)\ $ By the Rational Root Test, the only possible rational roots of $\rm\ x^2 -5\ x - 1\ $ are $\rm\ x = \pm 1\:.$ $(2)\ $ ...


9

Whenever something is provable at all, it is possible to disguise that proof as one by contradiction. But the result is not necessarily very enlightening. Suppose we have some kind of valid argument for the proposition $P$. We can then also prove $P$ by contradiction: $P$ is true. Namely, assume for a contradiction that $\neg P$. Then (insert the ...


9

Hint: This is a perfect example of why you can't always switch limits!


9

It's certainly good to know how to proceed with a proof by contradiction, and to have a firm grasp of its logic. You'll encounter them often. When students first grasp the logic of such a proof, and succeed in constructing those proofs, they often become enamored by them, especially given the satisfaction some get by "disproving" something. But it really is ...


8

Let me quickly summarize what you can find in some of the other answers, then I will throw my two cents on top of that: Proof is a proof, as long as it is sound. Maybe something cannot be proved by contradiction but otherwise it is just as good as direct proof. Somehow many feel that Reducio Ad Absurdum is less elegant, or less intuitive. Now my two ...


8

I don't know if I would consider this accessible or 'large', but the counterexample of Adyan to the famous General Burnside Problem in group theory requires an odd exponent greater than or equal to 665. The "shorter" counterexample (proof) due to Olshanskii requires an exponent greater than $10^{10}$. The reason for the large number in the latter proof is ...


8

I'm assuming you are more accustomed to seeing proof by contradiction used largely with statements that are implications or conditionals. And indeed, when writing a proof by contradiction to prove statements of the form $$P \implies Q,$$ we typically assume $(P\land \lnot Q)$. But in this particular case, we do not seem to have an implication to prove. ...


8

The gist of the OP's explanation of why the "cancellation" of $\partial f$'s should not be allowed (and does not work) is correct, but something more can be said. The partial derivative $\partial f/\partial x$ is the rate at which $f$ changes with respect to change in $x$, but while holding y constant. Similarly the definition of $\partial f/\partial y$ ...


8

Can you divide $(6n+2)$ by anything? What about $(6n+3)$?



Only top voted, non community-wiki answers of a minimum length are eligible