4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For theorems 2 and 3 there isn't even any issue. Just consider the statements $\forall n\in \mathbb N\left(n\neq 4\implies n+1=n+\frac{n-4}{n-4}\right)$ and $\forall m\in \mathbb N\left(m\ge n\implies m+1=m+\frac{m-4}{m-4}\right)$ where $n$ is some given large enough natural number, respectively. They both can be proved by induction. $\endgroup$ – Git Gud Mar 11 '17 at 18:44
  • $\begingroup$ Theorem 1 isn't really a problem either. Just prove $P(2m)$ for all natural numbers $m.$ That's not to say there are no proofs that are much easier if you can generalize the method of induction a bit, but they are not quite as easy to come up with as you might think. $\endgroup$ – David K Mar 12 '17 at 4:48
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 very nice. I think strong induction fits into this paradigm. Maybe worth an edit to point that out. $\endgroup$ – Ethan Bolker Mar 11 '17 at 18:59
6
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ I recommend pointing out that the expression "$\frac{x-4}{x-4}$" is valid only in a context where $x \ne 4$. So in fact your definition of $P$ in your "alternative" is invalid, because in standard logic implication is not the guarded conditional and hence both subformulae must be defined. $\endgroup$ – user21820 Mar 12 '17 at 0:07
  • $\begingroup$ @user21820 Oooh, let me ponder that a minute ... $\endgroup$ – Bram28 Mar 12 '17 at 0:10
  • $\begingroup$ @user21820 OK, that was several minutes ... I guess the way I see it is that this is a purely formal logical expression ... so the division symbol is a function symbol that can be interpreted any which way we want. ... so ... I think we're ok if we were to use this in a purely formal logical proof ... but I'm not sure ... gotta think some more ... but thanks for bringing this up! $\endgroup$ – Bram28 Mar 12 '17 at 0:17
  • $\begingroup$ See here for some of my comments on this issue. Unfortunately I've never seen any textbook that deals properly with this. It appears that only CS people are familiar with the guarded conditional.. In C/C++/Java[Script] syntax there is the conditional expression ( P ? x : y ) where only the relevant expression x or y is evaluated depending on the value of P. $P \mathrel{?\to} Q \equiv ( P \mathrel{?} Q : true )$, and here $Q$ only needs to be valid when $P$ is true. $\endgroup$ – user21820 Mar 12 '17 at 0:34
  • $\begingroup$ @user21820 Thanks! I am familiar with the guarded conditional ... but guess what, I'm from CS as well :) In fact, in a formal logic proof this 'conditional evaluation' would happen as well: when I need to prove P(x) for the x=4 case, I say 'assume $x \not = 4$. Oh, that contradicts x=4. So, I can infer the consequent. So, conditional proven, and on to the next case. But: that's indeed when this is treated as an expression to be used in a formal logic proof. As a mathematical expression, there is indeed a real problem, and you are absolutely right! I'll fix it, thanks for the head up! $\endgroup$ – Bram28 Mar 12 '17 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.