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


30

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


28

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

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


20

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


17

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


17

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.


13

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


13

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.


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


12

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


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

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)\ $ ...


10

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


9

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


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


9

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


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

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


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

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

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$


7

I was so pissed after testing one of my own conjectures that I remembered this question and wanted to post it here. I conjectured after numerical observations that for every prime p, and integers $k \ge 1, n \ge 1$, that $$ p^k \, || 2^n-1 \quad \Longleftrightarrow \quad p^{k-1} \, || \, n \quad and \quad O(2,p) \, |\, n, $$ where $O(2,p)$ is the least ...


7

Hint: suppose not. You know what $f(2^k)$ must be. You'll show that $f(3)$ can't be any natural number. You have bounds since $f(2) < f(3) < f(4)$. Start considering $f(3^j) = f(3)^j$ for some small values of $j$ and compare to $f(2^k)$ for some small values of $k$ to eliminate all possibilities for $f(3)$.


7

A contraction in a metric space is a mapping $f:X\to X$ such that there exists $0<c<1$ such that for all $x,y\in X$, $x\neq y$, it holds that $d(f(x),f(y))\leq cd(x,y)$. Indeed, the Banach fixed-point theorem shows that such mappings on complete metric spaces always have a unique fixed point. However, if one relaxes the conditions to require only ...


7

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


7

As an odd-degree polynomial, $x^3+x+1=0$ certainly has real solutions, but none that are rational. Applying the rational root theorem shows us that the only possible rational roots are $\pm1$, and substitution shows us that neither of these works. It's worth noting that you can't conclude from $a\cdot b=-1$ that $a=-1$ or $b=-1$. For example, let ...


6

If $4q^2 = p^2$, $4$ is a factor of $p^2$, but it does not follow that $4$ is a factor of $p$ only that $2$ is a factor of $p$. For example, $4$ is a factor of $36$, but $4$ is not a factor of $6$ (but $2$ is). In general, if $a$ is prime and $a$ is a factor of $pq$ then $a$ must be a factor of $p$ or a factor of $q$ (or both); in particular, if $a$ is a ...



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