Skip to main content
2 of 2
added 301 characters in body
Will Brian
  • 18.5k
  • 3
  • 79
  • 106

I claim that every graph with $\leq \aleph_1$ vertices can be embedded in $[\omega]^\omega$ in the manner Dominic described. This means that we have a consistent answer to Dominic's question: the answer is yes assuming that the Continuum Hypothesis holds.

Recall that $\mathcal P(\omega) / \mathrm{fin}$ denotes the Boolean algebra of all subsets of $\omega$ modulo the ideal of finite sets. I'm going to write my answer in terms of $\mathcal P(\omega) / \mathrm{fin}$, because I think that's a good way to think about the problem. (To translate: a subset of $\omega$ is infinite iff its equivalence class in $\mathcal P(\omega) / \mathrm{fin}$ is nonzero, two sets are almost disjoint iff their equivalence classes in $\mathcal P(\omega) / \mathrm{fin}$ are incompatible.)

To prove the claim, we'll use something called the countable saturation of $\mathcal P(\omega) / \mathrm{fin}$. This means:

Suppose $\{a_n :\, n \in \omega\}$ is a countable subset of $\mathcal P(\omega) / \mathrm{fin}$, and let $x$ be a variable. Suppose we have countably many statements (in the first-order language of Boolean algebras) involving $x$ and the $a_n$'s, and no finite subset of these statements is inconsistent. Then there is, in $\mathcal P(\omega) / \mathrm{fin}$, a solution to this infinite system of equations: i.e., there is a value we can assign to $x$ in order to make all the statements true simultaneously.

(For example, if $a_n$ is (the equivalence class of) $\{2^nk :\, k \in \omega\}$ for each $n$, then we could have a countable sequence of statements asserting $0 \neq x < a_n$ for each $n$. No finite subset of these statements is inconsistent (indeed, the first $n$ statements are all satisfied by $x=a_{n+1}$). So countable saturation tells us that these statements are simultaneously satisfiable (e.g., by $\{2^k :\, k \in \omega\}$).)

For a proof that $\mathcal P(\omega) / \mathrm{fin}$ has this property, I'll refer you to van Mill's article in the Handbook of Set Theoretic Topology (link), corollary 1.1.5. The proof is what you might imagine: a delicate diagonalization with lots of bookkeeping.

Now suppose we have a graph $(V,E)$ with $|V| = \aleph_1$. Enumerate $V$ in type $\omega_1$, say $V = \{v_\alpha :\, \alpha < \omega_1 \}$. We'll build, by recursion, a sequence of $a_\alpha$'s such that the mapping $v_\alpha \mapsto a_\alpha$ is an embedding of $(V,E)$ into $\mathcal P(\omega) / \mathrm{fin}$.

For the base case, let $a_0$ be any member of $\mathcal P(\omega) / \mathrm{fin}$ other than $0$ or $1$ (the equivalence classes of $\emptyset$ and $\omega$). At stage $\alpha > 0$, we've obtained a countable collection of members of $\mathcal P(\omega) / \mathrm{fin}$, namely $\{a_\beta :\, \beta < \alpha \}$. Let $x$ be a variable, and consider the following system of equations: $$x \neq 0,1 \quad \qquad \qquad \qquad \qquad \qquad$$ $$\qquad \quad x - \vee F \neq 0 \qquad \text{for any finite } F \subseteq \{a_\beta :\, \beta < \alpha\}$$ $$\qquad \quad x \vee (\vee F) \neq 1 \qquad \text{for any finite } F \subseteq \{a_\beta :\, \beta < \alpha\}$$ $$x - a_\beta \neq 0 \qquad \text{ for any } \beta < \alpha \qquad \ \quad$$ $$a_\beta \wedge x = 0 \qquad \text{whenever } \{ v_\beta,v_\alpha \} \in E$$ $$a_\beta \wedge x \neq 0 \qquad \text{whenever } \{ v_\beta,v_\alpha \} \notin E$$ This is a countable system of equations, and it's easy to check that any finite number of them are simultaneously satisfiable. By the countable saturation of $\mathcal P(\omega) / \mathrm{fin}$, there is some value we can assign to $x$ to satisfy all these equations simultaneously. This is our choice of $a_\alpha$.

This recursion can continue through all countable ordinals. Once the recursion is done, it is easy to see that $a_\alpha \wedge a_\beta = 0$ if and only if $\{\alpha,\beta\} \in E$ for all $\alpha,\beta < \omega_1$.

To translate this back into the language of Dominic's question: for each $\alpha < \omega_1$, let $A_\alpha$ be any representative of the equivalence class $a_\alpha$. Then $A_\alpha \cap A_\beta$ is finite if and only if $\{\alpha,\beta\} \in E$ for all $\alpha,\beta < \omega_1$.

Finally, let me point out that a system of $\aleph_1$ equations like this is not generally satisfiable in $\mathcal P(\omega) / \mathrm{fin}$. That is, $\mathcal P(\omega) / \mathrm{fin}$ is not $\kappa$-saturated for any larger cardinals $\kappa$, not even consistently. The witness to this is Hausdorff gaps, which can be translated to a finitely satisfiable, unsatisfiable system of $\aleph_1$ equations in $\mathcal P(\omega) / \mathrm{fin}$. So to get an outright yes answer to Dominic's question, or even the consistency of a yes with the negation of CH, some new idea will be required.

Will Brian
  • 18.5k
  • 3
  • 79
  • 106