Vtyjkyuk

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, $ain A$, and $f colon Ato A$ a mapping. Then there exists a unique mapping $g: Bbb Nto 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!

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 $GcolonBbb Nto X$, given by $G(n)=g(n+1)(n)$ is an injective function as wanted.

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
arrayl
H : & X^<omega
& longrightarrow & X^<omega \
& h & longmapsto & H(h) endarray$$

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 operatornameranh$. Because $|operatornameranf_k+1| = k+1 > |operatornameranh| = k$, $n in mathbb N mid f_k+1(n) notin operatornameranh 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 operatornamedomg_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 $|operatornamedomf_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 operatornamerang_n$. This contradicts the definition of $H circ g_n(n+1)$.

b. If $i_2 < n+1$. Then $i_1,i_2 in operatornamedomg_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.