How to show that the chromatic number > aleph_0 Let $V =\{ f | \exists _{\alpha<\omega_1} ( f:\alpha \rightarrow \mathbb{N} \wedge f $ is $ 1-1) \}$. We define $E\subseteq [V]^2 $, such that $\forall_{f,g\in V } (<f,g>\in E \longleftrightarrow ( f\subseteq g \vee g\subseteq f))$. We need to show that the chromatic number of $G=(V,E)$ is bigger than $\aleph_ 0$. It is obvious why it cannot be $<\aleph_0$, but I'm having trouble showing that it cant be $=\aleph_0$. Could anyone help?
 A: There is a beautiful argument going back to, I think, Galvin. 
Assume that $F:V\to\omega$ is a good coloring. By transfinite recursion define $f_\alpha:\alpha\to\omega$ as follows. $f_0=\emptyset$. If $\alpha$ is limit, set $f_\alpha=\bigcup\{f_\beta:\beta<\alpha\}$. If $f_\alpha$ is given, let $f_{\alpha+1}$ be that extension of it to $\alpha+1$ for which $f_{\alpha+1}(\alpha)=F(f_\alpha)$ holds. Now one can show that each $f_\alpha$ is in $V$ and $f_{\beta}\subseteq f_\alpha$ for $\beta<\alpha$. But then $\bigcup\{f_\alpha:\alpha<\omega_1\}$ would be an injection $\omega_1\to\omega$, an impossibility.
A: Consider any coloring $\varphi:V\to\omega$. Construct a strictly decreasing sequence $\langle X_n:n\lt\omega\rangle$ in $\mathcal P(\mathbb N)$ and a strictly increasing sequence $\langle f_n:n\lt\omega\rangle$ in $V$ so that for each $n\in\omega$ we have:  


*

*$\text{range}(f_n)\subset X_n$,  

*$|X_n\setminus\text{range}(f_n)|=\aleph_0$,  

*either $\varphi(f_n)=n$, or else $\varphi(f)\ne n$ for all $f\in V$ such that $f_n\subseteq f,\text{range}(f)\subset X_n$, and $|X_n\setminus\text{range}(f)|=\aleph_0$.


[The last condition means that, whenever we can, we take $f_n$ to be a vertex of color $n$.]
Let $f=\bigcup_{n\lt\omega}f_n\in V$ and let $n=\varphi(f)$. Then $\varphi(f_n)=n=\varphi(f)$, showing that $\varphi$ is not a proper coloring of $G$. 
[Note that $\text{range}(f)\subseteq X=\bigcap_{n\lt\omega}X_n$, and $X_n\setminus X$ is infinite for every $n$ as the $X_n$ are strictly decreasing.]
P.S. In other words, the partially ordered set $P=(V,\subseteq)$ has the partition property $P\rightarrow(2)_{\omega}^1$.
A similar argument shows that $P\rightarrow(\omega)_{\omega}^1$, which in turn implies (according to something I read somewhere) that $P\rightarrow(\alpha)_{\omega}^1$ 
for every ordinal $\alpha\lt\omega_1$. [Posets $P$ such that $P\rightarrow(\omega)_{\omega}^1$ are called non-special, see this answer.]
P.P.S. To prove $P\rightarrow(\omega+1)_{\omega}^1$ we proceed as before except that, instead of trying to choose $f_n$ of color $n$, we try to choose $f_n$ of color $c_n$ where $\langle c_n:n\lt\omega\rangle$ is an enumeration of $\omega$ with each element repeated infinitely often.
