35
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – RubeRad
    Commented Jul 15, 2010 at 14:59
  • 3
    $\begingroup$ Please see wikipedia before asking. $\endgroup$
    – Abhishek Parab
    Commented Jul 15, 2010 at 15:16
  • 10
    $\begingroup$ See Andrej Bauer's post - math.andrej.com/2010/03/29/… $\endgroup$
    – François G. Dorais
    Commented Jul 15, 2010 at 15:37
  • 6
    $\begingroup$ See also gowers.wordpress.com/2010/03/28/… (A. Bauer's post is linked there, and there are additional references.) $\endgroup$
    – Andrés E. Caicedo
    Commented Jul 15, 2010 at 16:32
  • 12
    $\begingroup$ 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. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Jul 15, 2010 at 21:11

9 Answers 9

Reset to default
53
$\begingroup$

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$

This idea immediately generalizes to a proof by induction on degree that $\Bbb Z$ is integrally closed (i.e. the monic case of the rational root test).

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's really slick too; I'll have to make some time to read the link... $\endgroup$
    – RubeRad
    Commented Jul 15, 2010 at 15:57
  • 42
    $\begingroup$ 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? $\endgroup$
    – Rasmus
    Commented Jul 15, 2010 at 16:31
  • 6
    $\begingroup$ Your theorem is neat, though. $\endgroup$
    – Rasmus
    Commented Jul 15, 2010 at 16:34
  • 4
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Jul 15, 2010 at 16:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Jul 15, 2010 at 22:39
39
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 9
    $\begingroup$ 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. $\endgroup$
    – Dan Piponi
    Commented Jul 15, 2010 at 18:07
  • 4
    $\begingroup$ 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$. $\endgroup$
    – David Corfield
    Commented Jul 15, 2010 at 18:35
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dan Piponi
    Commented Jul 15, 2010 at 20:36
  • 5
    $\begingroup$ 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. $\endgroup$
    – David Corfield
    Commented Jul 16, 2010 at 8:37
  • 1
    $\begingroup$ Aha! Looks like Bishop and Andrej Bauer (in that article) have differing terminology. Confusion lifted. Thanks @David. (I like the problem.) $\endgroup$
    – Dan Piponi
    Commented Jul 16, 2010 at 16:04
19
$\begingroup$

Rational numbers have finite continued fractions.

$\sqrt{2}=1+1/(\sqrt{2}+1)=1+1/(2+1/(\sqrt{2}+1))=\cdots$ 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).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ These are continued (not continuous) fractions. $\endgroup$
    – Robin Chapman
    Commented Jul 16, 2010 at 18:07
  • 2
    $\begingroup$ Spanish tricked me. We use the same word. Thanks. $\endgroup$
    – O.R.
    Commented Nov 4, 2010 at 1:58
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sridhar Ramesh
    Commented Jan 13, 2012 at 22:25
7
$\begingroup$

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,\ldots\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Aaron: This is nice, but why do you need to cube? Squaring suffices: $nq^2s^2+2psqt+q^2t^2=1$. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 9, 2010 at 23:06
5
$\begingroup$

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.

PS: When I wrote this I probably had in mind Inexhaustibility: a non-exhaustive treatment by Torkel Franzén, page 101.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If you ever happened to remember the book I would appreciate it if you could tell me the title. $\endgroup$
    – Ovi
    Commented May 24, 2017 at 1:17
  • $\begingroup$ @Ovi I don't know about the book, but similar ideas are expressed here gowers.wordpress.com/2010/03/28/… (linked above in this thread) $\endgroup$
    – Will Sawin
    Commented May 24, 2017 at 3:55
  • $\begingroup$ @WillSawin : When I wrote this I probably had in mind Inexhaustibility: a non-exhaustive treatment by Torkel Franzén, page 101. $\qquad$ $\endgroup$
    – Michael Hardy
    Commented May 24, 2017 at 6:30
4
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Robin Chapman
    Commented Dec 9, 2010 at 16:50
  • $\begingroup$ 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. $\endgroup$
    – roy smith
    Commented Dec 9, 2010 at 19:40
  • $\begingroup$ 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? $\endgroup$
    – roy smith
    Commented Dec 9, 2010 at 21:03
  • $\begingroup$ @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.$ $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 9, 2010 at 21:17
  • $\begingroup$ 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 $\endgroup$
    – roy smith
    Commented Dec 12, 2010 at 18:50
4
$\begingroup$

Observe that if $\sqrt 2$ is rational, then there is some positive integer q such that $q \times \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 \times (\sqrt 2 - 1) = (q \times \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 \times \sqrt 2$ is also an integer, since $r\times \sqrt 2 = (q \times \sqrt 2-q ) \times \sqrt 2 = (2q - q \times\sqrt 2)$. In short, $r$ is a positive integer less than $q$ and $r \times\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 \times ( \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 $qx^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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ There seems to be a problem with your code (the first paragraph is cut off.) $\endgroup$
    – Andrés E. Caicedo
    Commented Jul 15, 2010 at 16:33
  • $\begingroup$ Ye, Andres, thanks, don't know what the problem was but it's fixed now. $\endgroup$
    – Dick Palais
    Commented Jul 15, 2010 at 16:37
  • 2
    $\begingroup$ According to your first sentence I believe that you provide a proof by contraction which is not what the OP has asked for. $\endgroup$
    – Rasmus
    Commented Jul 15, 2010 at 16:40
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Jul 15, 2010 at 16:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Jul 15, 2010 at 19:11
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .