Is the induction principle still viable if the induction skips over, or does not hold for some numbers?

Question

The axiom of induction, which induction is based on can be stated as (for example in Peano axioms):

$$P(0)\wedge\forall x (P(x) \rightarrow P(S(x))) \rightarrow \forall x P(x)$$

Where P is some property of a number and S is the successor function.

This poses an interesting question, can the following theorems, which intuitively feel like they must obviously be valid be proven from the Peano axioms, (or in general).

Theorem 1. Consider the the induction ranging over only a subset of the natural numbers rather than over all of them. By having a similar induction rule for the subset, can we state that the property holds for the subset? Example: can we prove by induction that all even numbers have a property P by proving that 1 has that property and then that any even number k+2 has that property (assuming that even number k has that property).

Theorem 2. Can we say that if the induction proof fails only for some numbers, the result nonetheless holds for the rest. Example: $n+1 = n+(n-4)/(n-4)$ can be proven for all case, except for when $n=4$, so we should be able to say that the induction proof holds as long as n is not 4.

Theorem 3. Same as theorem 2 except now the induction would hold only after n, so that it wouldn't hold for the base case n=0.

Answer 1

Think about it this way. Let $S = \{n : P(n) \text{ is true}\}$. Then $S$ is the set of all numbers for which the proposition holds. What if, as an example, I told you that $S$ has the following few properties:

1. whenever $n$ is in $S$, then $2n$ is in $S$
2. whenever $n > 3$ is in $S$, then $n - 3$ is in $S$

You could say nothing: $S$ could be empty. But, if you know that $1$ is in $S$, then from (1) we know that $2, 4, 8, 16, 32, ...$ are all in $S$; and then from (2) we know that $1, 5, 13, 29, ...$ are in $S$; and then from (1) again we know that $10, 20, 40, 80, ...$ are in $S$; and then from (2) we know that $7, 17, 37, 67, ...$ are in $S$; and then from (1) we know that $14, 34, 74, ...$ are in $S$, etcetera. It should be clear now that $S = \{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, ...\} = \mathbf{N}\setminus 3\mathbf{N}$.

The moral: don't think about whether the "induction proof holds". Instead, think about the set $S$, and its closure under your collection of implications. Typical induction has $1 \in S$ and $n \in S \implies n+1 \in S$, and in this case $S = \mathbf{N}$. Strong induction has $1 \in S$ and ($k \in S$ for all $k < n$) $\implies n \in S$. Another set of implications for which $S = \mathbf{N}$ is $1 \in S$ and $n \in S \implies 2n \in S$ and $1 < n \in S \implies n-1 \in S$: I've seen this used by Artin in his little monograph on the $\Gamma$ function.

Answer 2

Yes, induction still works, but you'll either want to change the formula as a whole, or adjust the $P(x)$ formula. I'll explain below.

Theorem 1

First: you want to start with 0, not 1.

To work with even numbers only, you have a number of options:

• You can use P(x) to P(s(s(x))), and conclude that it is true for all even numbers, rather than for all numbers. So:

$$(P(0)\wedge\forall x (P(x) \rightarrow P(S(S(x))))) \rightarrow \forall x (Even(x) \rightarrow P(x))$$

• Alternatively, you can use:

$$(P(0)\wedge\forall x (P(2*x) \rightarrow P(2*S(x)))) \rightarrow \forall x P(2*x)$$

• Or keep the inductive axiom as it is, and use $P(x)$ : $Even(x) \rightarrow P(x)$. So then you get:

$$((Even(0) \rightarrow P(0))\wedge\forall x ((Even(x) \rightarrow P(x)) \rightarrow (Even(S(x)) \rightarrow P(S(x)))) \rightarrow \forall x (Even(x) \rightarrow P(x))$$

Theorem 2

Again, a few options:

• You can do 0,1,2,3 individually, and do 5 and up using induction, starting with 5:

$$(P(5)\wedge\forall x \ge 5 : (P(x) \rightarrow P(S(x)))) \rightarrow \forall x \ge 5 : P(x)$$

where $P(x) : x + 1 = x + \frac{x-4}{x-4}$

• Alternatively, keep the inductive axiom as is, and use:

$P(x) : x \not = 4 \rightarrow x + 1 = x + \frac{x-4}{x-4}$

EDIT (thanks @user21820 for pointing this out!)

This last expression can be used as a symbolic statement for a formal proof, but as a mathematical expression this will not do since x=4 is part of the domain and so we have an ill-defined expression given the $\frac{x-4}{x-4}$ term.

Theorem 3

Same thing.

• Either start with n+1:

$$(P(S(n))\wedge\forall x > n : (P(x) \rightarrow P(S(x)))) \rightarrow \forall x > n : P(x)$$

• Or keep the axiom as it is and use:

$P(x) : x > n \rightarrow \phi(x)$