Talk:Proof by infinite descent

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.

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)

Ow... my eyes. The integers aren't well-ordered. It's necessary to make the set a subset of the positive integers (which are well-ordered) in order to assume that the set has a smalled member. Other than that, the notation hurts my eyes. —The preceding unsigned comment was added by 75.39.133.62 (talk) 07:16, 7 May 2007 (UTC).

The proof that 3|a^2+b^2 => 3|a and 3|b above I don't think you are right when you wrote b^2 = 1 (mod 3) in (2) because you have no guarantee that gcd(3,b)=1 to apply Fermat's little theorem. You have to break it into cases again, so say that not 3|b then follow what you wrote, else if 3|b then we have a clear contradiction. —Preceding unsigned comment added by 66.38.130.1 (talk) 21:30, 6 September 2007 (UTC)

This appears on the page, but it is not true:

Thus we have

   (3 a_2)^2 + (3 b_2)^2 = 3 \cdot (s_1^2+t_1^2)

and

   3(a_2^2+b_2^2) = s_1^2+t_1^2.\, 

because you cannot factor out a 3 like that. Where a = 2 and b = 3 you would have:

Thus we have

   (3 2_2)^2 + (3 3_2)^2 = 3 \cdot (s_1^2+t_1^2)

and

   3(2_2^2+3_2^2) = s_1^2+t_1^2.\,  —Preceding unsigned comment added by 200.162.223.52 (talk) 16:40, 28 September 2007 (UTC) 

No valid examples of infinite descent in article

Neither proof in this article is a valid example of infinite descent. The first one assumes that the square root of 2 can be expressed as a fraction in lowest terms, and derives a contradiction. It is a proof by contradiction, but not a proof by infinite descent. The second proof assumes the existence of a minimal counterexample. This is a valid method, but it is not infinite descent.

The proofs should be rewritten to use infinite descent. For example, show that if (a_1, b_1) is a solution to the Diophantine equation (not necessarily a minimal solution) then there exists another solution (a_2, b_2) with a_2 < b_1. Or, show that if the square root of 2 can be expressed as p/q (not necessarily in lowest terms) then there exists another fraction with smaller denominator that expresses the square root of 2. -- Me 66.41.27.169 (talk) 18:57, 7 December 2008 (UTC)