Almost inclusion, pseudointersections and towers

The definitions in this item work in ZF. As usual $\mathbb{N}=\omega$ is the set of von Neumann naturals (The natural numbers $\mathbb{N}$ (von Neumann)), a set $A$ is finite when $A\approx n$ for some $n\in \mathbb{N}$, and $A$ is infinite when it is not finite (Finite, countably infinite, countable, uncountable, The cardinality $\mid A\mid$ of a finite set). An infinite $A\subseteq \omega$ has $\mid A\mid ={\mathrm{\aleph }}_0$, but nothing below uses that. Write

$[\omega {]}^{\omega }:=\{A\subseteq \omega :A\text{ is infinite}\}$

for the set of infinite subsets of $\omega$; it is a set by Separation (The power set $\mathcal{P}(x)=\{z:z\subseteq x\}$) and it is nonempty, for instance $\omega \in [\omega {]}^{\omega }$. No cardinal comparison is needed to define the notions below.

Almost inclusion. For $A,B\subseteq \omega$ write

$A{\subseteq }^{\ast }B:⟺A\setminus B\text{ is finite},$

and say that $A$ is almost contained in $B$. Here $A\setminus B$ is the set difference (The difference $a\setminus b$, the symmetric difference $a\mathrm{△}b$, and the complement $X\setminus a$ relative to a set $X$) and finiteness is the notion of Finite, countably infinite, countable, uncountable. Thus $A{\subseteq }^{\ast }B$ holds exactly when $A\subseteq B\cup F$ for some finite $F\subseteq \omega$. Two sets are almost equal, written $A{=}^{\ast }B$, when $A{\subseteq }^{\ast }B$ and $B{\subseteq }^{\ast }A$; equivalently when the symmetric difference $A\mathrm{△}B$ is finite.

Pseudointersections. Let $\mathcal{F}\subseteq [\omega {]}^{\omega }$. A set $X\in [\omega {]}^{\omega }$ is a pseudointersection of $\mathcal{F}$ when $X{\subseteq }^{\ast }A$ for every $A\in \mathcal{F}$. The family $\mathcal{F}$ has the strong finite intersection property (SFIP) when $A_0\cap A_1\cap \cdots \cap A_{n-1}$ is infinite for every $n\in \mathbb{N}$ and all $A_0,\dots ,A_{n-1}\in \mathcal{F}$. Every finite subfamily of an SFIP family has infinite intersection, and a finite family of infinite sets has the SFIP exactly when its total intersection is infinite.

Towers. A tower is a family $⟨A_{\alpha }:\alpha <\kappa ⟩$, indexed by an ordinal $\kappa$, of infinite subsets of $\omega$ such that

$A_{\beta }{\supseteq }^{\ast }{A}_{\alpha }\text{whenever }\beta <\alpha <\kappa ,$

that is, the family is decreasing in the almost-inclusion order ${\supseteq }^{\ast }$, and such that the family $\{A_{\alpha }:\alpha <\kappa \}$ has no pseudointersection.

Removing repetitions. Call $\alpha <\kappa$ new when $A_{\alpha }{\mathrm{\ne }}^{\ast }{A}_{\beta }$ for every $\beta <\alpha$, let $K\subseteq \kappa$ be the set of new indices, let $\theta$ be the order type of $K$ and list $K$ increasingly as $⟨{\alpha }_{\iota }:\iota <\theta ⟩$, and put $B_{\iota }=A_{{\alpha }_{\iota }}$. Then:

• $⟨B_{\iota }:\iota <\theta ⟩$ is decreasing up to almost equality, and it is strictly decreasing: if $\iota <\eta <\theta$, then ${\alpha }_{\iota }<{\alpha }_{\eta }$ and ${\alpha }_{\eta }\in K$, so $B_{\eta }{\mathrm{\ne }}^{\ast }{B}_{\iota }$;
• every member of the original family is almost equal to some $B_{\iota }$: if $\gamma <\kappa$ and $\alpha$ is the least $\beta \le \gamma$ with $A_{\beta }{=}^{\ast }{A}_{\gamma }$, then $\alpha \in K$, since $\delta <\alpha$ with $A_{\delta }{=}^{\ast }{A}_{\alpha }$ would give $A_{\delta }{=}^{\ast }{A}_{\gamma }$ and contradict the minimality of $\alpha$;
• consequently a pseudointersection of the $B_{\iota }$ is almost contained in every $A_{\gamma }$, hence is a pseudointersection of the original family, and therefore the $B_{\iota }$ have none and $⟨B_{\iota }:\iota <\theta ⟩$ is itself a tower.

So every tower contains a strictly decreasing tower of order type $\theta \le \kappa$. The map $\iota \mapsto [B_{\iota }]$ injects $\theta$ into $\mathcal{P}(\omega )\mathrm{/}\mathrm{f}\mathrm{i}\mathrm{n}$. For the following cardinal comparison assume AC (The Axiom of Choice): choose one representative from each almost-equality class to inject the quotient into $\mathcal{P}(\omega )$, which has cardinality $2^{{\mathrm{\aleph }}_0}$ by The continuum is equinumerous with the power set of the naturals. Hence $\mid \theta \mid \le \mid \mathcal{P}(\omega )\mathrm{/}\mathrm{f}\mathrm{i}\mathrm{n}\mid \le 2^{{\mathrm{\aleph }}_0}$. This does not assert $\theta \le 2^{{\mathrm{\aleph }}_0}$ as ordinals: an ordinal may be longer than its initial cardinal.

There is a second normalization that preserves the lack of a pseudointersection. If $C\subseteq \kappa$ is cofinal, meaning that for every $\beta <\kappa$ some $\alpha \in C$ satisfies $\beta \le \alpha$, restrict the tower to the indices in $C$ in increasing order. An infinite set almost contained in every selected $A_{\alpha }$ would also be almost contained in every original $A_{\beta }$: choose such an $\alpha \ge \beta$ and use $A_{\alpha }{\subseteq }^{\ast }{A}_{\beta }$. Thus the restricted sequence is again a tower, with length the order type of $C$, which need not equal its cardinality. Removing repetitions also leaves unchanged the family of sets almost contained in every member.

The quotient $\mathcal{P}(\omega )\mathrm{/}\mathrm{f}\mathrm{i}\mathrm{n}$ and its forcing order. Almost equality is an equivalence relation on $\mathcal{P}(\omega )$, and the quotient $\mathcal{P}(\omega )\mathrm{/}\mathrm{f}\mathrm{i}\mathrm{n}$ is the Boolean algebra of subsets of $\omega$ modulo finite symmetric difference; the class of an infinite set is called positive, and every positive class contains an infinite subset of $\omega$, namely any of its members. The associated forcing order is the relation

$p\text{ is stronger than }q:⟺p{\subseteq }^{\ast }q(p,q\in [\omega {]}^{\omega }),$

which is reflexive and transitive on $[\omega {]}^{\omega }$ and is well defined on almost-equality classes: if $p{=}^{\ast }{p}^{\mathrm{\prime }}$ and $q{=}^{\ast }{q}^{\mathrm{\prime }}$ then $p{\subseteq }^{\ast }q$ exactly when $p^{\mathrm{\prime }}{\subseteq }^{\ast }{q}^{\mathrm{\prime }}$. Thus smaller infinite sets are stronger conditions, and the relation displayed by some sources as the weaker-than order, $p{\supseteq }^{\ast }q$, is this same order read in the reverse direction; the order is a partial order on classes (Partial order and partially ordered set) and not a partial order on the sets themselves, where $p{\subseteq }^{\ast }q{\subseteq }^{\ast }p$ holds for distinct but almost equal sets.

Conventions for this page. In the items below, when a family is written $⟨A_{\alpha }:\alpha <\kappa ⟩$ together with the assertion that it is decreasing, the assertion is always that $A_{\beta }{\supseteq }^{\ast }{A}_{\alpha }$ for $\beta <\alpha$, as above. An uncountable family is displayed by an ordinal enumeration; no well-order of a general family is presupposed unless the item says so.

The negation of $A{\subseteq }^{\ast }B$ says that $A\setminus B$ is infinite, and for infinite $A$ this is not the same as $B{\subseteq }^{\ast }A$: the disjoint sets $A=$ the even numbers and $B=$ the odd numbers satisfy $A\mathrm{̸}{\subseteq }^{\ast }B$ and $B\mathrm{̸}{\subseteq }^{\ast }A$. The almost-inclusion order is therefore genuinely different from inclusion, and the distinction is exactly what the diagonal constructions below exploit.

Monk states the relation ${\subseteq }^{\ast }$ and the pseudointersection property at the opening of his notes and introduces towers as decreasing families with no pseudointersection when he defines the tower number; Malliaris and Shelah present $\mathcal{P}(\omega )\mathrm{/}\mathrm{f}\mathrm{i}\mathrm{n}$ with the reverse (weaker-than) convention. A condition is a positive class; in the stronger-than convention fixed above, strengthening passes to an almost subset. Reversing the symbol used to display the order does not reverse which conditions are stronger. The conventions fixed above are the ones used on this page; no mathematical content depends on which of the two display conventions is chosen.