Tricki
a repository of mathematical know-how

Revision of Induction from Wed, 04/02/2009 - 18:47

When this article is written, it should have examples of several different styles of inductive proof: the usual kind where you deduce P(k) from P(k-1), the slightly more sophisticated kind where you deduce it from the fact that P(j) is true for every j<k, induction over more sophisticated well-ordered sets, use of the well-ordering principle, etc.

Transfinite induction is discussed in a separate article.

See also Using generators and closure properties.

Parent article

Proving "for all" statements

Comments

Moved the discussion to the comments

When this article is written, it should have examples of several different styles of inductive proof: the usual kind where you deduce P(k) from P(k-1), the slightly more sophisticated kind where you deduce it from the fact that P(j) is true for every j<k, induction over more sophisticated well-ordered sets, use of the well-ordering principle, etc.

Induction without an indexing set

"The generalized induction is harder because we don't have a nice indexing set like the natural numbers. Is there a way of doing induction without the crutch of an indexing set? Yes there is: you look for a minimal counterexample."

The above is from this article by Prof Gowers: http://www.dpmms.cam.ac.uk/~wtg10/bounded.html.

I feel that this could be put somewhere, but I am not sure where. The connection between the well-ordering principle and induction could also be mentioned (albeit briefly, since it doesn't seem like a trick).