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


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).

