# What is the smallest cardinality of a maximal ultrafamily of infinite subsets of $\omega$?

A family $$\mathcal U$$ of infinite subsets of $$\omega$$ is called an ultrafamily if for any sets $$U,V\in\mathcal U$$ one of the sets $$U\setminus V$$, $$U\cap V$$ or $$V\setminus U$$ is finite.

By the Kuratowski-Zorn Lemma, each ultrafamily $$\mathcal U\subseteq [\omega]^\omega$$ can be enlarged to a maximal ultrafamily.

Let $$\mathfrak{uf}$$ be the smallest cardinality of a maximal ultrafamily. It can be shown that $$\max\{\mathfrak s,\mathfrak a\}\le\mathfrak {uf}\le\mathfrak c,$$ where $$\mathfrak a$$ is the smallest cardinality of a maximal infinite almost disjoint family of infinite sets in $$\omega$$ and $$\mathfrak s$$ is the smallest cardinality of a family $$\mathcal S\subseteq[\omega]^\omega$$ such that for every $$X\in[\omega]^\omega$$ there exists $$S\in\mathcal S$$ such that the sets $$X\cap S$$ and $$X\setminus S$$ are infinite.

Problem 1. Find non-trivial upper (and lower) bounds for the cardinal $$\mathfrak{uf}$$.

Problem 2. Is $$\mathfrak{uf}$$ equal to any known cardinal characteristic of the continuum?

Problem 3. Is $$\mathfrak{uf}<\mathfrak c$$ consistent?

Added in Edit. The diagrams of known small uncountable cardinals in the surveys of Blass and Vaughan do not show up any cardinal characteristic between $$\max\{\mathfrak s,\mathfrak a\}$$ and $$\mathfrak c$$. So the answer to Problem 2 is rather no'' unless $$\mathfrak{uf}=\mathfrak c$$ (which would be a bit surprising).

• A piece of heuristics: this statement has a very similar flavour to Booth's lemma (that is equivalent to Martin's axiom), so very likely $uf = c$ under MA and probably it is consistent that there is a strict inequality. – Tomasz Kania Apr 15 '20 at 15:38
• @TomekKania That $\mathfrak{uf}=\mathfrak{c}$ under MA follows from the inequalities in the question plus the fact that MA implies $\mathfrak{s}=\mathfrak{c}$. – Andreas Blass Apr 15 '20 at 16:54

To my surprise, I found that this my new'' cardinal $$\mathfrak{uf}$$ is equal to $$\mathfrak c$$.

Theorem. $$\mathfrak{uf}=\mathfrak{c}$$.

Proof. Fix any maximal ultrafamily $$\mathcal U\subseteq[\omega]^{\omega}$$. For two sets $$A,B$$ we write $$A\subset^* B$$ if $$A\setminus B$$ is finite but $$B\setminus A$$ is infinite.

A subfamily $$\mathcal L$$ will be called

$$\bullet$$ linearly ordered if for any distinct sets $$A,B\in\mathcal L$$ we have either $$A\subset^* B$$ or $$B\subset^* A$$;

$$\bullet$$ densely linearly ordered if for any distinct sets $$A,B\in\mathcal L$$ with $$A\subset^* B$$ there exists a set $$C\in\mathcal L$$ such that $$A\subset^* C\subset^* B$$.

Claim 1. If $$\mathcal U$$ contains a set $$U\in\mathcal U$$ such that the family $${\downarrow}U=\{V\in\mathcal U:V\subset^* U\}$$ is linearly ordered, then $${\downarrow}U$$ is densely linearly ordered.

Proof. Assuming that $${\downarrow}U$$ is not densely linearly ordered, we can find two sets $$A,B\in{\downarrow}U$$ such that $$A\subset^* B$$ and the set $$\{C\in\mathcal U:A\subset^* C\subset^* B\}$$ is empty. Taking into account that $$B\setminus A\subset^* U$$ and the family $${\downarrow}U$$ is linearly ordered, we conclude that $$B\setminus A\notin\mathcal U$$. By the maximality of $$\mathcal U$$, there exists a set $$W\in\mathcal U$$ such that the sets $$(B\setminus A)\cap W$$, $$(B\setminus A)\setminus W$$, $$W\setminus(B\setminus A)$$ are infinite. Then also the sets $$B\cap W$$, $$B\setminus W$$ are infinite. Taking into account that $$\mathcal U$$ is an ultrafamily, we conclude that $$W\subseteq^* B\subset^* U$$ and hence $$W\in{\downarrow}U$$. Now the choice of the sets $$A,B$$ guarantees that $$W\subseteq^*A$$ and then $$(B\setminus A)\cap W$$ is finite, which is a desired contradiction. $$\quad\square$$

Claim 2. If $$\mathcal U$$ contains a set $$U\in\mathcal U$$ such that the family $${\downarrow}U=\{V\in\mathcal U:V\subset^* U\}$$ is linearly ordered, then $$|\mathcal U|=|{\downarrow}U|=\mathfrak c$$.

Proof. By Claim 1, the family $${\downarrow}U$$ is densely linearly ordered. Consider the countable set $$\mathbb Q_2=\{\frac{k}{2^n}:n\in\omega,\;0\le k\le 2^n\}$$ of binary rational numbers in the unit interval $$[0,1]$$. Using the density of the linear order on $$\mathcal L$$, we can inductively construct a subfamily $$\{L_q\}_{q\in\mathbb Q_2}\subseteq\mathcal L$$ such that for any rational numbers $$r in $$\mathbb Q_2$$ we have $$L_r\subset^* L_q$$.

To see that $$|{\downarrow}U|=\mathfrak c$$, it remains to prove the following

Claim 3. For every $$r\in[0,1]\setminus \mathbb Q_2$$ there exists a set $$L_r\in\mathcal U$$ such that $$L_p\subset^* L_r\subset^* L_q$$ for every rational numbers $$p,q\in\mathbb Q_2$$ with $$p.

Proof. To derive a contradiction, assume that the maximal ultrafamily $$\mathcal U$$ does not contain such set $$L_r$$.

Since the poset $$\mathcal P(\omega)/\mathrm{Fin}$$ contains no $$(\omega,\omega)$$-gaps, there exists a set $$\tilde L_r\subseteq \omega$$ such that $$L_p\subset^* \tilde L_r\subset^* L_q$$ for any $$p,q\in\mathbb Q_2$$ with $$p. By our assumption, $$\tilde L_r\notin\mathcal U$$.

By the maximality of $$\mathcal U$$ we can find a set $$L_r\in\mathcal U$$ such that the sets $$\tilde L_r\cap L_r$$, $$\tilde L_r\setminus L_r$$ and $$L_r\setminus \tilde L_r$$ are infinite. The infiniteness of the intersections $$\tilde L_r\cap L_r$$ and $$\tilde L_r\setminus L_r$$ implies that for any $$q\in\mathbb Q_2$$ with $$r the intersections $$L_q\cap L_r$$ and $$L_q\setminus L_r$$ are infinite. Taking that $$\mathcal U$$ is an ultrafamily, we conclude that $$L_r\subseteq^* L_q\subset^* U$$ and hence $$L_r\in{\downarrow}U$$. For every $$p\in\mathbb Q_2$$ with $$p the infiniteness of the set $$L_r\setminus \tilde L_r$$ and the almost inclusion $$L_p\subset^* \tilde L_r$$ implies the infiniteness of the set $$L_r\setminus L_p$$. Since the family $${\downarrow}U$$ is linearly ordered, we conclude that $$L_p\subseteq^* L_r$$. Therefore, we proved that $$L_p\subset^* L_r\subseteq^* L_q$$ for any rational numbers $$p,q\in\mathbb Q_2$$ with $$p. But the existence of the set $$L_r$$ contradicts our assumption. $$\quad\square$$

So, Claims 3 and 2 have been proved. $$\quad\square$$

Claim 2 reduced the proof of the theorem to the case when for every $$U\in\mathcal U$$ the family $${\downarrow}U$$ is not linearly ordered and hence contains two sets $$U_0,U_1$$ such that $$U_0\cap U_1$$ is finite. In this case we can inductively construct a family of sets $$\{U_s\}_{s\in 2^{<\omega}}\subseteq\mathcal U$$ indexed by the elements of the binary tree $$2^{<\omega}=\bigcup_{n\in\omega}2^n$$ such that $$\mbox{U_{s\hat{\;}0}\cup U_{s\hat{\;}1}\subseteq^* U_s and U_{s\hat{\;}0}\cap U_{s\hat{\;}1}=^*\emptyset for any binary sequence s\in 2^{<\omega}}.$$

Claim 4. For every $$s\in 2^\omega$$ there exists a set $$U_s\in\mathcal U$$ such that $$U_s\subseteq^* U_{s{\restriction}n}$$ for every $$n\in\omega$$.

Proof. To derive a contradicion, assume that for some $$s\in 2^\omega$$ the sequence $$(U_{s{\restriction}n})_{n\in\omega}$$ has no pseudointersection in $$\mathcal U$$. Choose any infinite pseudointersection $$\tilde U_s$$ of the sequence $$(U_{s{\restriction}n})_{n\in\omega}$$. By our assumption, $$\tilde U_s\notin\mathcal U$$ and by the maximality of the ultrafamily $$\mathcal U$$, there exists a set $$U_s\in\mathcal U$$ such that the sets $$U_s\cap\tilde U_s$$, $$U_s\setminus\tilde U_s$$ and $$\tilde U_s\setminus U_s$$ are infinite. Then for every $$n\in\omega$$ the sets $$U_{s{\restriction}n}\cap\tilde U_s$$ and $$U_{s{\restriction}n}\setminus U_s$$ are infinite. Taking into account that $$\mathcal U$$ is an ultrafamily, we conclude that $$U_s\subseteq^* U_{s{\restriction}n}$$ for every $$n\in\omega$$, which contradicts our assumption. $$\quad\square$$

It is easy to see that the family $$(U_s)_{s\in 2^\omega}$$ given by Claim 4 is almost disjoint and hence $$|\mathcal U|\ge|\{U_s\}_{s\in 2^\omega}|=|2^\omega|=\mathfrak c$$. $$\quad\square$$.