If a collection $\mathcal{F}$ is Ramsey, then $\mathcal{F}$ is Sperner

41 Views Asked by At

I guess I should mention we are working in $\mathsf{ZFC}$. We start with some definitions:

  1. $\mathbb{N}^{[<\infty]}=\{s:s\text{ is a finite subset of $\mathbb{N}$}\}$.

  2. Fix $\mathcal{F}\subseteq\mathbb{N}^{[<\infty]}$. A finite partition $\mathcal{P}=[F_0,F_1,...F_n]$ on $\mathcal{F}$ is a collection such that $\bigcup\mathcal{P}=\mathcal{F}$. We may assume without loss of generality that $\mathcal{P}$ is pairwise disjoint. For $M\subseteq\mathbb{N}$, $$F|_M=\{s\in\mathcal{F}:s\subseteq M\}.$$ We say that $\mathcal{F}$ is:

    a) Ramsey if for any finite partition there exists infinite $M\subseteq\mathbb{N}$ such that $F|_M$ is monochromatic. i.e. there exists a $i$, such that $F|_M\subseteq F_i$.

    b) Sperner if for all $s\neq t$ in $\mathcal{F}$, we have that $s\not\subset t$.

We want to prove that if $\mathcal{F}$ is Ramsey then there exists an infinite $M\in\mathbb{N}$ so $\mathcal{F}|_M$ is Sperner. I think the argument is as follows:

We partition $\mathcal{F}$ into $F_0,F_1$ so $s\in F_0$ iff no proper subset of $s$ is contained in $\mathcal{F}$. We notice that if $\emptyset\in F$, then $\emptyset\in F_0$. Since $\mathcal{F}$ is Ramsey, we know that there is an infinite $M\subseteq\mathcal{N}$ so $\mathcal{F}|_M$ is monochromatic. That is, either $\mathcal{F}|_M\subseteq F_0$ or $\mathcal{F}|_M\subseteq F_1$. We must show the latter cannot be true. Suppose for a contradiction, that $\mathcal{F}|_M\subseteq F_1$. Now, if $s\in\mathcal{F}|_{M}\subseteq F_1$, there exists $t\in\mathcal{F}$ such that $t\subset s$ for otherwise $s\in F_0$, contradictory to was we assumed. Since $\mathcal{F}\subseteq\mathbb{N}^{[<\infty]}$, $|s|=k$ with $k$ finite. Then $|t|<k$. Continuing to argue along these lines, we will eventually hit an $r\in F_1\cap\mathcal{F}|_M$, which has no proper subset in $\mathcal{F}$, and so must be an element of $F_0$. But if this is the case, then $\mathcal{F}|_M$ is not monochromatic, and so we conclude $\mathcal{F}|_M=F_0$. And clearly, for $s,t\in F_0$, it is true that $s\not\subset t$ and $t\not\subset s$, and so $\mathcal{F}|_M$ is Sperner as required.

Minus the hand-waving about the descending chain, does this look alright?