Halmos: Principle of induction shows only one function satisfies a recurrence relation.

Question

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$$

Answer 1

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))$.

Answer 2

Once you prove the existence of such a function u you can prove its uniqueness under these conditions using induction.

Suppose that $v$ is another function from $\omega$ to $X$ verifying $v(0)=a$ and $v(n^+)=f(v(n))$. Now let S be the set of all natural numbers on which $u$ & $v$ agree. Since $u(0)=v(0)=a$, $0\in S$. Now suppose that $n\in S$, i.e. $u(n)=v(n)$. Then $u(n^+)=f(u(n))=f(v(n))=v(n^+)$ where the second equality is by our induction hypothesis and the other two are by the conditions satified by $u$ and $v$. Therefore, by induction, $S=\omega$ and hence $u$ is unique under these conditions.

So what Halmos meant is that the recursion theorem states the "existence" and "uniqueness" of such a function. The existence part, as you can see in his book, is given as the intersection of the collection of ordered pairs in $\omega \times X$ with the desired properties and not by induction. However, the uniqueness part is proved by induction.