Let $\omega^\omega$ denote the collection of all functions $f:\omega\to\omega$. For $f,g\in\omega$ we say $f\simeq g$ if and only if $\exists N \in \omega$ such that $f(n) = g(n)$ for all $n\geq N$.

Often, the symbol $(fin)$ is used for the equivalence relation $\simeq$. For $[f], [g] \in \omega^\omega/(fin)$ we define $[f]\leq^* [g]$ if and only if $\exists N\in\omega$ such that $f(n)\leq g(n)$ for all $n\in \omega$ with $n\geq N$. Clearly, $\leq^*$ is well-defined and $(\omega^\omega/(fin), \leq^*)$ is a poset.

What is the order dimension of $(\omega^\omega/(fin), \leq^*)$?


$\newcommand\Fin{\text{Fin}}$Theorem. The order dimension of $\langle\omega^\omega/\Fin,\leq^*\rangle$ is precisely the continuum.

Proof. It is easy to see that the dimension is at most the continuum, since the space itself has size continuum. (One must argue that for any instance of incomparability, we may find two linear orders extending $\leq^*$ placing the two individuals in opposite order, so that the intersection witnesses that instance of incomparability.)

Let me now argue that the dimension is at least continuum. For this, I build a continuum-sized version of the example of dimension four described on the wikipedia page to which you link. Probably it would help to be familiar with that finite example to understand how the one I present here works, since the underlying idea is the same.

Specifically, we first construct inside $\langle\omega^\omega/\Fin,\leq^*\rangle$ functions $a_s,b_s\in\omega^\omega$ indexed by $s\in 2^\omega$, such that $s\neq t\to a_s\perp a_t,\ b_s\perp b_t$ and also $a_s\perp b_s$ and $a_s\leq^*b_t\iff s\neq t$. So these functions are two antichains, with $a_s$ below all the $b_t$ except for $b_s$.

To construct this situation, let $A_s\subset\mathbb{N}$ be an almost disjoint family for $s\in 2^\omega$. Such a family can be constructed by labeling the nodes of the tree $2^{<\omega}$ with distinct natural numbers, and letting $A_s$ be the labels on the branch $s$. It follows that each $A_s$ is infinite and $s\neq t\to A_s\cap A_t$ is finite. Now, let $a_s$ be the characteristic function of $A_s$, that is, $a_s(n)=1$ if $n\in A_s$ and otherwise $0$. These functions are pairwise incomparable. Let $b_s$ be the characteristic function of the complement of $A_s$. These functions are also pairwise incomparable. Because the family is almost disjoint, it follows that $a_s\leq^* b_t$ whenever $s\neq t$, but $a_s\perp b_s$. So the family is as desired.

Now suppose that we have a family of linear orders whose intersection is $\leq^*$. For any particular $s\in 2^\omega$, then since $a_s$ and $b_s$ are incomparable by $\leq^*$, there must be a linear order $<$ in the family for which $b_s<a_s$. But now, since $a_s\leq^*b_t$ and $a_t\leq^* b_s$ for all $t$, it follows that this order $<$ works only for this particular $s\in 2^\omega$.

So the family of linear orders must have size at least continuum. QED


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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