Talk:Infinite descent
From Wikipedia, the free encyclopedia
How about some examples?
It is not true that infinite descent is a type of induction. If we want to prove by induction that every number x has property P, we must know that a specific number x1 has property P. From this we prove that every number has this property. On the other hand, If we want to prove by infinite descent that every number x has property P, we do NOT need to have a specific example for a number which has the property P. We just say that if there exists a number x that doesn't have property P, then there must exist a smaller number that doesn't have property P, and this is impossible - not because we know of a number x for which the property P is true, but because a descending sequence of natural numbers (say) is impossible.
Actually this kind of proof uses the well-ordering principle of natural numbers. Accepting this principle is equivalent to accepting the principle of induction (they are equivalent). So in some way this is a proof by induction, since it uses the principle of induction. I believe there is proof of the equivalence in the Proof of mathematical induction article.
I think the proof could use some extra detail in the part which states that "3|a^2+b^2 <-> 3|a and 3|b". This can be done easily although I'm not comfortable with the syntax so maybe someone else can merge it as a reference note? (edit this page for reading the dem. since the line breaking gets messed up)
(1) Suppose 3|a, and 3 is prime 3|a -> 3|a^2 3|a^2+b^2 and 3|a^2 -> 3|b^2 Because 3 is prime, 3|b^2 -> 3|b So one possibility is 3|a and 3|b.
(2) Suppose not 3|a not 3|a -> not 3|a^2 3|a^2+b^2 and not 3|a^2 -> not 3|b^2 -> not 3|b Therefore 3 and b are coprimes, and 3 and a are coprimes, which we use in the congruence equations of fermat's little theorem: a^2 = a^(3-1) = 1 mod 3 b^2 = b^(3-1) = 1 mod 3 Then a^2 + b^2 = 1 + 1 mod 3 = 2 mod 3 and this is absurd. Finally 3 must divide a, and therefore divide b as proven in (1)
As far as the example above re: changing the proof, I didn't think that "n|a^2+b^2 <-> n|a and n|b" would need a proof here, maybe just a reference to a proof if even that. But for clarity, what comparison is used to say that one solution is less than another? No mention is made, which might be assuming more than it should be in this context.
[edit] CAN I PUT THIS ON ?
If √2 is a rational number, then there must exist a set of integers {S1 S2 S3 ...} any one of which, when multiplied by √2 give an integer. This set must have a smallest member Let S1 be the smallest of this set. S1√2 = Integer. S1(√2 - 1) = an integer <S1 because (√2 - 1)< 1 so S1(√2 - 1)*√2 = an integer, so S1 cannot be the smallest integer with this property. I found this proof on the internet some time ago. I think it would serve as a very simple example under the heading : Simple application examples I did not invent this proof I found it here but this is my own explanation of it. So would I be OK as far as copyright is concerned, and can anyone see a mistake or room for improvement ? Robert2957 14:57, 28 October 2006 (UTC)
