# Irrationality proofs not by contradiction

Per now, I have basically come upon proofs of the irrationality of $\sqrt{2}$ (and so on) and the proof of the irrationality of $e$. However, both proofs were by contradiction.

When thinking about it, it seems like the definition of irrationality itself demands proofs by contradiction. An irrational number is a number that is not a rational number. It seems then that if we were to find direct irrationality proofs, this would rely on some equivalent definition of irrational numbers, not involving rational numbers themselves.

Are there any irrationality proofs not using contradiction?

-
There was a long discussion about this at MO: mathoverflow.net/questions/32011/direct-proof-of-irrationality –  Qiaochu Yuan Feb 5 '11 at 18:55
en.wikipedia.org/wiki/Square_root_of_2#Constructive_proof This is probably something you are looking for. –  InterestedGuest Feb 5 '11 at 19:00
Here is a question of a related flavor: math.stackexchange.com/questions/14970/rational-numbers –  PEV Feb 5 '11 at 19:00
In particular you may find this post by Tim Gowers interesting. A big problem with the statement of your question is that, even if your proof "looks like" it doesn't use any contradictions, how do you know it actually doesn't use any contradictions? In other words, do you want to check all the foundational statements that may come into play? –  Willie Wong Feb 5 '11 at 19:34
Thanks all for the interesting links! Guess I should've searched MO before posting. There's no answer to accept, so if you want your reputation points, please post one of the above links as an answer ;) –  Fredrik Meyer Feb 5 '11 at 19:42

An irrational number can be defined as having infinite continued fraction

The continued fraction of sqrt(2) is [1, 2, 2, 2, ...] so it's irrational.

-
How would the proof that this definition is equivalent to the normal definition go? –  AnonymousCoward Feb 6 '11 at 18:02
Leibniz: For equivalence combine the two basic facts (1) Every rational number has a finite continued fraction. (2) Every real number has a unique continued fraction. –  quanta Feb 6 '11 at 19:50
So this is a proof by contradiction then, right? :) –  Alexei Averchenko Oct 31 '12 at 5:01

A very simple proof follows from Gauss's lemma (polynomial)

If $p$ is prime, then clearly, $\sqrt{p}$ is a root of $f(x)=x^2-p$. Gauss's lemma shows that $f(x)=x^2-p$ has no rational roots (since it clearly has no integer roots). Thus $\sqrt{p}$ is irrational.

Also note the proof of Gauss' lemma is not a proof by contradiction so this entire result can be proven directly.

-
The proof in the Wikipedia article made we wonder if proving the contrapositive is equivalent to a proof by contradiction. By the usual irrationality proof of $\sqrt{2}$, it seems not, but I don't know how to prove it. –  Fredrik Meyer Feb 6 '11 at 5:47
It take it "the proof" is not the one from your link, since that is by contradiction? –  WimC Feb 5 '13 at 21:06

Consider the sum of two reduced fractions. The variables a₁ and a₂ are integers. The variables b₁ and b₂ are positive integers. $$\displaystyle \frac{a_1}{b_1}+\frac{a_2}{b_2}=\frac{a_1b_2+a_2 b_1}{b_1 b_2}$$ If the sum is an integer, then $b_1|b_2$ and $b_2|b_1$, thus $b_1=b_2$.

Summarizing, if the sum of two reduced fractions is an integer, then the denominators are equal. Contrapositively, if the denominators are not equal, then the sum of two reduced fractions is not an integer.

Now let us apply this idea to the nth root of a positive integer, m.

$$\displaystyle m^{1/n}=\frac{a}{b}\\ \displaystyle m=\frac{a^n}{b^n}\\ \displaystyle \frac{a^n}{b^n}+\frac{-m}{1}=0$$

Because the sum is an integer, the denominators must be equal.

$$\displaystyle b^n=1\\ \displaystyle b=1$$

In conclusion, the only rational solution occurs when $m^{1/n}$ is an integer. Therefore, $m^{1/n}$ is either an integer or irrational.

-
The proof is circular: it implicitly assumes that $\rm\:a,b\:$ coprime implies $\rm\:a^n,b^n\:$ coprime. But that alone suffices to prove the sought result. –  Bill Dubuque Oct 31 '12 at 4:16
@Bill, I see your point. Assuming: $m^{1/n}=\frac{a}{b}$. Given: $\gcd (a,b)=1\Rightarrow \gcd \left(a^n,b^n\right)=1$. Yields: $m b^n=a^n\Rightarrow 1=\gcd \left(a^n,b^n\right)=\gcd \left(m b^n,b^n\right)=b^n\Rightarrow b=1$. I suppose it just depends on how far down the lemma chain one wants to travel, eventually a link based on contradiction must exist. Wonder if there is a direct proof? –  cyclochaotic Nov 1 '12 at 3:17

This is a really interesting question, because it seems hard to prove that numbers are irrational without also proving they are transcendental (roughly not the roots of a polynomial with integer coefficients). I do not want to focus on arguments about whether or not something is a proof by contradiction. Most proofs can be dressed up that way without seeming to unnatural, and conversely. I want to focus on how you go about proving something irrational. Eg Euler gamma constant, to take a notorious example.

Of course, if you look at the Cantor side of things we expect "almost every" number to be transcendental, and few indeed to be irrational but not transcendental. But it seems to be easier for someone who has been through the standard graduate school courses to prove a number transcendental than irrational. (I am not knocking those courses, just trying to indicate the typical knowledge of someone attacking the problems).

Nonetheless there are some standard approaches. A good introduction is in Proofs from the Book 3rd ed (be sure to get that edition, this entry has been substantially over the editions - ie ISBN10 3540404600, Aigner & Ziegler). The leading approach is integrals. The classic Book proof there is unfortunately not in the book, but is available on the web as a free pdf (you can get it by the standard searches): the rejigging of Apery's proof by Frits Beukers, Bull LMS 11 (1979) p268-72. There is also an interesting informal article he wrote 25 years later "Consequences of Apery's work on zeta(3)" (I think it is on Arxiv). Various people have tried to generalise it with less success than one might expect so far.

Then there are the tricks. Such as the classic one first published as an exercise (!) (well, that is an exaggeration, an exercise with hints), in those elementary math books by Yaglom^2, now available in English translation - chock full of beautiful stuff, often based on Moscow Olympiad problems [see ISBN10 0486655377m "Challenging Mathematical Problems with Elementary Solutions, Vol II", Dover, section X p22-24].

But are they really just tricks? Tricks often hide deeper things. It is worth trying to figure out why they work.

However, there is certainly no equivalent of Alan Baker's work when it comes to irrationality. But then there are few numbers which anyone really believes will turn out to be irrational but not transcendental.

-

Cantor's diagonal argument shows that for any countable list of numbers, one can construct a number not on that list. Cantor used this argument to show, for example, that there are transcendental numbers, since one may describe a way to list all the polynomials with integer coefficients and their roots and hence to list all the algebraic numbers.

One sometimes hears it asserted that Cantor's proof of the existence of transcendental numbers is a "pure-existence" proof, showing merely that transcendental numbers exist, but not that any particular number is transcendental. But that view is not correct, for the argument is completely constructive: one may explicitly describe an enumeration of the algebraic numbers and the diagonal procedure produces a definite real number that is not algebraic. (I once saw an article, I think in one of the MAA volumes, with the title something like "0.24543... is transcendental", where they implemented Cantor's actual algorithm.)

The relevance to this question is that Cantor diagonalization also can be used to prove that specific real numbers are not rational, by producing real numbers that are explicitly different from every rational number. Specifically, we may enumerate the rational numbers as $q_k$ in any of the usual effective manners, and define a real number $z$ so that the $k$-th digit of $z$ is $4$, say, if $r_k$ does not have $k$-th digit $4$, and otherwise the $k$-th digit of $z$ is $5$. It now follows by construction that $z\neq r_k$ for each $k$, which is what it means for $z$ to be irrational.

-
Cantor's diagonal argument: en.wikipedia.org/wiki/Cantor's_diagonal_argument –  JDH Feb 6 '11 at 3:52
I never really thought of Cantor's diagonalization as a means to produce irrational numbers, but of course it is (finding an explicit bijection between $\mathbb{Q}$ and $\mathbb{N}$ shouldn't be too hard either). It is interesting to note that the method only produces irrational numbers, and cannot be used to prove irrationality of chosen numbers. –  Fredrik Meyer Feb 6 '11 at 5:32