Induction is often used not only to prove things but also to define things.
Suppose, to be specific, that $f$ is a function from a set $X$ into the same set
$X$, and suppose that $a$ is an element of $X$. It seems natural to try to define
an infinite sequence $\{u(n)\}$ of elements of $X$ (that is, a function $u$ from $\omega \to X$) in some such way as this: write $u(0) = a, u(1) = f(u(0)), u(2) = f(u(1))$, and so on. If the would-be definer were pressed to explain the "and so on," he might lean on induction. What it all means, he might say, is that we define $u(0)$ as $a$, and then, inductively, we define $u(n^{+})$ as $f(u(n))$ for every $n$. This may sound plausible, but, as justification for an existential assertion, it is insufficient. The principle of mathematical induction does indeed prove, easily, that there can be at most one function satisfying all the stated conditions, but it does not establish the existence of such a function.
(Book: Halmos, Paul. Naive Set Theory, Section 12, The Peano Axioms, p.48.)
What might Halmos mean by the line in bold? What is the proof in question? I feel like I am missing something obvious.
Context:
The set of natural numbers is denoted $\omega$ here.
The successor of $n$ is $n^{+}$ here.
Principle of induction is expressed set-theoretically as $$ S\subseteq \omega \wedge 0\in S \wedge (n\in S \Rightarrow n^{+} \in S) \Rightarrow S = \omega$$
Best Answer
Suppose two such functions $u_1$ and $u_2$ exist and they’re not equal. Then the set $A=\{ n \in \Bbb N \mid u_1(n) \neq u_2(n) \}$ is a non-empty set of natural numbers, so it must have a least element. What can that least element be?
It can’t be $0$ because we’re given that $u_1(0)=a=u_2(0)$. Therefore, the least element of $A$ must take the form $m+1$ for some $m$.
But that’s not possible either. Since $m+1$ is the least element where $u_1$ and $u_2$ differ, $m \lt m+1$ tells us that $u_1(m)=u_2(m)$. But then $u_1(m+1)=f(u_1(m))=f(u_2(m))=u_2(m+1)$ and, contrary to our assumption, $m+1 \notin A$ after all.
This contradiction shows that $A$ can’t have a least element, so it must be empty; in other words, $\forall n \in \Bbb N ~ (u_1(n)=u_2(n))$.