Why is this a valid induction rule?

Question

To show a property P is true of all the nonnegative integers, show that P(0) and P(1) are true, that P(n) is true if n is a prime, and for all m, n ∈ N,(P(m) ∧ P(n) → P(mn)).

I assume that P(0) and P(1) are base cases... and that P(n) is true if n is a prime is vacuously (not sure if this is the correct terminology) true. So property P is true of all nonnegative integers because we show that the inductive step, (m, n ∈ N,(P(m) ∧ P(n) → P(mn))) is true.

I get that the property P can be shown to be true of all non negative integers, but what is a valid way of showing that the inductive step is true?

Answer 1

Let P be such that P(0) and P(1) are true, that P(n) is true if n is a prime, and for all m, n ∈ N,(P(m) ∧ P(n) → P(mn)). We seek to prove that P(n) is true for all n.

We proceed by the strong form of induction. That P(0) is true is a hypothesis, so we need only show that if P(k) is true for all $k \le n$, then P(n + 1) is true.

Case I: n + 1 is 1. In this case, P(n + 1) is true by hypothesis.

Case II: n + 1 is prime. In this case, P(n + 1) is true by hypothesis.

Case III: n + 1 is composite. In this case, there exist $a, b \lt n + 1$ such that $ab = n + 1$. Since P(a) and P(b) are both true by the inductive hypothesis, we have that P(n + 1) = P(ab) is true by hypothesis.

Answer 2

$P(n)$ for prime $n$ is not vacuously true, but rather is "given", i.e., may be assumed in this context just as $P(0)$ and $P(1)$. If you prefer, $P(2),P(3).P(5),P(7),P(11),\ldots$ are simply yet another bunch of base cases.

You ask, what is a valid way of showing that the inductive step, i.e., $$\tag1\forall n,m\in\Bbb N\,(P(m)\land P(n)\to P(mn)) $$ is true. This cannot be answered in general as it - obviously - depends on the property $P$. Depending on $P$, you may want to employ whatever methods of deduction you have available ... This is not different from "standard" indiuction, where the principle only requires you to somehow show $\forall n\,(P(n)\to P(n+1))$, but how exactly you show this, is left unspecified and depends on the property (for example if $P(n)$ is $1+2+\ldots +n=\frac{n(n+1)}{2}$, the induction step is a simple computation , but that does not mean that in other situations you need to employ a totally different proof method for tha step).

Answer 3

Suppose you have shown that $P(0)$ and $P(1)$ holds, and $P(n)$ for all prime $n$ and we also know that $P(n) \land P(m) \rightarrow P(mn)$ for all $m, n$.

Suppose $P(n)$ does not hold for all $n$. Then the set $C = \{n: \lnot P(n) \}$ is a non-empty subset of positive integers and as the positive integers are well-ordered, this set has a minimum $n_0 > 0$ (As $P(0)$ holds). Now either $n_0$ is prime which cannot be as we know that $P(n)$ holds for all primes. Or $n_0 = ab$ for $a,b$ non-negative integers. As then $a < n_0$ and $b < n_0$ $a,b \notin C$, or $n_0$ would not be the minimum of $C$. So $P(a)$ and $P(b)$ hold, but then $P(ab) = P(n_0)$ also holds, contradicting $n_0 \in C$. So there can be no counterexample and $P(n)$ holds for all $n$.