Get the latest tech news
A proof of proof by infinite descent
WARNING: the following contains a whole lot of pedantry about proving theorems at a level of detail such that you could likely convince a co...
Next, the proof uses the fact that every rational number can be represented by a fraction \(\frac{a}{b}\) such that \(a\) and \(b\) are relatively prime, in other words that no positive integer other than 1 divides them evenly, which is a precise way of saying that \(\frac{a}{b}\) is in reduced form. The funny thing is that the “base case” also has a perfectly fine induction hypothesis, but typically it is useless because most of the time the proof in question is not equipped to conjure an \(m < n\) with which to exploit it. It proceeds by course-of-values induction on \(a\) where the relevant property of a is the substatement : “for all positive natural numbers \(b\) ...” (now you know why I explicitly separated the two variable quantifications in the prose statement of the lemma).
Or read this on Hacker News
