Question

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$

Answer 1

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.

Answer 2

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

Answer 3

Rational numbers have finite continuous fractions.

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.