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$ Commented Jan 28, 2021 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$ Commented Jan 29, 2021 at 3:05
  • $\begingroup$ Don't forget to do your base case. $\endgroup$ Commented Jan 29, 2021 at 15:24

2 Answers 2

Reset to default
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$ Commented Jan 29, 2021 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$ Commented Jan 29, 2021 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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.