
Re: Double Induction  A brief note that may help
Posted:
Jul 16, 2013 8:00 PM


On Tuesday, July 16, 2013 4:08:29 PM UTC7, christian.bau wrote: > On Wednesday, July 17, 2013 12:02:52 AM UTC+1, christian.bau wrote: > > > > Apologies, I hope I get it right this time: > > > > That would indeed prove P (x, y) for all pairs x, y. However, it may be impossible to prove one of these. For example, I might be able to prove P (x, y) implies P (x+1, y), and I might only be able to prove that if P (x, y) is true for all integers x, then P (0, y + 1) is true. > > > In general you need to show: There is a way to order all pairs (x, y) in a list in such a way that > > > 1. P (x, y) is true for the first element in the list. > > 2. For every x, y other than the first element in the list, there is an earlier element (x', y') such that P (x', y') implies P (x, y).
I'm now pretty sure that it depends on the situation. The proof may follow in various ways.
The method I described above will work. Also, ordering N x N in a manner such that there is a linear ordering on P(x,y) will work: your method.
The question is which is easier in the given situation. The situation will definitely come into play in your situation. The linear ordering of P(x,y) will be based on a funtion F: N x N > N. This could be F(x,y) = x + y, or F(x,y) = x * y, or many other things.
If the problem presents a simple way to define F, and so define the ordering, then go that route. However, if one sees a easy way to apply induction on x when y = 1, and then on y when is held constant; the use that method.
A digression of Philosophy. The above is why I resist the idea that a Computer can constantly find all new proofs. There is a certain bit of intuition involved in decided the method of proof.
A good example is when I first saw the proof of The Cantor?Bernstein?Schroeder Equivalence Theorem. The result is easy enough to understand, but the proof is quite another. My first thought was "Who on Earth thought of that?". After understanding the proof, I see the underlying intuition.
I apologize for the verbosity. ZG

