What is the contradiction in infinite descent?

Question

I wasn't able to understand where the contradiction is in this proof of the irrationality of $\sqrt{3}$.

Suppose $$\sqrt{3}=\frac{a}{b}$$ where $a,b\in\mathbb{N}$ and the fraction is in lowest terms. Observe that $$3(a-b)^2 = (3b-a)^2.$$ So, $$\sqrt{3}=\frac{3b-a}{a-b}.$$ From the first assumption, $a-b<b$. This implies that we can descend through infinitely many other fractions with smaller denominators, however, that is impossible.

Is it impossible because you can't have an infinite decreasing chain of positive integers ? Or is the contradiction the fact that we assumed the fraction is in lowest terms but we produced one with a smaller denominator ? Moreover, where does this proof break if we use, say, $4$ instead of $3$?

Answer 1

Rather than focus on the specific proof you're looking at, I'm going to try to explai infinite descent in general. This should arguably be a comment but it's a bit long.

Infinite descent, as you guessed, uses the fact that there is no infinite descending sequence of natural numbers (that is, the natural numbers are well-ordered - this is a notion which will come up again down the road, especially in logic).

That this is the case can be proved via induction (so if you believe induction, you should believe infinite descent): suppose $a_1>a_2>a_3>...$ are natural numbers. Let $A$ be their "upwards closure" - $A$ is the set of natural numbers bigger than some $a_i$. (In symbols: $A=\{x\in\mathbb{N}:$ for some $i$ we have $x>a_i\}$.) Now think about the complement of $A$.

Clearly $0$ is in the complement of $A$ (there are no natural numbers at all below $0$, so in particular $0$ isn't above any of the $a_i$s). Now suppose $n$ is in the complement of $A$. Then $n+1$ must also be in the complement of $A$: if $n+1$ were in $A$, we would have $n+1>a_i$ for some $i$, but then we would have to have $n>a_{i+1}$ since $a_i>a_{i+1}$ by assumption. This can't happen since we assumed $n$ was in the complement of $A$, so we have a contradiction. By induction, we can now conclude that every natural number is in the complement of $A$. Oops!

Conversely, you can also use infinite descent to prove that induction works (after understanding the above argument, this will be a good exercise). So infinite descent is really just another way to think about proof by induction.

Answer 2

We can use strong induction on $n$, where the proposition says:

For every natural number $m$ such that $m > n$, we have $\dfrac m n \ne \sqrt3$

Then we can avoid arguing via infinite descent.

Answer 3

Hmmm, .... saying "let $\sqrt 3 = \frac ab$ be in lowest terms" assumes we know certain things about "lowest terms". We know that each rational number has a lowest term and that in is unique. And we know that all other expressions of the rational are ones with numerators and denominators are direct multiples the numerator and denominator as expresssed in lowest terms and are therefore larger (hence why we call it "lowest terms").

That's actually a lot to assume and it really is strange that we take it for granted.

So if we are assumed to know the above results, then discovering that if $\sqrt 3 = \frac ab$ is in lowest terms, and $\sqrt 3= \frac {3b-a}{a-b}$ and $0 < a-b < b$, then that is a contradiction because ... $a -b < b$ but $\frac ab$ was in lowest terms.

But I wouldn't call that "infinite descent".

But if we didn't know any of that stuff, and all we knew was that $\sqrt 3 = \frac ab$ where $a, b$ are positive integers and as $\sqrt 3 < 2$ then $b < 2a$. and we conclude $\sqrt 3 = \frac {3a -b}{a-b}$, than we can relable $3a-b = a_1$ and $b_1 = a-b$ and we have $b_1 < b$, then we can... do it again to get $\sqrt 3 = \frac {3a_1 - b_1}{a_1 - b_1}$ and $a_2 =3a_1 - b_1$ and $b_2= a_1 - b_1$ and $0 < b_2 < b_1 < b$ and we can repeat an infinite number of times so get an infinite number of decreasing positive terms.

And that is what I would call a contradiction of infinite descent.

And it's basically through such an infinite descent that we proved all the stuff in the first paragraph in the first place.

....

As for $4$....

So if $4 = \frac {a^2}{b^2}$ then $4b^2 = a^2$ and $4b^2 - a^2 = 0$.

Then $4(a-b)^2 = 4b^2 - 8ab + 4a^2$

And $(4b-a)^2 = 16b^2 - 8ab + a^2$.

And $(4b-a)^2 - 4(a-b)^2 = 12b^2 - 3a^2 = 0$.

So $4(a-b)^2= (4b-a)^2$ and so $\sqrt 4 = \frac {4b-a}{a-b}$

Now can we assume that $a - b < b$. Not really $2^2 = 4$ so $\frac ab = 2$ so $a = 2b$ and $a-b = b$.

Likewise this won't work for $\sqrt 5 = \frac ab$

$5(a-b)^2 = (5b-a)^2$ so $\sqrt {5} = \frac {5b -a}{a -b}$ but $a - b > b$. And there's no error in infinite ascent. But $a-b$ is not a multiple of $b$ which contradicts what we know about fractions and "lowest" terms and other representations of fractions have integers that are multiples of the lowest terms.

But that's a lot more than I think we can assume without proof. And I think we need the unique prime factorization theorem to proof that.