3
$\begingroup$

Suppose we have a property $P(n)$ pertaining to natural numbers and $P(n) \to P(n+1)$. We know by mathematical induction that $P(N)$ implies $P$ being true for all natural numbers greater than or equal to $N$.

It is an obvious consequence of this that for a finite number of natural numbers greater than or equal to $N$, $P$ is also true. I am wondering, however, that whether this "finite induction" can be applied even if we didn't know mathematical induction principle. This might seem trivial, just like $P(1) \to P(2)$, $P(2) \to P(3)$ and so on, but I don't know any logical rules approving this...

$\endgroup$
3
  • 2
    $\begingroup$ Not very clear... but yes: if we know that $P(N)$ holds, and $P(N+1)$ and ... and $P(N+k)$ all hold, then this is enough to assert that $P(n)$ holds for every $n$ such that $N \le n \le N+k$, without induction. $\endgroup$ Jan 28 at 16:30
  • $\begingroup$ So I guess in our logic we admit any proof of finite steps like this as a kind of axiom, and the existence of mathematical induction is to assert that induction can be applied to a infinite set? $\endgroup$ Jan 29 at 3:05
  • $\begingroup$ Don't forget to do your base case. $\endgroup$
    – DanielV
    Jan 29 at 15:24
1
$\begingroup$

We can prove the meta-theorem that in any logical system which lets you derive $Q$ from $P$ and $P \implies Q$, there is a proof of any given $P(n)$ from a base case less than $n$ and the induction step $P(n) \implies P(n+1)$. It is not necessary that the logical system have induction as an axiom.

In that logical system, such proofs will look like

  1. Prove $P(1)$.
  2. Prove $P(1) \implies P(2)$.
  3. Prove $P(2) \implies P(3)$.
  4. Prove $P(3) \implies P(4)$.
  5. Prove $P(4) \implies P(5)$.
  6. Conclude $P(2)$, then $P(3)$, then $P(4)$, then $P(5)$ by modus ponens.

It will be able to prove any given $P(n)$, and the meta-theorem tells us that it will be able to prove any given $P(n)$. Without the axiom of induction, it will not be able to prove $\forall n\ge 1\, P(n)$.

$\endgroup$
2
  • $\begingroup$ then does the axiom of induction mean to extend induction to infinity? $\endgroup$ Jan 29 at 23:44
  • $\begingroup$ I'm not entirely sure what "extend to infinity" would mean. There's no such statement as $P(\infty)$ to begin with! Rather, the axiom of induction lets us prove all the statements at once, while without it we were already able to prove any specific one of the statements. $\endgroup$ Jan 29 at 23:58
-1
$\begingroup$

Induction will hold an any set $X$ (possibly finite) with $x_0\in X$ (the "first" element) and $f: X \to X$ (the "successor" function) such that:

$~~~~~~X=\{ x_0, f(x_0), f(f(x_0)), \cdots \} $

We have:

$~~~~~~\forall P\subset X: [x_0\in P \land \forall a\in P:[ f(a)\in P] \implies P=X]$

$\endgroup$

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.