14
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 25, 2015 at 13:29
  • $\begingroup$ 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$). $\endgroup$ Aug 25, 2015 at 16:35
  • $\begingroup$ 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 $\endgroup$ Aug 26, 2015 at 6:40
  • $\begingroup$ 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. $\endgroup$ Aug 26, 2015 at 9:06
  • 2
    $\begingroup$ @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. $\endgroup$ Aug 26, 2015 at 9:45

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ 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$. $\endgroup$ Aug 28, 2015 at 7:48
  • $\begingroup$ 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 $\endgroup$ Aug 28, 2015 at 8:36
  • 4
    $\begingroup$ 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! $\endgroup$ Aug 29, 2015 at 9:52
  • $\begingroup$ That's a great fix, @Jan-ChristophSchlage-Puchta - thanks! $\endgroup$ Aug 31, 2015 at 6:44
  • $\begingroup$ 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. $\endgroup$
    – KP Hart
    Oct 8, 2018 at 15:00
2
$\begingroup$

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<n}3^k=\frac12(3^n-1)$. 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.

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