Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There are plenty of simple proofs out there that $\sqrt{2}$ is irrational. But does there exist a proof which is not a proof by contradiction? I.e. which is not of the form:

Suppose $a/b=\sqrt{2}$ for integers $a,b$.

[deduce a contradiction here]

$\rightarrow\leftarrow$, QED

Is it impossible (or at least difficult) to find a direct proof because ir-rational is a negative definition, so "not-ness" is inherent to the question? I have a hard time even thinking how to begin a direct proof, or what it would look like. How about:

$\forall a,b\in\cal I \exists \epsilon$ such that $\mid a^2/b^2 - 2\mid > \epsilon$

share|improve this question
    
Not sure why the LaTeX worked in the preview, but not the post! Let me retype that last line in ASCII: For all integers a,b, there exists epsilon such that |a^2/b^2 - 2| > epsilon –  RubeRad Jul 15 '10 at 14:59
3  
Please see wikipedia before asking. –  Abhishek Parab Jul 15 '10 at 15:16
5  
See Andrej Bauer's post - math.andrej.com/2010/03/29/… –  François G. Dorais Jul 15 '10 at 15:37
5  
See also gowers.wordpress.com/2010/03/28/… (A. Bauer's post is linked there, and there are additional references.) –  Andres Caicedo Jul 15 '10 at 16:32
7  
For those needing more inducement to click through than just links: Andrej's post discusses the point raised in the OP's last paragraph, the difference between classical “proof by contradiction” — “to prove $\varphi$, assume $\lnot \varphi$ and derive absurdity” — and the intuitionistically valid “to prove $\lnot \varphi$, assume $\varphi$ and derive absurdity”, which at a formal level (either classically or intuitionistically) any proof of a negative statement must essentially boil down to. Gowers' post discusses some related issues rather more informally, with a wide range of examples. –  Peter LeFanu Lumsdaine Jul 15 '10 at 21:11
show 3 more comments

9 Answers 9

up vote 22 down vote accepted

Below is a simple direct proof that I found as a teenager:

THEOREM $\;\rm r = \sqrt{n}\;$ is integral if rational, for $\;\rm n\in\mathbb{N}$.

Proof: $\;\rm r = a/b,\;\; {\text gcd}(a,b) = 1 \implies ad-bc = 1\;$ for some $\rm c,d \in \mathbb{Z}$, by Bezout

so: $\;\rm 0 = (a-br) (c+dr) = ac-bdn + r \implies r \in \mathbb{Z} \quad\square$

Nowadays my favorite proof is the 1-line gem using Dedekind's conductor ideal - which, as I explained at length elsewhere, beautifully encapsulates the descent in ad-hoc "elementary" irrationality proofs.

share|improve this answer
    
That's really slick too; I'll have to make some time to read the link... –  RubeRad Jul 15 '10 at 15:57
14  
So your proof of irrationality of $\sqrt{2}$ is follows: Assume $\sqrt{2}$ was rational. Then my theorem implies that $\sqrt{2}$ is integral, which is obviously impossible since no integer squares to $2$. QED. But this is a proof by contradiction isn't it? –  Rasmus Bentmann Jul 15 '10 at 16:31
3  
Your theorem is neat, though. –  Rasmus Bentmann Jul 15 '10 at 16:34
2  
But every proof does the same at some point - even if it's far down the line in some chain of lemmas, e.g. see the Gower's link above. –  Bill Dubuque Jul 15 '10 at 16:47
1  
Yes, of course there are many variations. But they are all mechanically derivable from the more conceptual ideal-based proofs, as I explain at length in the sci.math linked indirectly above. Thus they're all essentially equivalent and the key idea goes way back to Dedekind. I could easily write a program that could generate all of the known "elementary" proofs by unwinding the conceptual proofs, eliminating higher-order concepts like ideals, modules, and directly inlining lemmas, etc. Such elementary proofs are not novel in any way. –  Bill Dubuque Jul 15 '10 at 22:39
add comment

Wikipedia has a constructive proof. You can bound $\sqrt 2$ away from $p/q$.

share|improve this answer
    
Thanks, that exactly does it! (now if I could only reproduce the "easy calculation...") –  RubeRad Jul 15 '10 at 15:52
4  
I think there's some confusion going on here. The standard proof of the irrationality of $\sqrt 2$ is constructive, as noted in the comments above, pointing to Andrej's article: math.andrej.com/2010/03/29/… The "constructive" proof on Wikipedia is proving a result that is stronger from a constructive perspective. It's proving that $\sqrt 2$ and $a/b$ are "apart". You still need to derive a contradiction, or use a lemma that does so, in order to show that these values are distinct. –  Dan Piponi Jul 15 '10 at 18:07
3  
You have a point. This only bears on the constructivist distinction between 'It is not the case that $\sqrt 2$ is rational' and '$\sqrt 2$ is irrational'. The first of these means that the assumption that $\sqrt 2$ is rational leads to a contradiction. The second means that for any rational $p/q$, $\sqrt 2$ is apart from $p/q$ by a distance dependent on $p$ and $q$. –  David Corfield Jul 15 '10 at 18:35
1  
I'm pretty sure that with the usual definitions, 'It is not the case that $\sqrt 2$ is rational' is equivalent to '$\sqrt 2$ is irrational', constructively or not. The distinction I'm making hinges on the difference between 'apartness' and 'inequality'. The latter doesn't imply the former constructively as we don't have the familiar classical trichotomy. –  Dan Piponi Jul 15 '10 at 20:36
2  
Exercise 10 p. 62 of Constructive Analysis (Bishop and Bridges): Construct a real number that is not rational and not irrational. (A real number $x$ is irrational if $x \neq r$ for each rational number $r$.) A real number is a certain sequence of rationals. To prove it irrational, show that it is not equal to any $p/q$ considered as a constant sequence. To show inequality of two reals, show that entries at some point in the sequences are far enough apart. –  David Corfield Jul 16 '10 at 8:37
show 1 more comment

Rational numbers have finite continuued fractions.

$\sqrt{2}=1+1/(\sqrt{2}+1)=1+1/(2+1/(\sqrt{2}+1))=...$ Then the continued fraction is not finite 1+1/2+1/2+1/2+...

The geometric proof (not the one in Wikipedia), the one that proves $\sqrt{2}$ is not commensurable with $1$ is also direct (and is essentially the same as the continued fraction).

share|improve this answer
2  
These are continued (not continuous) fractions. –  Robin Chapman Jul 16 '10 at 18:07
    
Spanish tricked me. We use the same word. Thanks. –  ABC Nov 4 '10 at 1:58
add comment

From the viewpoint of prime factorization, integers are products of powers of primes in which the exponents are non-negative integers. Rational numbers are products of powers of primes in which the exponents can be any integer. In both cases, any given prime can only appear once. This, of course, means that when you square a rational number, all the exponents will be even numbers. Since 2 is not an even power of a prime, it cannot be the square of a rational number.

share|improve this answer
    
Slight clarification: POSITIVE integers are products of powers of primes in which the exponents are natural numbers, and POSITIVE rational numbers are products of powers of primes in which the exponents can be any integer. –  Sridhar Ramesh Jan 13 '12 at 22:25
add comment

Below is a direct proof that if $p,q,n$ are positive integers with $\gcd(p,q)=1$ and $p^2=nq^2$ then $q=1$ (so $n=p^2$). I would count that as a direct proof that $$\lbrace n \mid \sqrt{n}\in \mathbb{Q} \rbrace=\lbrace0,1,4,9,16,\cdots\rbrace$$ Given that $\gcd(p,q)=1$ there are integers $s,t$ with $ps+qt=1.$ Cube and regroup to get $p^2(ps+3qt)s^2+q^2(3ps+qt)t^2=1.$ Given that $p^2=nq^2$ we then have $nq^2(ps+3qt)s^2+q^2(3ps+qt)t^2=1$ so that $q$ divides 1. QED

later As Andres points out, it suffices to square. The cubing shows that $\gcd(p,q)=1$ implies $\gcd(p^2,q^2)=1$. Of course if $p,q,n$ are integers and we already know $\frac{p^2}{q^2} \ne n$ then it follows that $|\frac{p^2}{q^2}-n| \ge \frac{1}{q^2}$. I wanted an direct argument that if $p,q,n$ are positive integers with $\gcd(p,q)=1$ and $q \ge 2$ then $|\frac{p^2}{q^2}-n| \ge \frac{1}{q^2}$. I think that could be done but in this situation one wants to keep a proof short.

In my opinion, the vast majority of "indirect proofs" are actually direct proofs of something else. But that is another story.

share|improve this answer
1  
@Aaron: This is nice, but why do you need to cube? Squaring suffices: $nq^2s^2+2psqt+q^2t^2=1$. –  Andres Caicedo Dec 9 '10 at 23:06
add comment

A book on logic whose title and the identity of whose author escape me at the moment said that not all proofs by contradiction are indirect proofs. The idea is that when proving an inherently negative statement---one that asserts non-existence of something---one can proceed only by contradiction, which in that case constitutes a direct proof. I'll see if I can find it.

share|improve this answer
add comment

Observe that if $\sqrt 2$ is rational, then there is some positive integer q such that q × $\sqrt 2$ is an integer. Since the positive integers are well ordered, we may suppose that q is the smallest such number.

We next observe that since 1 < $\sqrt 2$ < 2, then $\sqrt 2$ – 1 < 1, and consequently q × ($\sqrt 2$ – 1) = (q ×$\sqrt 2$ – q ) is less than q. Let us call this new number r, and observe that it too is a positive integer. But we now have r × $\sqrt 2$ is also an integer, since r × $\sqrt 2$ = (q × $\sqrt 2$– q ) ×$\sqrt 2$ = (2q – q ×$\sqrt 2$ ). In short, r is a positive integer less than q and r ×$\sqrt 2$ is an integer. But we said that q was the smallest positive integer with this property, and so we have a contradiction.

The nice thing about this proof is how easily it generalizes. Let us denote by $|\sqrt n|$ the integer part of $\sqrt n$ . For example, since the square root of 5 is approximately 2.236, the integer part is 2. For any n that is not a perfect square, we may prove that is irrational exactly as above by considering q × ( $\sqrt n$– $|\sqrt n|$). (On the other hand, if n is a perfect square (so that $\sqrt n$ = $|\sqrt n|$) then there is no contradiction.)

More generally still, if x is a rational but not integral zero of a monic integer polynomial of degree d, let q be the least positive integer so that q$x^j$ is integral for all j < d. Then, considering q(x – n) where n is an integer with n < x < n + 1, we get a contradiction. In other words, we have proved that every rational “algebraic integer” is an integer.

share|improve this answer
    
There seems to be a problem with your code (the first paragraph is cut off.) –  Andres Caicedo Jul 15 '10 at 16:33
    
Ye, Andres, thanks, don't know what the problem was but it's fixed now. –  Dick Palais Jul 15 '10 at 16:37
1  
According to your first sentence I believe that you provide a proof by contraction which is not what the OP has asked for. –  Rasmus Bentmann Jul 15 '10 at 16:40
    
In fact it generalizes quite widely to show that any PID/Dedekind domain is integrally-closed. It's just a specialization of a the 1-line proof by way of principality of the conductor (denominator) ideal which I mentioned above. See the link in my post for much further discussion. –  Bill Dubuque Jul 15 '10 at 16:53
1  
I thought it worth emphasis for the reader since rediscoverers often think that such proofs are novel - even professional mathematicians - even number theorists! E.g. Estermann rediscovered such an elementary proof in 1975 and often boasted that it was "the first new proof since Pythagoras" and this claim was supported by some other number-theorists, e.g. Niven. –  Bill Dubuque Jul 15 '10 at 19:11
show 2 more comments

Here's another take on Bill's integrality theorem, using existence and uniqueness of fractions in lowest terms:

If sqrt(2) = p/q is in lowest terms, then 2/1 = p^2/q^2 is also in lowest terms. Hence p^2 = 2, and q^2 = 1.

share|improve this answer
2  
So why does $p/q$ being in lowest terms entail that $p^2/q^2$ is? If "in lowest terms" means having no common factors save units, then this implication doesn't hold in all integral domains. –  Robin Chapman Dec 9 '10 at 16:50
    
Forgive me - I was tempted by some of these answers to offer the most elementary and shortest proofs I know, valid in Z, and using only facts acceptable to laypersons, that sqrt(2) is irrational. Since all high school students presumably learn the rational root theorem, it is odd e.g. that few US high school algebra books conclude that the only rational roots of X^2 - 2, are integer factors of 2. –  roy smith Dec 9 '10 at 19:40
    
Although the first argument used unique factorization, the second only uses integral closure. I guess the general statement would be that an element of a given domain having no square root, still has none in the fraction field. Are there domains that are integrally closed for solutions of quadratic equations but not in general? –  roy smith Dec 9 '10 at 21:03
    
@Robin But it does in Bezout Domains. Given that $s,t$ exist with $ps+qt=1$, cube both sides and regroup: $p^2(ps+3qt)s^2+q^2(3ps+qt)t^2=1.$ –  Aaron Meyerowitz Dec 9 '10 at 21:17
    
Robin, on reflection, I don't quite understand your remark. Say we want to prove an element of a given domain is a square if and only if it is a square in its field of fractions. Bill's proof above uses that gcd(a,b) exists and is a linear combination of a,b, which holds only in a pid. My first argument above works more generally in a ufd, and my second one still more generally in an integrally closed domain. I do not know of a proof that works in a yet more general domain. Thus I asked if there is a domain not integrally closed, but closed "for squares". Do you know one?? regards, roy –  roy smith Dec 12 '10 at 18:50
add comment

Most common axiom systems I've seen are a list of $\forall$ and $\exists$ axioms. If you look at a minimal underlying logic, most of the common rules for transforming these axioms shouldn't change the $\forall$ or $\exists$ into a $\neg \exists$. So you could fix a logic system, and argue that the only method that results in a $\neg \exists$ statement is the equivalent of proof by contradiction.

You haven't fixed a logic system in your original question, but the "proof by direct substitution" method won't be sufficient.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.