2

The definition of induction that most of us are familiar with is this: If statement $S$ is true for $1$, and $$S \text{ is true for } n\implies S \text{ is true for }n^+$$ then $S$ is true for all natural numbers. This is the only kind of induction mentioned in the wiki article on mathematical induction.

However I have seen other kinds of induction too, whose mathematical validity I'm not sure of:

  1. In some group theory proofs (Sylow's theorem, for example), I have seen the following statement: assume that statement $S$ is true for all groups of order lower than $n$. Then take any group of order $n$, and prove that $S$ is true for it. You can prove this way that $S$ is true for all groups. We're, in effect, assuming the inductive hypothesis to be true for an infinite number of groups. Also, in induction for natural numbers, the hypothesis is verified for $1$! Here, we can't possibly verify it for an infinite number of groups (all groups of order lower than $n$). In the proofs that I have read it is not even verified for groups of order $1$!

  2. In a proof in linear agebra, we have to prove a certain property for a set of $n$ vectors. We take $r\leq n$ vectors. It is assumed that any subset of $r-1$ vectors satisfies property $S$. The book then goes on prove that the set of $r$ vectors also satisfied $S$. Hence, the whole set of $n$ vectors satisfies $S$. Shouldn't we be doing it this way: assume $S$ is true for $v_1,v_2,\dots,v_{r-1}$, and then prove $S$ for $v_1,v_2,\dots,v_{r-1},v_r$? How can we assume p[roperties for $v_r$ as soon as we start considering it?

  3. Is this also a valid form of induction: prove $S$ is true for $(0,1)$, and also prove $S$ is true for $r$ implies $S$ is true for $r+1$. Then $S$ is true for $\Bbb{R^+}$.

Thank you.

algebraically_speaking
  • 197

2 Answers2

1

See the section on "complete induction" in the wiki article you linked.

You're still only verifying a finite number of cases: You prove it for all groups of order 1, then all groups of order 2, etc. You don't even necessarily need that there are finitely many groups of fixed order. The point is you've separated what you want to prove into countably many cases.

The case for n=1 wasn't verified because it's trivial. Whatever property you're trying to verify is probably trivially satisfied by the group of order 1. It might not even matter if it is satisfied for the group of order 1. For example if you're proving a theorem about decomposing a group into other groups, you don't really care about the group of order 1.

mathematician
  • 2,450
  • Could you shed some light on point 2? – algebraically_speaking Apr 07 '14 at 03:20
  • @algebraically_speaking This is just another case of "complete induction". Using induction is just saying: It's true for one vector, and it's true whenever we add a vector to a set of vectors for which it is true, so it's true for any number of vectors. I can't comment on how this proof was actually phrased. Maybe it was just written poorly. – mathematician Apr 07 '14 at 04:12
1

Induction is just a restatement of the well-ordering principle---A set is well-ordered if, given any non-empty subset of that set, then it has a least element---and the fact that the natural numbers are well-ordered.

In the case of groups, for example, suppose you want to prove that $P$ is true of all finite groups. Suppose that it is false for some (finite) group. Then as the order of a group is a natural number, there exists a group of smallest order (say $n$) for which $P$ is false. However: If you also have that $P$ is true for all groups of size less than $n$ implies that it is true for a group of size $n$, then we would have a contradiction! Hence it must be true for all finite groups.

Simon Rose
  • 6,793