Under what minimal conditions must the range of a definable, injective function $\omega^{<\omega}\to\Bbb N$ have positive density in the integers?

I'm very inexperienced in such matters but it would appear that even if some countable set bijects into $\Bbb N$, the same set might by some other function only range over into $\{2^n:n\in\Bbb N\}$, in which case its image would not be guaranteed to have positive density in the integers.

So it appears on the fact of it that some further conditions would need to be implied.

But I don't know if this would contradict some countability argument. Perhaps by the nature of $\omega^{<\omega}$, if the length of sequences is truly unlimited, no exponential map exists which could accommodate an unlimited number of limit points and still be countable.


closed as unclear what you're asking by Andrés E. Caicedo, José Carlos Santos, Lord Shark the Unknown, hardmath, Shailesh Aug 11 '18 at 4:46

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ I don't know of any natural such conditions. Certainly any countable set behaves the same as any other countable set in this context; e.g. fixing a bijection $b$ from $\omega^{<\omega}$ to $\mathbb{N}$ the map $\sigma\mapsto 2^{b(\sigma)}$ is an injection from $\omega^{<\omega}$ to $\mathbb{N}$ whose range has density zero. $\endgroup$ – Noah Schweber Aug 10 '18 at 16:08
  • $\begingroup$ @NoahSchweber Thank-you. I should perhaps have suggested types of conditions, such as e.g. the condition: if we situate $\Bbb N$ in the 2-adic space, every limit ordinal in $\omega^{<\omega}$ is associated with the same limit point in $\Bbb Z_2\setminus\Bbb Z$. $\endgroup$ – samerivertwice Aug 10 '18 at 16:15
  • $\begingroup$ Perhaps this Question arose in connection with a context in which it would be more natural to pose an assumption that gives you positive density, but Noah's construction shows that the context would need to restrict the possible functions considerably. Some use of big-Oh notation comes to mind, but I would be guessing that it applies to your purpose. $\endgroup$ – hardmath Aug 11 '18 at 1:32
  • $\begingroup$ @hardmath my thoughts in these circumstances are generally that the answer is a most useful one and I hope others are not deprived of it. The purpose of this question is to help me think about whether this has positive density: mathoverflow.net/questions/301110 and to describe why. $\endgroup$ – samerivertwice Aug 11 '18 at 10:04

(1). There exists a bijection $g: \omega^{<\omega}\to \Bbb N.$ If $h:\Bbb N\to \Bbb N$ is any injective function then the composite function $hg:\omega^{<\omega}\to \Bbb N$ is injective . Examples: (i). $h=id_{\Bbb N}.$...(ii). $h(n)=2n$ for all $n\in \Bbb N.$...(iii). $h(n)=2^n$ for all $n\in \Bbb N$. ... (iv). Let $S$ be any infinite subset of $\Bbb N$ and let $h:\Bbb N\to S$ be the (unique) order-isomorphism.

(2). For any $S\subset \Bbb N$ and for any $n\in \Bbb N$ let $|n\cap S|$ denote the number of members of $S$ that are less than $n.$

We can construct $S\subset \Bbb N$ such that for every $r\in [0,1]$ there exists a strictly increasing $j_r:\Bbb N\to \Bbb N$ such that $\lim_{n\to \infty} \frac {| j_r(n)\cap S|}{j_r(n)}=r.$

We first construct $S$ such that this holds for every $r\in \Bbb Q\cap [0,1].$ Then for $r\in 0,1] \backslash \Bbb Q$ take a sequence $(q_i)_{i\in \Bbb N}$ of rationals in $[0,1]$ converging to $r.$

Now let $j_r(1)=j_{(q_1)}(m)$ for some $m$ such that $\left|q_1-\frac {|j_r(1)\cap S|}{j_r(1)}\right| <2^{-1}.$

And take $j_r(n+1)= j_{(q_{n+1})}(m)$ for some $m$ such that $j_r(n+1)>j_r(n)$ and such that $\left|q_{n+1}-\frac {|j_r(n+1)\cap S|}{j_r(n+1)}\right|<2^{-n}.$

Then $\lim_{n\to \infty} \frac {|j_r(n)\cap S|}{j_r(n)}=r. $

  • $\begingroup$ Thank-you, this is fabulous. You must have a sixth sense (or maybe the 2-adic convergence comment guided you?) as it could not be closer to what I was looking for! $\endgroup$ – samerivertwice Aug 11 '18 at 14:53
  • $\begingroup$ You weren't clear about "limits" so I wasn't at all sure what you were looking for. I thought it might turn out to be something else entirely. $\endgroup$ – DanielWainfleet Aug 11 '18 at 21:29

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