2
$\begingroup$

Define ${\cal L}$ as in this question: the set of functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $f(n)\leq f(n+1)\leq f(n)+1$, where two functions are considered equal if they differ at at most finitely many points, and $f\prec g$ is defined to mean $f(n)\leq g(n)$ for all but at most finitely many exceptions $n$.

Let ${\cal P}(\omega)/fin$ be defined as in this post. In another post, it was established that there is some kind of "natural" (not in the categorical sense) lattice embedding from ${\cal P}(\omega)/fin$ into ${\cal L}$.

My question is: Can the relationship between ${\cal P}(\omega)/fin$ and ${\cal L}$ be made more precise? Isn't ${\cal L}$ essentially ${\cal P}(\omega)/fin$ "stacked on top of itself $\omega$ times"? Or is ${\cal L}$ (a quotient of) a product of ${\cal P}(\omega)/fin$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Look at your and my second answer to the original question. Take your map from $\mathcal{P}(\omega)$ into $\mathcal{L}$ (or rather the set of functions before identifying almost equal elements). That is for $A\subseteq\omega$ define $f_A$ as in your answer: $f_A(n)=|n\cap A|$. What I showed is this: if $A\subset^*B$ then $f_B(n)-f_A(n)$ diverges to infinity. What you can also show is: if $A=^*B$ then $f_A-f_B$ is constant on a tail. Indeed, if $A\setminus m=B\setminus m$ then for $n\ge m$ we have $f_A(n)-f_B(n)=f_A(m)-f_B(m)$. On the other hand, if $A\neq^*B$ then $f_A-f_B$ is not constant on a tail: if $n\in A\setminus B$ then $f_A(n)<f_A(n+1)$ but $f_B(n)=f_B(n+1)$ and vice versa.

This shows that $A\mapsto f_A$ induces an injective map from $\mathcal{P}(\omega)/\mathit{fin}$ into $\mathcal{L}/{\equiv}$ where $f\equiv g$ means that $f-g$ is constant on a tail. The map is also onto: given $f\in\mathcal{L}$ look at $g$ defined by $g(n)=f(n)-f(0)$; then $g=f_A$, where $A=\{n:f(n+1)=f(n)+1\}$.

As shown in the other answer the map is order-preserving in the sense that $A\subset^*B$ implies that $f_B(n)-f_A(n)$ diverges to infinity.

On the other hand disjoint sets can map to comparable functions: let $A$ consist of the even numbers and let $B=\{4n+1:n\in\omega\}$. Then $f_A$ grows like $n/2$ and $f_B$ grows like $n/4$ so that $f_A(n)-f_B(n)$ will diverge to infinity.

$\endgroup$

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.