Basics on towers on the natural numbers

For $A, B \subseteq \omega$ we write $A \subseteq^* B$ if $A\setminus B$ is finite, and we write $A\simeq^* B$ if $A\subseteq^* B$ and $B\subseteq^* A$.

A tower is a collection ${\cal T}$ of co-infinite subsets of $\omega$ such that for all $A\neq B\in {\cal T}$ we have $A\not\simeq^*B$ and either $A\subseteq^* B$ or $B \subseteq^* A$. ( $A\subseteq \omega$ is co-infinite if $\omega\setminus A$ is infinite.)

If ${\cal S}, {\cal T}$ are towers, we say that ${\cal S}\leq_t {\cal T}$ if $A\in {\cal S}$ and $B\in{\cal T}$ with $B\subseteq^* A$ jointly imply that $B\in{\cal S}$. (In other words, this means that ${\cal S}$ is a down-set or initial segment of ${\cal T}$ with respect to $\subseteq^*$). It is easy to prove that $\leq_t$ is a partial order on the collection of all towers on $\omega$.

The remainder of this post is about maximal towers with respect to $\leq_t$. The proof of the following lemma is routine.

Lemma 1. If ${\frak T}$ is a collection of towers, such that for all ${\cal S}, {\cal T}\in {\frak T}$ we have either ${\cal S}\leq_t {\cal T}$ or ${\cal T}\leq_t {\cal S}$, then

1. $\bigcup {\frak T}$ is a tower, and
2. ${\cal T}\leq_t \bigcup{\frak T}$ for all ${\cal T}\in{\frak T}$.

Corollary 1. Zorn’s Lemma and Lemma 1 imply that there is a tower in $\omega$ that is maximal with respect to $\leq_t$.

Lemma 2. If ${\cal A}$ is a countable tower then ${\cal A}$ is not maximal.

Proof. Let $(A_n)_{n\in\omega}$ be a sequence of co-infinite subsets of $\omega$ such that for all $n\in\omega$ we have $A_n \subseteq^* A_{n+1}$ . We want to show there is $A\subseteq \omega$ co-infinite with $A_n\subseteq^* A$ for all $n\in\omega$.

Step 1. If $k\in \omega$, then $\bigcup_{i=0}^k A_i$ is co-infinite.

Step 2. There is $f:\omega\to\omega$ strictly increasing such that $f(n) \in \omega\setminus\big(\bigcup_{i=0}^n A_i\big)$ for all $n\in\omega$.

Step 3. Set $A = \bigcup_{k\in\omega}\big(A_k\setminus [0,\ldots,f(k)]\big).$

Then it follows that

1: $A_k\subseteq^* A$ for all $k\in \omega$ since $(A_k\setminus A) \subseteq [0,\ldots,f(k)]$ which is a finite set.

2: $A$ is co-infinite, since for all $k\in \omega$ we have $f(k)\notin A$, so $A\cap \{f(k):k\in\omega\}=\emptyset$, and since $f$ is strictly increasing we have $\{f(k):k\in\omega\}$ is infinite, so $A$ is co-infinite.

Letting ${\cal A} =\{A_n:n\in\omega\}$ we get that ${\cal A}' = {\cal A} \cup\{A\}$ is a tower with ${\cal A} \leq_t {\cal A}'$ but ${\cal A}' \not\leq_t {\cal A}$, so the countable tower ${\cal A}$ is not maximal. $\Box$ 