0
$\begingroup$

Let us assume we already know the Principle of (weak) Mathematical Induction (if $\mathrm{P}(0)$ is true and $\mathrm{P}(n+1)$ is also true whenever $\mathrm{P}(n)$ is, then $\forall n \in \mathbb{N} \ \ \mathrm{P}(n)$ is true) which is really a trivial consequence of the construction of $\mathbb{N}$. We can also assume the well-ordering principle for $\mathbb{N}$.

What I need to prove is the following "generalized" (weak) induction principle:

$\forall k \in \mathbb{N} \ \ \forall$ properties $\mathrm{P}(x)$

($\mathrm{P}(k)$ holds and $\forall n \in \mathbb{N}, k \leq n: \ \mathrm{P}(n) \Rightarrow \mathrm{P}(n+1)) \Rightarrow \forall n \in \mathbb{N}, k \leq n: \ \mathrm{P}(n)$ holds

I have tried to use the ordinary induction on $k$. For $k = 0$ it becomes the Principle of (weak) Mathematical Induction.

However, even assuming it's true for $k$, I can't seem to prove it also is for $k+1$.

Before asking this question, I was sure it had been asked already, but I can't seem to find a prood of that exact theorem. It's either the weak induction with a basis $0$, or the strong induction.

$\endgroup$
1
$\begingroup$

Sure, fix $k$. Define the property $Q(n)$ as $P(k+n)$.

Now we can prove that $Q(0)$ holds, and $Q(n)\rightarrow Q(n+1)$. By induction, we get that for all $n$, $Q(n)$ holds. Which translates to $P(n)$ for all $n\geq k$ holds.

Alternatively, define $Q'(n)$ as "true" for $n<k$ and $P(n)$ for $n\geq k$, and again prove by induction that $\forall n: Q'(n)$ holds.

Since our $k$ and $P$ were arbitrary, the conclusion follows.

$\endgroup$
  • $\begingroup$ Thank you, but do you know any ways to prove it without defining addition for natural numbers? The book I'm working through (Hrbacek's and Jech's "Introduction to Set Theory") gives us this exercise before even touching the subject of arithmetic on $\mathbb{N}$. $\endgroup$ – Jxt921 Mar 5 '17 at 18:48
  • 1
    $\begingroup$ Sure. I've edited to incorporate this. $\endgroup$ – Asaf Karagila Mar 5 '17 at 18:50

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.