# How big is the lattice of all functions?

Define the lattice $(\mathcal{L},\prec)$ as the set of all function $f:\mathbb{N}\rightarrow\mathbb{N}$ satisfying $f(n)\leq f(n+1)\leq f(n)+1$, where two functions are considered equal if they differ at finitely many points, and $f\prec g$ is defined as $f(n)\leq g(n)$ with finitely many exceptions.

This lattice is large, e.g. you can construct chains and antichains of size continuum, chains of antichains of the same cardinality and so on. Although these constructions are structurally simple, defining them in a precise way gets quite complicated. Therefore I am interested into references dealing with this lattice or sublattices, making the intuitive "largeness" precise.

Background: Y. Barnea and I constructed a set of groups parametrized by elements of $\mathcal{L}$, and want a way to convince group theorists that we really have "many" groups, and don't want to waste a lot of space on constructions which yield results far inferior to what every lattice theorist would immediately see.

Edit: As every function in $\mathcal{L}$ is equivalent to either a function $f$ satisfying $f(0)=0$ or a function $f(n)=n+c$, the interesting part is the sublattice of functions satisfying $f(0)=0$. Also I always assume AC and would not mind too much about assuming CH.

• Several cardinal invariants of this lattice are the well-known cardinal characteristics of the continuum such as bounding number or the dominating number. The cardinal characteristics of the continuum are described in detail by Andreas Blass in chapter 6 in the Handbook of Set Theory. – Joseph Van Name Aug 25 '15 at 13:29
• Yes, but the bounding number measures only the tip of the lattice. If we assume $\mathfrak{c}=\aleph_1$, then I would expect that most uncountable lattices occurring in real life have bounding number $\mathfrak{c}$. But $\mathcal{L}$ looks larger, e.g. every open interval has also bounding number equal to the bounding number of the continuum (note that one has to remove the maximal element $f(n)=n$). – Jan-Christoph Schlage-Puchta Aug 25 '15 at 16:35
• If you don't have access to the book that Joseph mentions, here's an overview of the cardinal characteristics of the continuum: en.wikipedia.org/wiki/Cardinal_characteristic_of_the_continuum – Dominic van der Zypen Aug 26 '15 at 6:40
• I know about cardinal characteristics, I just don't think that they capture the size of L very well. I would guess that a more proper measurement would be something like "What is the largest ordinal embeddable into L?", or may be well quasi order in place of ordinal. – Jan-Christoph Schlage-Puchta Aug 26 '15 at 9:06
• @Jan-ChristophSchlage-Puchta It seems to me that L contains a countable dense order, and so the ordinals that embed into L are exactly the countable ordinals. – Joel David Hamkins Aug 26 '15 at 9:45

One partial answer is the following. The large lattice ${\cal P}(\omega)/fin$ (which is defined here) can be embedded into ${\cal L}$ as follows:

For $A\subseteq \omega$ define $f_A:\omega \to \omega$ by $$f_A(n) = |\{0,\ldots,n\}\cap A|$$ for all $n\in \omega$. It is not hard to verify that the map $\varphi:{\cal P}(\omega)/fin \to {\cal L}$ sending $[A]_{fin}$ to $[f_A]$ is well-defined and injective. (It is also a lattice homomorphism.)

Could it be that ${\cal L}$ is some kind of power of ${\cal P}(\omega)/fin$? I'll ask that in a separate question.

EDIT: Andreas Blass pointed out an error in the above construction, but it seems like Jan-Christoph Schlage-Puchta was able to fix the error -- see comments below.

• I'm afraid I can't verify the "not hard to verify" claim in the question. If I delete one element, say $q$, from $A$, then the value of $f_A(n)$ decreases by $1$ for all $n\geq q$. So the new and old $A$'s represent the same element of $\mathcal P(\omega)/$fin, but the new and old $f_A$'s represent different elements of $\mathcal L$. – Andreas Blass Aug 28 '15 at 7:48
• Oh - that's right... Let me see if this can be still make to work, but maybe we would need "jumps of at least 2 steps" (which are not allowed). Somehow I was convinced that ${\cal P}(\omega)/fin$ can be embedded into ${\cal L}$, but I may be mistaken – Dominic van der Zypen Aug 28 '15 at 8:36
• The construction is essentially correct: Define $f(3n)=2n$, $f(3n+2)=2n+1$, and $f(3n+1)=2n$ or $2n+1$, depending on whether $n\in A$ or not. Nice! – Jan-Christoph Schlage-Puchta Aug 29 '15 at 9:52
• That's a great fix, @Jan-ChristophSchlage-Puchta - thanks! – Dominic van der Zypen Aug 31 '15 at 6:44
• The map is not a lattice homomorphism. See the end of the answer to the separate question mentioned above: mathoverflow.net/questions/215821/…. The sets $A$ and $B$ are disjoint, so their infinum is $\emptyset$, which has a constant-on-a-tail function as its image, but $f_A\land f_B=f_B$, which is not constant on a tail. – KP Hart Oct 8 '18 at 15:00

Here are a few tricks to play with. For every $$A\subseteq\omega$$ define $$f_A$$ by $$f_A(0)=0$$, $$f_A(n+1)=f_A(n)+1$$ if $$n\in A$$, and $$f_A(n+1)=f_A(n)$$ if $$n\notin A$$. If $$A\subset^*B$$ (so $$B\setminus A$$ is infinite) then $$f_A\prec f_B$$: fix $$m$$ such that $$A\setminus B\subseteq m$$; in fact, $$f_B(n)-f_A(n)$$ will diverge to infinity. Now take a tower $$\langle T_\alpha:\alpha<\mathfrak{t}\rangle$$ such that $$T_{\alpha+1}\setminus T_\alpha$$ is always infinite. Then $$\langle f_{T_\alpha}:\alpha<\mathfrak{t}\rangle$$ is a $$\mathfrak{t}$$-chain in $$\mathcal{L}$$. One can also create a copy of the unit interval in $$\mathcal{L}$$ in this way.

If $$\mathcal{A}$$ is an almost disjoint family then we can modify it as follows: for every $$A$$ let $$X_A=\bigcup_{n\in\omega}[3^n,3^{n+1})$$. Then the set $$\{f_{X_A}:A\in\mathcal{A}\}$$ is an antichain in $$\mathcal{L}$$. To see this consider two infinite sets $$A$$ and $$B$$ with finite intersection, say $$A\cap B\subseteq m$$, and write $$g_A=f_{X_A}$$ and $$g_B=g_{X_B}$$. For every $$n$$ we have $$g_A(3^n), g_B(3^n)\le \sum_{k. Now, take $$l\ge m$$ and let $$n\le l$$ be the first member of $$(A\cup B)\setminus l$$; now if $$n\in A$$ then $$g_A(3^{n+1})=g_A(3^n)+2\cdot 3^n$$ and $$g_B(3^{n+1})=g_B(3^n)$$, so that $$g_A(3^{n+1})>g_B(3^{n+1})$$. If $$n\in B$$ then this reverses. It follows that $$g_A$$ and $$g_B$$ are $$\prec$$-incomparable.