a question on delta systems

259 Views Asked by At

I have two questions relating to existence of a delta system of certain cardinality:

a) Show that for every family $F = \{S_\alpha : \alpha<(2^{\aleph_0})^+\}$ of countable sets, $F$ includes a delta system of cardinality $(2^{\aleph_0})^+$.

b) Show that there exists a family $F = \{S_\alpha : \alpha<2^{\aleph_0}\}$ (each set still countable) such that there does not exist a delta system of cardinality $3$.

Apart from the definition of delta systems, I know the delta system lemma, but that's about it, and the lemma does not appear to directly help me here (although I probably need to figure out some way to use it). How can I approach these two problems?

1

There are 1 best solutions below

8
On BEST ANSWER

I’ll write $\mathscr{F}$ for your $F$.

Suppose that if $\mathscr{A}\subseteq\mathscr{F}$ is a $\Delta$-system then $|\mathscr{A}|\le 2^\omega$. I’ll construct families $\mathscr{F}_\xi$ for $\xi<\omega_1$ in such a way that $\mathscr{F}=\bigcup_{\xi<\omega_1}\mathscr{F}_\xi$, and $|\mathscr{F}_\xi|\le 2^\omega$ for each $\xi<\omega_1$; this implies that $|\mathscr{F}|\le\omega_1\cdot2^\omega=2^\omega$ and so proves the theorem.

Start by letting $\mathscr{F}_0$ be a maximal pairwise disjoint subfamily of $\mathscr{F}$. If $\eta<\omega_1$, and $\mathscr{F}_\xi$ has been defined for each $\xi<\eta$, let $\mathscr{F}_\eta'=\bigcup_{\xi<\eta}\mathscr{F}_\xi$, and let $F_\eta=\bigcup\mathscr{F}_\eta'$. For each countable $K\subseteq F_\eta$ let

$$\mathscr{F}_\eta(K)=\{S\in\mathscr{F}\setminus\mathscr{F}_\eta':S\cap F_\eta=K\}\;.$$

If there are $S_\alpha,S_\beta\in\mathscr{F}_\eta(K)$ such that $S_\alpha\cap S_\beta=K$, let $\mathscr{F}_\eta'(K)$ be a maximal $\Delta$-system in $\mathscr{F}_\eta(K)$ such that $\bigcap\mathscr{F}_\eta'(K)=K$; otherwise, let $\mathscr{F}_\eta'(K)$ be any maximal $\Delta$-system in $\mathscr{F}_\eta(K)$. Finally, set

$$\mathscr{F}_\eta=\bigcup\{\mathscr{F}_\eta'(K):K\subseteq F_\eta\text{ and }|K|\le\omega\}\;.$$

I leave it to you to check that if $|\mathscr{F}_\xi\le 2^\omega$ for each $\xi<\eta$, then $|\mathscr{F}_\eta|\le 2^\omega$ as well.

It only remains to show that $\bigcup_{\xi<\omega_1}\mathscr{F}_\xi=\mathscr{F}$, so suppose that $S\in\mathscr{F}\setminus\bigcup_{\xi<\omega_1}\mathscr{F}_\xi$.

  • Now show that $S\cap(F_{\xi+1}\setminus F_\xi)\ne\varnothing$ for each $\xi<\omega_1$, and get a contradiction by concluding that $|S|>\omega$. HINT: For each $\xi<\omega_1$ you want to consider the set $K=S\cap F_\xi$.

(That last step isn’t entirely trivial, but I want to give you a chance to work on it on your own; if you get completely stuck, I can say more.)

For the second question let $\mathscr{F}={}^\omega\{0,1\}$, the set of functions from $\omega$ to $\{0,1\}$, viewed as subsets of $\omega\times\{0,1\}$.


Added: After writing the original answer, I realized that I know another proof that is perhaps a little easier. I’ll give you your choice of which you find easier to complete.

Let $\kappa$ be the ordinal (and cardinal) $(2^\omega)^+$; since $|\bigcup\mathscr{F}|=\kappa$, we may as well assume that $\bigcup\mathscr{F}\subseteq\kappa$. For each $\alpha<\omega_1$ let $\mathscr{F}_\alpha=\{S\in\mathscr{F}:S\text{ has order-type }\alpha\}$; clearly there is some $\alpha<\omega_1$ such that $|\mathscr{F}_\alpha|=\kappa$, so without loss of generality we may assume that each $S\in\mathscr{F}$ has order-type $\alpha$. For each $S\in\mathscr{F}$ let $S=\{\sigma_\xi^S:\xi<\alpha\}$ be an increasing enumeration of $S$.

For each $\eta<\kappa$ we have $|\eta|\le 2^\omega$, so $\eta$ has at most $2^\omega$ countable subsets, and $\bigcup\mathscr{F}$ must be unbounded in $\kappa$. There is therefore some $\eta<\alpha$ such that $\{\sigma_\eta^S:S\in\mathscr{F}\}$ is unbounded in $\kappa$. Let $\eta_0$ be the smallest such $\eta$, and let $$\beta_0=\sup\{\sigma_\xi^S+1:S\in\mathscr{F}\text{ and }\xi<\eta_0\}\;;$$ check that $\beta_0<\kappa$, and observe that $\sigma_\xi^S<\beta_0$ for all $S\in\mathscr{F}$ and $\xi<\eta_0$.

Recursively choose $S_\gamma\in\mathscr{F}$ for each $\gamma<\kappa$ in such a way that

$$\sigma_{\eta_0}^{S_\gamma}>\max\left\{\beta_0,\sup\left\{\sigma_{\xi}^{S_\delta}:\delta<\gamma\text{ and }\xi<\alpha\right\}\right\}\;.$$

In other words, each $\sigma_{\eta_0}^{S_\gamma}$ is larger than $\beta_0$ and larger than every element of $\bigcup_{\delta<\gamma}S_\delta$.

Now let $\mathscr{F}'=\{S_\gamma:\gamma<\kappa\}$.

  • Show that $|\mathscr{F}'|=\kappa$.

  • Show that if $\delta<\gamma<\kappa$, then $S_\delta\cap S_\gamma\subseteq\beta_0$.

  • Use the previous observation to show that $\mathscr{F}'$ contains a $\Delta$-system $\mathscr{D}$ such that $|\mathscr{D}|=\kappa$ and $\bigcap\mathscr{D}\subseteq\beta_0$.