Let $[\omega]^{\omega}$ be the set of all infinite subsets of $\omega$, the first countable ordinal (the set of the natural numbers).

  • We say that $\mathcal A\subset [\omega]^{\omega}$ is open if for all $A, B \in [\omega]^{\omega}$ then if $A\subset^*B\in \mathcal A$ then $A\in \mathcal A$.
  • We say that $\mathcal D\subset [\omega]^{\omega}$ is dense if for all $A \in [\omega]^\omega$ there exists $B \in \mathcal D$ such that $B\subset^*A$.

It's possible to show that these open sets define a topology on $[\omega]^\omega$ and that in this topology, the dense subsets are what we defined above.

Let $\mathfrak h$ be the first cardinal that there exists a colection $\mathscr A$ of dense open subsets of $[\omega]^\omega$ of cardinality $\mathfrak h$ such that $\bigcap \mathscr A=\emptyset$. It's possible to show that $\omega<\mathfrak h\leq \mathfrak c$, that $\mathfrak h$ is regular and it's consistent that $\mathfrak h<\mathfrak c$.

We may prove the following theorem, that is called the Base Matrix Tree Lemma:

There exists $\mathcal T\subset [\omega]^\omega$ such that:

  1. $\supset^*$ is a tree order on $\mathcal T$. The first level of $\mathcal T$ is $\{\omega\}$. The height of $\mathcal T$ is $\mathfrak h$.
  2. Every node of $\mathcal T$ has exactly $\mathfrak c$ successors.
  3. For every $A\in [\omega]^\omega$ there exists $B \in \mathcal T$ such that $B\subset A$.
  4. If $0<\alpha<\mathfrak h$, then the $\alpha$-th level of $\mathcal T$ is a mad family over $\omega$.

Reminder: Let $N$ be an infinite countable set. An almost disjoint family over $N$ is an infinite collection $\mathcal A$ of infinite subsets of $N$ such that for every $A, B \in \mathcal A$, $A\cap B$ is finite. A maximal almost disjoint family (mad family) over $N$ is an almost disjoint family that isn't properly contained in any almost disjoint family.


I am trying to understand the proof of theorem 4.2 of this article. I have understood every detail but the one I'm gonna ask for help.

My Question:

Suppose $\mathfrak h<\mathfrak c$ and fix $\mathcal T$ as above. For every $A \subset 2^{<\omega}$, let $\pi_A=\{n \in \omega: A\cap 2^n\neq \emptyset\}\subset \omega$. So there exists $\mathcal A\subset[2^{<\omega}]^\omega$ such that:

  1. $\mathcal A$ is a mad family (over $2^{<\omega}$)
  2. Every $A \in \mathcal A$ is either a chain or an antichain in $2^{<\omega}$.
  3. $\pi_A \in \mathcal T$ for all $A \in \mathcal A$.
  4. If $A, B \in \mathcal A$ and $A\neq B$, then $\pi_A\neq \pi_B$.

Question: Why does $\mathcal A$ exists?

My Progress:

The authors claim that the existence of $\mathcal A$ follows from a simple application of the Zorn's Lemma. So I defined: $$\mathcal U=\{\mathcal A \subset [2^{<\omega}]^\omega: |\mathcal A|\geq\omega, \mathcal A \text{ is an adf}, \mathcal A \text{ satisfies (2), (3), (4)}\}.$$

I managed to show that $\mathcal U$ is not empty and it's easy to see that the union of a chain in $\mathcal U$ is again an element of $\mathcal U$, therefore there exists a maximal element $\mathcal M$. It remains to show that $\mathcal M$ is mad, and this is where I'm having trouble. If $\mathcal M$ is not mad, then there exists $X\in [2^{<\omega}]^\omega$ such that for every $A \in \mathcal M$, $A\cap X$ is finite. Then it's not hard to show that there exists an infinite $X' \subset X$ such that $X'$ is either a chain or an antichain in $2^{<\omega}$ and such that $\pi_{X'}\in \mathcal T$. If we can shrink $X'$ so that for every $A \in \mathcal M$, $\pi_A\neq \pi_{X'}$ then we are done but this is where I'm stuck.


You could define $\mathcal{A}$ recursively:

Enumerate all elements of $[2^{<\omega}]^\omega$ as $(X_\alpha)_{\alpha< \mathfrak{c}}$. Then whenever elements $(A_{\alpha})_{\alpha<\gamma}$ have already been constructed, check if $X_\gamma$ is almost disjoint from them. If not, skip step $\gamma$. If yes then find a subset $A_\gamma \subseteq X_\gamma$ so that $A_\gamma$ is a chain or antichain, $\pi_{A_\gamma} \in \mathcal{T}$ and $\pi_{A_\gamma} \neq \pi_{A_\alpha}$ for all $\alpha<\gamma$ (this is easy to achieve because we have only defined $<\mathfrak{c}$ many elements of $\mathcal{A} $ yet and below each node in $\mathcal{T}$ there are enough sets to choose from).

Of course there is choice involved and so maybe this is what they meant with Zorn's Lemma. In an application of Zorn's Lemma as you did above, you might have a maximal element which is not a mad family (just pick take a bijection of $2^\omega$ to $\mathcal{T}$ and get an almost disjoint family with the above properties which is not maximal but where each $\pi \in \mathcal{T}$ was already picked by restricting each $f \in 2^\omega$ to its corresponding set in $\mathcal{T}$).

| cite | improve this answer | |

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.