Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is a simple way of proving strong induction implies weak induction and vice versa using simple predicate logic and quantifiers?

share|cite|improve this question

closed as off-topic by Carl Mummert, RedMushroom, G. Sassatelli, hardmath, wythagoras Mar 10 at 15:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, RedMushroom, G. Sassatelli, hardmath, wythagoras
If this question can be reworded to fit the rules in the help center, please edit the question.

One direction is easy, right? An instance of weak induction can be "embedded" in the strong induction scheme, simply ignoring the extra strength of the induction hypothesis. You seem familiar with terminology of first-order logic. As your Question hints, the strong induction hypothesis can be recast as a weak induction hypothesis using a quantified predicate. – hardmath Mar 10 at 14:38

Weak induction: $$\Phi(0), \forall n\colon \Phi(n)\to\Phi(n+1)\vdash\forall n\colon \Phi(n).$$ Strong induction: $$\forall n\colon (\forall m<n\colon \Psi(m))\to\Psi(n)\vdash\forall n\colon \Psi(n)$$ (All vars implied to be in $\mathbb N_0$ for brevity).

To show that weak induction implies strong induction, one lets $\Phi(n)\equiv \forall m<n\colon \Psi(m)$ for given $\Psi$: We have $\Phi(0)$ because $\forall m<0\colon\Psi(m)$ is vacuously true. Using $m<n+1\to m<n\lor m=n$, we find that $$\forall m<n\colon \Psi(m)\implies\Psi(n)\land\forall m<n\colon \Psi(m)\implies \forall m<n+1\colon \Psi(m)$$ and thus $\forall n\colon \Phi(n)\to\Phi(n+1)$. By weak induction, $\forall n\colon \Phi(n)$. Especially, for arbitrary $n$ we find $\forall m<n\colon \Phi(m)$, i.e. $\forall n\colon\Psi(n)$.

share|cite|improve this answer

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