The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 1,072
Registered: 5/24/13
Re: Double Induction -- A brief note that may help
Posted: Jul 16, 2013 8:00 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.