I was reading a book and I came across the following:
Can someone explain exactly how the two expressions are different? A concrete example would be particularly helpful.
My sense is that the first one could be written as $(\forall n\in\mathbb{Z}_{\geq3})(\forall m\leq n)(S(n))$, where $m$ is understood to be an integer while the second expression could be written as $(\forall n\in\mathbb{Z}_{\geq3}\land m\leq n)(S(n))$, where $m$ is again understood to be an integer. I'm simply not seeing the main differentiator between the two expressions. Ideas or examples?
Edit: Is the first expression essentially saying that all $m$ are packaged into one statement (so for $S(n)$ to be true all $m$ would have to work) while in the second the $m$ are independent? That is, if $S(n)$ is true for some $m$, then $S(n)$ will simply be true for those $m$ but possibly false for other $m$?
$(\forall n\in\mathbb{Z}_{\geq3}\land m\leq n)(S(n))$ is not a well-formed formula. The appropriate way to write it would indeed be $(\forall n\in\mathbb{Z}_{\geq3})(\forall m\leq n)(S(n))$, but this is missing the point. The point is whether the $\forall m\leq n$ is part of $S$ or not. The options are either: $\forall n\geq 3.S_1(n)$ or $\forall n\geq 3.\forall m\leq n.S_2(m,n)$ where $S_1(n)=\forall m\leq n.S_2(m,n)$.
Still, the presentation is confusing. "For each $n\geq 3$ let $S(n)$ be..." makes it sound like we're defining a different proposition for each $n$ and only when $n\geq 3$. Really what's happening is more like: "Let $S_1(i)$ be ... then for each $n\geq 3$, $S_1(n)$ holds" or "let $S_2(i,j)$ be ... then for each $n\geq 3$ and $m\leq n$, $S_2(m,n)$ holds". That is $S_1$ and $S_2$ are defined for all (pairs of) natural numbers, and then we are going to state that they are true when certain conditions hold. Since induction only proves statements of the form $\forall n\in\mathbb N.P(n)$, we need to incorporate any additional conditions into $P$.
Spelling out exactly what's going on in the example, we have some arbitrary $S_2(i,j)$, and in terms of this, we can write the formula as:$$\forall n\in\mathbb N.\forall m\in\mathbb N.(n\geq 3\land m\leq n)\implies S_2(m,n)$$ which is equivalent to $$\forall m\in\mathbb N.\forall n\in\mathbb N.(n\geq 3\land m\leq n)\implies S_2(m,n)$$
Now we need to formulate a predicate $P$ to apply induction to. The book is referring to the following two choices (although there is a corresponding two by doing induction to infer the $\forall m\in\mathbb N$, i.e. induction on $m$, and yet another by doing simultaneous induction over both $m$ and $n$).
We can choose $P_1(n)=\forall m\in\mathbb N.(n\geq 3\land m\leq n)\Rightarrow S_2(m,n)$ or we can choose $P_2(m,n)=(n\geq 3\land m\leq n)\Rightarrow S_2(m,n)$. (Note, $P_1(n)=\forall m\in\mathbb N.P_2(m,n)$.) The latter corresponds to fixing a particular $m$, and showing by induction that for the fixed $m$, $P_2(m,n)$ holds for all $n$. These different choices lead to different induction schemes. In particular, using $P_1$ gives a stronger induction hypothesis. Namely, when proving $P_1(n+1)$ we have the induction hypothesis $\forall m\in\mathbb N.P_2(m,n)$ which states that we have $P_2(m,n)$ for all $m$, whereas if we did induction over $n$ in $P_2(m,n)$ for some fixed $m$, the induction hypothesis would only give us $P_2(m,n)$ for the fixed $m$. The flip side of that is we only need to show e.g. $P_2(m,n+1)$ for some fixed $m$ where $P_1(n+1)$ would require showing $P_2(m,n+1)$ for all $m$.
Whether $P_1$ or $P_2$ is appropriate depends on the structure of your proof. The benefit of $P_1$ is that it sets you up to use (a nested) induction (on $m$) to prove $P_1(0)=\forall m\in\mathbb N.P_2(m,0)$ and $P_1(n+1)=\forall m\in\mathbb N.P_2(m,n+1)$. However, if we can prove $\forall n\in\mathbb N.P_2(m,n)$ for an arbitrary $m$ without analyzing it, then we can immediately do universal generalization to get $\forall m\in\mathbb N.\forall n\in\mathbb N.P_2(m,n)$. This will likely produce a simpler proof but often won't succeed.