Which version of Recursion Theorem should I use to justify this construction of $f:\mathbb N \to X$?

Question

Suppose $X$ is infinite and $f_n: \{1,\cdots,n\} \to X$ is injective for all $n \in \mathbb N$.

We define an injective mapping $f:\mathbb N \to X$ by recursive construction as follows: $$f(n)=f_{n}(i)$$ where $$i = \min \{t \in \mathbb N \mid f_{n}(t) \notin \{f(1),\cdots,f(n-1)\} \}$$

In other words, we take $f(n)$ to be $f_n(i)$, for the least $i$ such that $f_n(i)$ has not previously appeared as a value of $f(n)$.

---

This question arose when I tried to define a countably infinite subset of $X$. While I'm sure that this construction is justified by some version of Recursion Theorem, I only know the most primitive version, which is stated as:

Let $A$ be a set, $a\in A$, and $f \colon A\to A$ a mapping. Then there exists a unique mapping $g: \Bbb N\to A$ such that

1. $g(0)=a$
2. $g(n+1)=f \circ g(n)$

It seems that this basic version can not help me. Please give me some hints!

Answer 1

The point here is that $A$ can be practically any set. And it is $X^{<\omega}$, all the finite sequences from $X$. We then define $f(a)$ to be the following function: if $a$ is a sequence of length $k$ (namely, then domain of $a$ is $k$), then $f(a)$ is the sequence of length $k+1$ where we add the first element of $X$ appearing in the range of $f_{k+1}$ and not already appearing in $a$ itself.

Now define $g$ as obtained by the starting condition $g(0)=\varnothing$ (easily $g(1)=f_1$, by the way). By induction we can prove that $g(n)\subseteq g(n+1)$ and $g(n)$ is also injective. Therefore $G\colon\Bbb N\to X$, given by $G(n)=g(n+1)(n)$ is an injective function as wanted.

Answer 2

I re-formulate Asaf Karagila's sketch into a proof in detail. The motivation for this conduct is that I would like to truly understand every tiny aspect of Asaf Karagila's ideas. All credits are given to Asaf Karagila.

---

Let $\Bbb N =\{1,2,3,\cdots\}$ be the set of natural numbers and $I_n = \{1,\cdots,n\}$.

Let $X^{<\omega} = \{h: I_k \to X \mid k \in \Bbb N\}$ be the set of all finite sequences from $X$. Consider

$$\begin {array}{l|rcl} H : & X^{<\omega} & \longrightarrow & X^{<\omega} \\ & h & \longmapsto & H(h) \end{array}$$

where $h: I_k \to X$.

$H(h):I_{k+1} \to X$ is defined by $${H(h)\restriction}_{I_k} = h \text{ and } H(h)(k+1)=f_{k+1}(t)$$ where $t = \min \{n \in \mathbb N \mid f_{k+1}(n) \notin \operatorname{ran}h\}$. Because $|\operatorname{ran}f_{k+1}| = k+1 > |\operatorname{ran}h| = k$, $\{n \in \mathbb N \mid f_{k+1}(n) \notin \operatorname{ran}h\} \neq \emptyset$ and consequently such $t$ does exists.

By Recursion Theorem, there exists a unique mapping $g:\Bbb N \to X^{<\omega}$ such that $g_1=f_1$ and $g_{n+1}=H \circ g_n$.

1. $g_n \subseteq g_{n+1}$

By definition, $g_{n+1} = H \circ g_n$, then $g_{n+1}(i)=g_n(i)$ for all $i \in \operatorname{dom}g_n$. Hence $g_n \subseteq g_{n+1}$.

2. $g_n$ is injective

We prove this statement by induction on $n$. It's clear that $g_1=f_1$ is injective since $|\operatorname{dom}f_1|=1$. Assume that $g_n$ is injective for $n=k$.

Assume the contrary that $g_{n+1}$ is not injective, then $g_{n+1}(i_1)=g_{n+1}(i_2)$ for some $i_1 < i_2 \le n+1$ or equivalently $H \circ g_n(i_1) = H \circ g_n(i_2)$ for some $i_1 < i_2 \le n+1$.

a. If $i_2 = n+1$. Then $H \circ g_n(i_2)=H \circ g_n(i_1) =g_n(i_1)$. Thus $H \circ g_n(n+1)=H \circ g_n(i_2) =g_n(i_1) \in \operatorname{ran}g_n$. This contradicts the definition of $H \circ g_n(n+1)$.

b. If $i_2 < n+1$. Then $i_1,i_2 \in \operatorname{dom}g_n$, then $H \circ g_n(i_1) = H \circ g_n(i_2)$ $\implies g_n(i_1)=g_n(i_2)$. This contradicts the inductive hypothesis that $g_n$ is injective.

Hence $g_{n+1}$ is injective.

We now define the required mapping $G:\Bbb N \to X$ by $G_n=g_n(n)$.

1. $G$ is injective

Assume the contrary that $G$ is not injective. Then there exists $n_1 < n_2$ such that $G_{n_1} = G_{n_2}$, thus $g_{n_1}(n_1) = g_{n_2}(n_2)$.

$g_{n_1} \subseteq g_{n_1+1} \subseteq g_{n_1+2} \subseteq \cdots \subseteq g_{n_2} \implies g_{n_1} \subseteq g_{n_2}$. It follows that $g_{n_1}(n_1)=g_{n_2}(n_1) \neq g_{n_2}(n_2)$ since $g_{n_2}$ is injective. This contradicts the fact that $g_{n_1}(n_1) = g_{n_2}(n_2)$.

Hence $G$ is injective.