0
$\begingroup$

I am studying analysis 1 by Tao. And here is the definition of strong induction in his book.

Strong induction: Let $m_0$ be a natural number,and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m≥m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0≤m'<m$, then $P(m)$ is also true.(In particular, this means that $P(m_0)$ is true, since in the case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m≥m_0$.

I saw in few posts on MSE including Strong Induction Requires No Base Case?
I saw that write the strong induction as $$ ∀m ≥m_0[ ∀m'(m_0≤m'<m \implies P(m'))] \implies P(m)$$ But according to me the logical form would look like this $$ ∀m[ ∀m_0≤m'<m, P(m')] \implies P(m)$$

My Question: why people are introducing extra implication? that is $$ ∀m'(m_0≤m'<m \implies P(m')).$$

$\endgroup$
7
  • $\begingroup$ Your "logical form" is not correct. $\endgroup$ Commented Jul 14, 2023 at 15:29
  • $\begingroup$ @AnneBauval Oh I see. Can you please tell me what is correct and why? And why it isn't correct. $\endgroup$ Commented Jul 14, 2023 at 15:30
  • $\begingroup$ What is correct is the formula you reported just before "But according to me", and it is correct because it is precisely the formal transcription of Tao's definition of "Strong induction". $\endgroup$ Commented Jul 14, 2023 at 15:35
  • $\begingroup$ @AnneBauval oh. But I can't see this implication in the definition of strong induction! It simply says "If $P(m')$ is true for all $m_0≤m'<m$". This doesn't looks me an implication that "If for all $m_0≤m'<m$, then $P(m')$ is true" $\endgroup$ Commented Jul 14, 2023 at 15:36
  • 2
    $\begingroup$ Your writing "forall $m_0\le m'<m$" is formally incorrect. the "forall" must immediately be followed by $m'$. Then, the formalization of "$P(m')$ is true for all $m'$ such that $R(m')$", or "forall $m'$ such that $R(m')$, we have $P(m')$", requires an implication sign:$$(\forall m')(R(m')\implies P(m')).$$ $\endgroup$ Commented Jul 14, 2023 at 15:51

0

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.