This is exercise 7.9 of "An Introduction to Mathematical Reasoning" by P.J.Eccles, for which the author provides a solution.
However, I've reached an alternative reformulation for the inductive step which differs from the author and I can't tell if it's correct. The problem statement goes as follows:
Find a reformulation of the strong induction principle as a method for proving that subsets of $\mathbb{Z}^+$ are the whole set.
The author provides the following axiom for strong induction:
Suppose that $P(n)$ is a statement involving a general positive integer $n$. Then $P(n)$ is true for all positive integers n if
(i) $P(1)$ is true, and
(ii) [$P(n)$ holds for all positive integers $n \le k$] $\implies$ $P(k+1)$, for all positive integers $k$.
And here is my proposed reformulation:
Suppose that $A$ is a subset of $\mathbb{Z}^+$, the set of positive integers. Then $A=\mathbb{Z}^+$ if
$\quad$(i) $1 \in A$, and
$\quad$(ii) $\forall k,n \in \mathbb{Z}^+, n \le k (n \in A \implies k+1 \in A)$
As for the above reformulation, I had previously developed the following for the inductive step:
(ii) $\forall k \in \mathbb{Z}^+(\forall n \in \mathbb{Z}^+, n \le k(n \in A \implies k+1 \in A))$
However, I found it a little ambiguous, either because of the double parenthesis, or because of the extra use of the universal statement, and that's when I came up with the reformulation I've given first.
However, the author proposes the following solution.
Suppose that $A$ is a subset of $\mathbb{Z}^+$, the set of positive integers. Then $A=\mathbb{Z}^+$ if
(i) $1 \in A$, and
(ii) $\forall k \in \mathbb{Z}^+((1 \le n \le k \implies n \in A) \implies k+1 \in A)$.
And as you can see, everything is the same except for the inductive step.
Hence, my question: is mine and the authors reformulation of the inductive step the same but differently stated, or have I made wrong use of the quantifiers and reached an invalid reformulation of the strong induction axiom?
Thank you!
Your reformulation is incorrect.
$$\forall k,n \in \mathbb{Z}^+( n \le k \Rightarrow(n \in A \implies k+1 \in A))$$ (suppose you meant this) is much stronger than $$\forall k \in \mathbb{Z}^+((1 \le n \le k \implies n \in A) \implies k+1 \in A)$$ In fact, the former proposition implies, for example, $P(1)\Rightarrow P(100)$ (take $k=100$, $n=1$). Such strong restriction is hardly suitable for a reformulation of induction principle.