Let us first outline a proof that the mathematical (it might be more precise to call “arithmetic”) induction principle (MIP) and the well-ordering principle (WOP) are equivalent:
$$\mathrm{MIP}\iff\mathrm{WOP}$$
Recall that WOP states that every non-empty set of natural numbers contains a least element. In both directions, we shall employ reductio ad absurdum.
$\mathbf{MIP\implies WOP.}$ Suppose $U$ be a non-empty subset of natural numbers with no least element and $V$ is the complement of $U$.
$0\not\in U$, otherwise, it would be the least element. Therefore, $0\in V$.
Suppose every natural number $\leq n$ is in $V$. In case that $n+1\in U$, it would be the least element of $U$, since every natural number smaller is in the complement of $U$. But this is contradictory to that $U$ has no least element, therefore $n+1\in V$.
Carrying on in this fashion, every natural number is in $V$, by induction. Hence, $U=\emptyset$.
$\mathbf{WOP\implies MIP.}$ Suppose $P$ is a property of a natural number such that $P(0)$ is true, and $P(n)$ being true implies that $P(n+1)$ is true. Let $U$ be a non-empty set of natural numbers $k$ such that $P(k)$ is false.
Let $l$ be the least element of $U$. Since $P(0)$ is true, $0\not\in U$, so $l\neq 0$ and $l−1$ is a natural number. Since $l$ is the least element, $l-1\not\in U$. So, $l$ falls in the set such that $P(l−1)$ is true. But then by the property of $P$, $P(l−1)$ being true implies that $P(l)$ is true. So $l\in U$, contradictory to our assumption.
Therefore, $U=\emptyset$ and $P(k)$ is true for all $k$.
Hence, from a general vantage point, MIP and WOP do not have a priority one over another.
Then, we shall turn to Peano Arithmetic (PA) for a more foundational level. The non-logical vocabulary of the language of (first-order) PA (the logical vocabulary as the standard first-order predicate logic is assumed) consists of the constant ‘$\mathbf{0}$’, the one-place successor function symbol ‘$\mathbf{S}$’, and the two-place function symbols ‘$\mathbf{+}$’, ‘$\mathbf{\cdot}$’. In model-theoretic signature form:
$$\langle\mathbb{N},\mathbf{S},\mathbf{+},\mathbf{\cdot},\mathbf{0}\rangle$$
with the ordinary intended interpretation. The axioms are the universal closures of the following statements (there are alternative axiomatisations; in fact, Giuseppe Peano's original formulation was different):
- $\mathbf{0}\neq\mathbf{S}x$
- $\mathbf{S}x =\mathbf{S}y\rightarrow x = y$
- $x+\mathbf{0}=x$
- $x+\mathbf{S}y=\mathbf{S}(x + y)$
- $x\mathbf{\cdot}0=0$
- $x\mathbf{\cdot}y=(x\mathbf{\cdot}y)+x$
and the Induction Schema for any property $\mathbf{P}$
$$((\mathbf{P}(0)\wedge\forall x(\mathbf{P}(x)\rightarrow\mathbf{P}(Sx))\rightarrow\forall(x)\mathbf{P}(x)$$
We have seen that addition is defined by the primitive terms $\mathbf{0}$ and $\mathbf{S}$. It may be helpful to cite Bertrand Russell at this point (Introduction to Mathematical Philosophy, 2nd edition, pp.5-6):
The three primitive ideas in Peano’s arithmetic are:
0, number, successor.
By “successor” he means the next number in the natural order. That is
to say, the successor of 0 is 1, the successor of 1 is 2, and so on.
By “number” he means, in this connection, the class of the natural
numbers.2 He is not assuming that we know all the members of this
class, but only that we know what we mean when we say that this or
that is a number, just as we know what we mean when we say “Jones is a
man,” though we do not know all men individually.
The five primitive propositions [beware: not the axioms -T.B.] which Peano
assumes are:
(1) 0 is a number.
(2) The successor of any number is a number.
(3) No two numbers have the same successor.
(4) 0 is not the successor of any number.
(5) Any property which belongs to 0, and also to the successor of
every number which has the property, belongs to all numbers.
As the upshot of the foregoing discussion, we can say that
Addition is not the most basic operation in respect of the current foundational theory.
It is a matter of choice to start with MIP or WOP. But, with the primitive notions of number and one number succeeding the other, we have to admit that the notion of ordering is built-in. Indeed, the Induction Schema can be replaced with:
$\forall x(\mathbf{SS\ldots S}x\neq x)$
$\forall x(x\neq 0\rightarrow\exists y(\mathbf{S}y = x))$
Property $WOP$ is Well-Ordering Principle.
Property $MI$ is Mathematical Induction.
(Exercise 1) Statement $S$ is given with a Proof , hence we are given $WOP \implies S$.
We are asked to show that $MI \implies S$.
(Exercise 2) Statement $S$ is given with a Proof , hence we are given $MI \implies S$.
We are asked to show that $WOP \implies S$.
(Exercise 3) We are asked to show that $WOP \iff MI$.
While (Exercise 1) is the OP Query in the text book $3^{rd}$ Edition , we might also consider (Exercise 2) which might not be given in that text book , though (Exercise 3) is there in Newer Editions & all 3 Claims are essentially the Same Idea.
More-over , (Exercise 3) is the Best Way to state that Core Idea.
That can be seen with this intuitive thinking :
(Exercise 1) $[ (WOP \implies S) \land (WOP \iff MI) ] \implies (MI \implies S)\tag{X1}$
(Exercise 2) $[ (MI \implies S) \land (MI \iff WOP) ] \implies (WOP \implies S)\tag{X2}$
We can also see it using logical manipulation.
We are simply assuming & using (Exercise 3) here.
Proving (Exercise 3) is simple enough : Check out https://brilliant.org/wiki/the-well-ordering-principle/#equivalence-with-induction
I am skipping the Proof here , because OP says that the Proof is known & that Proof is not what the Question is about.
OP : To clarify, I know that the well-ordering principle is equivalent to weak mathematical induction; this is not what I am asking.
Proof Over-view : We show that $WOP \implies MI$ & $MI \implies WOP$ , to then conclude that $WOP \iff MI$.
Naturally , the Newer Edition is better focused on the Core Issue.
OP : Another way to state the problem above is: if I can write a valid proof for a statement using the well-ordering principle, can I write a valid proof for the same statement that uses weak mathematical induction without knowing the well-ordering principle?
Yes , we can achieve that with the Equivalences given by (X1) & (X2) , where we can use the Proof Method itself , while not invoking WOP.
OP : I am not sure how to answer this and could not find the answer online.
In general , we just have to show the Equivalence between the two.
Even though we have the Stronger Claim that $MI \iff WOP$ here , within the Context of the Exercise , we have to just show $MI \implies WOP$.
Basic Out-line : Prove WOP with MI , then use the given Proof that "$WOP \implies S$" to get the Chain "$[ MI \implies WOP ] \land [ WOP \implies S ]$" to eventually conclude that "$MI \implies S$"
Diagram & Analogy :
When WOP gives S , we can start at MI , then show WOP & then show S. Hence MI gives S.
When MI gives S , we can start at WOP , then show MI & then show S. Hence WOP gives S.
Here is one analogy to see what is going on.
P1 : When $x$ is Even number , then $x^3+5$ is not divisible by $8$.
P2 : When $x=2y$ , then $x^3+5$ is not divisible by $8$.
Both are true because "$x$ is Even" $\iff$ "$x=2y$" & we have to use that fact (Directly or not) : We can not escape that Equivalence.
Here is one non-mathematical analogy :
Prove that "X1 : US President can press the nuclear bombing button"
Prove that "X2 : Biden can press the nuclear bombing button"
Prove that "X3 : White House Boss can press the nuclear bombing button"
Every Proof of X2 will utilize the fact (Directly or not) that the Authority lies with US President who is "Currently" Equivalent to Biden.
Every Proof of X3 will utilize the fact that White House Boss is Biden who is "Currently" US President.
We can not escape that Equivalence.
Here is one last scientific analogy :
Suppose we have Chemical Ingredient X.
Suppose liquid water is necessary to convert X to Chemical Y through a well-known reaction.
Suppose ice will not react with X.
Prove that we can make Chemical Y with Chemical Ingredient X & ice , even though ice is inert & will not react with X.
Proof : Heat the ice to make liquid water. Then use that water in the well-known reaction to convert X to Y.
We have used the inert ice to convert X to Y !
That occurs because ice (WOP) is equivalent to water (MI) !
We can easily convert X (Premises) to Y (Conclusion S) with that Equivalence
More-over , we can not escape that Equivalence.
Best Answer
Well, often we consider addition as being directly built into the structure of $\mathbb{N}$ - that is, as a primitive operation. (This is the line taken with first-order Peano arithmetic, for example.) If we do that, then the whole problem doesn't arise in the first place. Similarly, if we grant "$\le$" as primitive then we have the same fix.
But let's say we don't. It turns out that we can still define the ordering without any shenanigans using just successor: $a\le b$ iff for $a\in X$ for every set $X$ such that
$b\in X$, and
whenever $S(c)\in X$ then $c\in X$.
So we can in fact define the ordering, and consequently express WOP, using just successor alone.
The above has a slight annoyance: the definition of $\le$ we build from $S$ is second-order. Can we do better?
Well, not really. The usual ordering of $\mathbb{N}$ is not first-order definable in the structure $(\mathbb{N};S)$ of the natural numbers with just successor. First-order logic is actually pretty weak a lot of the time: we also can't define $+$ from successor and order, nor can we define multiplication from addition, successor, and order. It's only once we have both addition and multiplication that we can "implement recursive definitions" in a first-order way. Basically, if we want to avoid second-order definitions we need to equip the natural numbers with a richer "primitive structure" than mere successor alone.