# Constructing an $\omega_1$-sequence of functions that almost extend all previous functions

I want to construct a sequence of functions $$f_\alpha: \alpha \rightarrow \omega,\ \alpha < \omega_1$$ such that for all $\alpha < \omega_1$ the following holds:

• $f_\alpha$ is injective.
• $(\forall \beta < \alpha)\ f_\beta =^* f_\alpha \upharpoonright \beta$,

i.e. the restriction $f_\alpha \upharpoonright \beta$ agrees with $f_\beta$ in all but finitely many places.

I feel this should be possible for similar reasons we can construct a family of continuum many almost disjoint subsets of $\omega$.

Sure, we can do this. We'll also arrange that $\text{ran}(f_\alpha)$ is coinfinite. That will make the successor steps easy, since there is always another point available. The difficulty is what to do at limits. Suppose we have $f_\alpha$ for $\alpha<\lambda$, where $\lambda$ is a countable limit ordinal. We want to define the function $f_\lambda$. In order to do this, pick an increasing cofinal sequence $\alpha_0<\alpha_1<\alpha_2<\cdots<\lambda$ with $\sup_n\alpha_n=\lambda$. We shall define $f_\lambda$ in blocks. First, let $f_\lambda$ agree with $f_{\alpha_0}$ up to $\alpha_0$. Next, on the interval $[\alpha_0,\alpha_1)$, we make $f_\lambda$ agree with $f_{\alpha_1}$, except modified so that it is still injective in combination with what we already did below $\alpha_0$. This modification will require only at most finitely many changes to $f_{\alpha_1}\upharpoonright[\alpha_0,\alpha_1)$, since $f_{\alpha_0}$ and $f_{\alpha_1}$ agree except on a finite set. Continuing, we define $f_\lambda$ on the interval $[\alpha_n,\alpha_{n+1})$ to agree with $f_{\alpha_{n+1}}$, except fixed up again to be injective, which will require only finitely many changes. Ultimately, in this way we'll get an injective function $f_\lambda:\lambda\to\omega$. For any $\alpha<\lambda$, we have $\alpha<\alpha_n$ for some $n$, and consequently $f_\lambda\upharpoonright\alpha$ was obtained from finite modifications of the $f_{\alpha_k}$'s for $k<n$, each of which had only finite difference from $f_\alpha$ up to $\alpha$. And so our function $f_\lambda$ differs from $f_\alpha$ on $\alpha$ only at most finitely. Lastly, to ensure that $f_\lambda$ has coinfinite range, we may if necessary simply change the values on the ordinals $\alpha_n$, since this will involve only finitely many changes below any given $\alpha<\lambda$. Thus, we have constructed the function $f_\lambda$ with the desired properties, the construction may proceed up to $\omega_1$.
• It's not difficult to see that the coinfinite range requirement is necessary, because if some $f_\alpha$ has cofinite range in $\omega$, then you will run out of room at some $f_{\alpha+k}$. – Joel David Hamkins Jul 16 '15 at 13:11
• This can also be done at higher successor cardinals $\kappa^+$ where the disagreements are size $<\kappa$. It's a bit more complicated. – Monroe Eskew Jul 18 '15 at 16:31
Todorcevic' $\rho_2$ Number of Steps function and its related tree $T(\rho_2)$ define a coherent set of functions (discovered by Peng).