3
$\begingroup$

If ${\cal S}$ is a collection of functions $f:\omega\to\omega$ we say that ${\cal S}$ is meetable if there is a "global function" $g:\omega\to \omega$ such that for every $f\in {\cal S}$ there is $n\in\omega$ such that $g(n) = f(n)$.

Let ${\cal S}^{\pm 1}$ denote collection of functions $f:\omega\to\omega$ such that $|f(n) - f(n+1)| = 1$ for all $n\in\omega$ and for $k\in\omega \setminus \{0\}$, let ${\cal S}^{\pm 1}_{\leq k} = \{ f\in {\cal S}^{\pm 1}: f(0) \leq k\}$.

Is ${\cal S}^{\pm 1}$ meetable? If not, is ${\cal S}^{\pm 1}_{\leq k}$ meetable for all $k\in\omega\setminus\{0\}$?

(User Wojowu pointed out in a comment below that ${\cal S}^{\pm 1}_{\leq 1}$ is meetable.)

$\endgroup$
3
  • $\begingroup$ ${\cal S}^{\pm 1}_{01}$ is met by the constant $1$ function. $\endgroup$
    – Wojowu
    Jan 24, 2020 at 10:35
  • $\begingroup$ Right - thanks! $\endgroup$ Jan 24, 2020 at 15:18
  • $\begingroup$ Am including Wojowu's remark in the post and editing it slightly $\endgroup$ Jan 24, 2020 at 15:53

1 Answer 1

5
$\begingroup$

$\newcommand\om{\omega}$ The set $S:={\cal S}^{\pm 1}$ is meetable by any function $g$ of the following form:

Let $l_0,l_1,\dots$ be odd numbers in $\om=\{0,1,\dots\}$ such that $l_j/n_j\to\infty$ (as $j\to\infty$), where $n_0=-1$ and $n_{j+1}=n_j+l_j$ for $j\in\om$. (E.g., take $l_j=1+j!$ for $j\ge2$.) For each $j\in\om$ and all $n\in\om$ such that $n_j<n\le n_{j+1}$, let $g(n)=n_{j+1}-n$.

Indeed, take any $f\in S$ and suppose that $f$ is not met by $g$. Since $l_j/n_j\to\infty$, we have $f(n_j+1)\le f(0)+n_j+1\le l_j-1=g(n_j+1)$ for all large enough $j$. For all such $j$, there exists $$m_j:=\max\{n\in\{n_j+1,\dots,n_{j+1}\}\colon f(n)\le g(n)\}.$$ Since $f$ is not met by $g$ and $|f(n+1)-f(n)|=1$, we see that $f(m_j)=g(m_j)-1=n_{j+1}-m_j-1$, whence $n_{j+1}-1=f(m_j)+m_j=f(0)\text{ mod }2$ for all large enough $j$. This is a contradiction, because the $l_j$'s are all odd and hence the $n_j$'s alternate $\text{ mod }2$.


Here are the list plots $\{(n,g(n))\colon n\in\{1,\dots,n_5\}\}$ (blue) for $l_j\equiv1+j!$ and $\{(n,f(n))\colon n\in\{1,\dots,n_5\}\}$ (red) for a "random" $f\in S$, showing how $g$ eventually "catches/meets" $f$ -- catches only by the last in the picture (negatively sloped) dotted blue line segment ($f$ was able to get through the previous blue barrier):

enter image description here

$\endgroup$
1
  • $\begingroup$ Amazing construction - thanks Iosif! $\endgroup$ Jan 24, 2020 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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