Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Double Induction -- A brief note that may help
Replies: 13   Last Post: Jul 18, 2013 12:42 AM

 Messages: [ Previous | Next ]
 Tucsondrew@me.com Posts: 1,161 Registered: 5/24/13
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 UTC-7, 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

Date Subject Author
7/15/13 Dan Christensen
7/15/13 Virgil
7/15/13 David Chmelik
7/15/13 Dan Christensen
7/16/13 William Elliot
7/16/13 Brian Q. Hutchings
7/15/13 David Petry
7/16/13 William Elliot
7/15/13 Tucsondrew@me.com
7/16/13 gnasher729
7/16/13 gnasher729
7/16/13 gnasher729
7/16/13 Tucsondrew@me.com
7/18/13 Dan Christensen