I am reading this wikipedea article on the proof of irrationality of $\sqrt{2}$. It uses the principle of infinite descent. I understand it as:

  1. We assume $\sqrt{2}=\dfrac pq$, where $p$ and $q$ are some positive integers.
  2. We have $2q^2 = p^2 \implies$ $p$ is even, i.e. $p=2r$ for some positive integer $r$.
  3. Now we have $2q^2=(2r)^2 \implies q$ is also even, i.e. $q=2s$ for some positive integer $s$.

From steps 1,2 and 3 we conclude that both $p$ and $q$ have $2$ as their factor at least one time. So we can say $\sqrt{2}=\dfrac pq = \dfrac rs$.

Now we can repeat the steps 1,2 and 3 with $\sqrt{2}= \dfrac rs$. This will eventually imply that intezers $r$ and $s$ also have 2 as their factor at least one time, or $r=2r_1$ and $s=2s_2$. Recalling $p=2r$ and $q=2s$ implies that $p$ and $q$ have $2$ as their factor at least two number of times.

The notable fact is that we can repeat steps 1,2 and 3 infinite number times, which implies that $p$ and $q$ have 2 as their factor infinite number of times, but this can't be for any finite $p$ and $q$, that is to say their does not exist any intezer which can have 2 as its factor infinite number of times. So we conclude that there doesn't exist any $p$ and $q$ which satisfies $\sqrt 2 = \dfrac pq$, hence $\sqrt 2$ is irrational.

Question 1: Do I understand the proof correctly?

Question 2: I noted that this proof on wikipedea is titled as Proof by infinite descent, where it does not use the concept of infinite descent at all. So why is it titled as Proof by infinite descent?

  • $\begingroup$ Question 1: yes. Question 2: it is proved so because it is a proof by infinite descent. Why do you think it is not? $\endgroup$ – Timbuc Nov 14 '14 at 11:55
  • $\begingroup$ @Timbuc 2. Because it doesn't uses the principle of infinite descent at all. $\endgroup$ – user103816 Nov 14 '14 at 11:57
  • $\begingroup$ but it does: you have a proof in which you begin with something , $\;p/q\;$ , and then from it you get something else $\;r,s\;$, with $\;r/s<p/q\;$ , which fulfills exactly the same as $\;p/q\;$ ... $\endgroup$ – Timbuc Nov 14 '14 at 12:01
  • $\begingroup$ @Timbuc It is, but they do not carry it forward, i.e. they just stop without repetition. The correct version is this :en.wikipedia.org/wiki/… here they explain how we repeat the steps infinitely. on the other hand here:en.wikipedia.org/wiki/… they do not say anything about infinite descent in the 10 steps. $\endgroup$ – user103816 Nov 14 '14 at 12:04
  • $\begingroup$ the second link talks of a proof by direct contradiction, which is probably the most widely known. The first one seems to be the one you repeat, and to which I refer: it is infinite descent. $\endgroup$ – Timbuc Nov 14 '14 at 12:09

It would seem that the first proof you linked to, and transcribed in the question, is a proper proof by infinite descent.

The proof in the second link is not a proper proof by infinite descent; it is more or less formulated as a proof of the non-existence of a minimal counterexample. An not even quite that, since the hypothesis used is not that the pair $(a,b)$ is minimal, but that it is reduced (has no common factors); as stated it depends on the preliminary result that all rational numbers can be represented by a reduced fraction. But that dependency could be avoided by rephrasing it to assume a counterexample $(a,b)$ with (say) $a+b$ minimal; clearly this implies easily that $a/b$ is reduced. Also note the reducedness is not used anywhere except at the end to detonate the contradiction; minimality would have done quite as well for that purpose.

Although close in spirit, a proof by infinite descent is not the same as a proof by non-existence of a minimal counterexample. The former establishes from any counterexample an (impossible) infinite descending chain of counterexamples. Clearly this implies that a minimal counterexample cannot exist. But a proof of non-existence of a minimal counterexample just needs to derive a contradiction from the supposed existence of a minima counterexample. The contradiction may, but does not have to, derive from the construction of an even smaller counterexample. Only if that is the case, and moreover the minimality is not used in the construction itself, can one convert the proof into one by infinite descent. Since therefore proofs by infinite descent are no easier than by non-existence of a minimal counterexample, possibly harder, and in any case the invariably end with the not very elegant "one can repeat this construction indefinitely, leading to an infinite descent, which is impossible", they are not very popular nowadays.

Proofs by non-existence of a minimal counterexample are of course very close to proofs by induction as well, more precisely of a proof by strong induction of a statement "for any $n$ there are no counterexamples up to stage $n$". But that was not really the question here.


Answer to Question 1: Yes, that is one version of the most commonly given ("Pythagorean") proof of the irrationality of $\sqrt 2$.

Answer to Question 2: Using the proof you give, you are constructing two infinite, descending sequences $p_i,q_i$ of natural numbers by repeatedly extracting their common factor $2$. Given that there are only finitely many natural numbers less than a given natural number (in particular, less than your original $p$ and $q$), you have established an impossible infinite descent, so the classification of the proof as a proof by infinite descent is entirely correct.

  • $\begingroup$ 2. No, wikipedea's proof stops at step 10 saying that $gcd(a,b) \neq 1$, which is a contradiction to step 2. Hence $\sqrt{2}$ is irrational. They do not repeat the procedere. Nor they construct $a_i$ and $b_i$. $\endgroup$ – user103816 Nov 14 '14 at 12:00
  • $\begingroup$ @user31782: The Wikipedia proof uses the labels $a,b$ rather than $p,q$ but is otherwise identical to the proof you give in your question. The contradiction derived from a fraction being irreducible being shown as having yet another common factor is the essence of the "infinite descent" idea, being made explicit rather than hidden away in the term. $\endgroup$ – user139000 Nov 14 '14 at 12:03
  • 1
    $\begingroup$ Note that the Wikipedia page on infinite descent states: "An alternative way to express this is to assume one or more solutions or examples exists. Then there must be a smallest solution or example—a minimal counterexample. We then prove that if a smallest solution exists, it must imply the existence of a smaller solution (in some sense)—which again proves that the existence of any solution would lead to a contradiction." $\endgroup$ – user139000 Nov 14 '14 at 12:05
  • $\begingroup$ I have no problem with this article:en.wikipedia.org/wiki/… . I cannot grasp that this en.wikipedia.org/wiki/… is a proof by infinite descent. In all the 10 steps they don't at all uses the concept of infinite descent. $\endgroup$ – user103816 Nov 14 '14 at 12:09
  • 1
    $\begingroup$ @user31782: Look at the quote in my above comment. If you replace "smallest" by "irreducible", you will see that this pattern perfectly applies to the linked proof, which shows that if there is a smallest (irreducible) fraction, it can yet be reduced (by $2$). $\endgroup$ – user139000 Nov 14 '14 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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