11
$\begingroup$

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

$\endgroup$
14
$\begingroup$

Nice question! I like it very much.

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

$\endgroup$
  • 4
    $\begingroup$ I seem to recall that such a family of functions is used in Stevo Todorcevic's proof that forcing to add a Cohen real creates a Suslin tree. $\endgroup$ – Joel David Hamkins Jul 16 '15 at 12:11
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Joel David Hamkins Jul 16 '15 at 13:11
  • 4
    $\begingroup$ Nice exposition! Actually the statement and proof appear in Kunen's chapter in the Handbook of Mathematical Logic, pp 383-4. Modesty prevents from mentioning also my book Problems and Theorems in Classical Set Theory. $\endgroup$ – Péter Komjáth Jul 16 '15 at 15:23
  • 3
    $\begingroup$ This can also be done at higher successor cardinals $\kappa^+$ where the disagreements are size $<\kappa$. It's a bit more complicated. $\endgroup$ – Monroe Eskew Jul 18 '15 at 16:31
  • 3
    $\begingroup$ See Monroe's paper on many interesting generalizations of this: math.uci.edu/~meskew/forests.pdf $\endgroup$ – Ashutosh Jul 20 '15 at 17:43
1
$\begingroup$

Todorcevic' $\rho_2$ Number of Steps function and its related tree $T(\rho_2)$ define a coherent set of functions (discovered by Peng).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.