Set theory - Chapter 9: Combinatorial Set Theory

1. (1)

   Let $S$ be an infinite set endowed with a partial ordering. Let $F:{[S]}^{2}\rightarrow\{0,1\}$ such that $F({x,y})=1$ if and only if $x$ and $y$ are comparable. Then an infinite homogeneous set for $F$ is either a chain or a set of mutually incomparable elements

2. (2)

   Let $S$ be an infinite set endowed with a total ordering. Let $\{x_{\alpha}:\alpha<{|S|}\}$ an enumeration of $S$ and define $F:{[S]}^{2}\rightarrow\{0,1\}$ as follows: for all $\alpha<\beta$, $F({x_{\alpha},x_{\beta}})=1$ if and only if $x_{\alpha}<x_{\beta}$. Then an infinite homogeneous set provides an increasing or decreasing sequence $x_{{\varphi(\alpha)}}$.

Let $\kappa$ be an infinite cardinal. Define $\exp_{{0}}(\kappa)=\kappa$ and for all $n\in\mathbb{N}$, $\exp_{{n+1}}(\kappa)=2^{{\exp_{{n}}(\kappa)}}$. For all $n\geq 1$, we shall prove the partition property ${(\exp_{n}(\kappa))}^{+}\rightarrow{(\kappa^{+})}_{\kappa}^{{n+1}}$ For $n=1$ we get ${(2^{\kappa})}^{+}\rightarrow{(\kappa^{+})}_{\kappa}^{2}$ and in particular ${(2^{\kappa})}^{+}\rightarrow{(\kappa^{+})}^{2}$. We will denote $\lambda_{n}=\exp_{n}(\kappa)$.

Let $n\geq 1$ and $F:{[\lambda_{n}^{+}]}^{{n+1}}\rightarrow\kappa$. Define for all $a\in\lambda_{n}^{+}$ the function $F_{a}$ on ${\left[\lambda_{n}^{+}\setminus\{a\}\right]}^{{n}}$ by $F_{a}(x)=F(x\cup\{a\})$.

First we construct by induction on $\alpha<\lambda_{{n-1}}^{+}$ a sequence $A_{\alpha}\subseteq\lambda_{n}^{+}$ of sets of size $\lambda_{{n}}$. $A_{0}$ is arbitrary and at limit step $A_{\alpha}=\bigcup_{{\beta<\alpha}}A_{\beta}$. If $A_{\alpha}$ is defined then for all $C\in{[A_{\alpha}]}^{{<\lambda_{{n-1}}^{+}}}$ the sets of ${F_{u}}_{{|C}}$ such that $u\in\lambda_{n}^{+}\setminus C$ is of size at most $\kappa^{{|C|}}=\kappa^{{\lambda_{{n-1}}}}=\kappa^{{\exp_{{n-1}}(\kappa)}}=2^{{(\exp_{{n-1}}(\kappa))}}=\exp_{n}(\kappa)=\lambda_{n}$. Let $V_{C}\subseteq\lambda_{n}^{+}\setminus C$ of size $\lambda_{n}$ such that $\{{F_{u}}_{{|C}}:u\in\lambda_{n}^{+}\setminus C\}=\{{F_{v}}_{{|C}}:v\in V_{C}$ and define $A_{{\alpha+1}}=A_{\alpha}\cup\bigcup_{{C\in{[A_{\alpha}]}^{{<\lambda_{{n-1}}^{+}}}}}V_{C}$. We have $\lambda_{{n}}=|A_{\alpha}|\leq|A_{{\alpha+1}}|\leq\lambda_{{n}}+\sum_{{C\in{[A_{\alpha}]}^{{<\lambda_{{n-1}}^{+}}}}}{|V_{C}|}\leq\lambda_{{n}}+{\left|{[A_{\alpha}]}^{{<\lambda_{{n-1}}^{+}}}\right|}\lambda_{n}=\lambda_{n}^{{\lambda_{{n-1}}}}\lambda_{n}=2^{{\lambda_{{n-1}}}}\lambda_{n}=\lambda_{n}$.

Now define $A=\bigcup_{{\alpha<\lambda_{{n-1}}^{+}}}A_{\alpha}$, which is of size at most $\lambda_{{n-1}}^{+}\lambda_{n}=\lambda_{n}<\lambda_{n}^{+}$. In particular, there exists $a\in\lambda_{n}^{+}\setminus A$. We shall define by induction a set $X=\{x_{\alpha}:\alpha<\lambda_{{n-1}}^{+}\}\subseteq A$. Let $x_{0}\in A$ be arbitrary. Suppose $C=\{x_{\beta}:\beta<\alpha\}$ is defined. $|C|=|\alpha|<\lambda_{{n-1}}^{+}$. So there is $\alpha<\lambda_{{n-1}}^{+}$ such that $C\subseteq A_{\alpha}$. We have $a\in\lambda_{{n-1}}^{+}\setminus A\subseteq\lambda_{{n-1}}^{+}\setminus A_{\alpha}$ so there is $x_{{\alpha+1}}\in A_{{\alpha+1}}\subseteq A$ such that ${F_{{x_{{\alpha+1}}}}}_{{|C}}={F_{a}}_{{|C}}$.

Now for any $x_{{\alpha_{1}}}<x_{{\alpha_{2}}}<...<x_{{\alpha_{{n+1}}}}$ elements of $X$, we have $F(\{x_{{\alpha_{1}}},x_{{\alpha_{2}}},...,x_{{\alpha_{{n+1}}}}\})=F_{{x_{{\alpha_{{n+1}}}}}}(\{x_{{\alpha_{1}}},x_{{\alpha_{2}}},...,x_{{\alpha_{{n}}}}\})=F_{a}(\{x_{{\alpha_{1}}},x_{{\alpha_{2}}},...,x_{{\alpha_{{n}}}}\})=G(\{x_{{\alpha_{1}}},x_{{\alpha_{2}}},...,x_{{\alpha_{{n}}}}\})$ where $G:{[X]}^{n}\rightarrow\kappa$ is defined by $x\mapsto F_{a}(x)$. By construction $|X|=\lambda_{{n-1}}^{+}$.

If $n=1$ then $|X|=\lambda_{{n-1}}^{+}=\kappa^{+}>\kappa$ and $\kappa^{+}$ regular. So by there is $H\subseteq X$ of size $\kappa^{+}$ such that $G$ is constant on ${[X]}^{n}\cong X$. If $n>1$ and if the result is true for $n-1$ then applying this to $G$ also gives an homogeneous $H\subseteq X$ of size $\kappa^{+}$. Finally, $F$ is constant on ${[H]}^{{n+1}}$.

Let $A,B$ be a partition of ${[\omega_{1}]}^{2}$. For all $\alpha<\omega_{1}$ let $K_{\alpha}$ be a maximal subset of $\alpha$ such that $[K_{\alpha}\cup\{\alpha\}]^{2}\subseteq B$. Suppose that one of the $K_{\alpha}$ is infinite. Then extract an $\omega$-sequence $\alpha_{0}<\alpha_{1}<...$ in $K_{\alpha}\subseteq\alpha$. Then $H=\{\alpha_{n}:n<\omega\}\cup\{\alpha\}$ is of order type $\omega+1$ and ${[H]}^{2}\subseteq B$.

Otherwise, all the $K_{\alpha}$ are finite and we can write the element of $K_{\alpha}$ $\beta_{{\alpha 1}}<\beta_{{\alpha 2}}<...<\beta_{{\alpha n_{\alpha}}}$. Consider the stationary set $C=\omega_{1}\setminus\omega$. Then for all $\alpha\in C$ we have $n_{\alpha}<\omega\leq\alpha$. By Fodor’s theorem, there exists a stationary set $S\subseteq C$ and $n\in\mathbb{N}$ such that for all $\alpha\in S$ $|K_{\alpha}|=n_{\alpha}=n$. Similarly, because $\beta_{{\alpha 1}}<\alpha$ we can find a stationary set $S_{1}\subseteq S$ and $\beta_{1}$ such that for all $\alpha\in S_{1}$, we have $\beta_{{\alpha 1}}=\beta_{1}$. And by induction we get $\beta_{1},...,\beta_{n}$ and $S_{n}$ stationary such that for all $\alpha\in S_{n}$ we have $K_{\alpha}=\{\beta_{1},\beta_{2},...,\beta_{n}\}=K$.

Now let $\alpha,\beta\in S_{n}$. By maximality of $\alpha$ we have ${[K\cup\{\alpha\}\cup\{\beta\}]}^{2}\nsubseteq B$. But ${[K\cup\{\alpha\}\cup\{\beta\}]}^{2}={[K_{\alpha}\cup\{\alpha\}]}^{2}\cup{[K_{\beta}\cup\{\beta\}]}^{2}\cup\{\{\beta,\alpha\}\}$ and the two first sets are included in $B$ so $\{\beta,\alpha\}\notin B$ that is $\{\beta,\alpha\}\in A$. $S_{n}$ is unbounded so we can construct by induction for all $\alpha\in\omega_{1}$ $\gamma_{\alpha}\in S_{n}\cap\{\beta:\beta>\sup_{{\xi<\alpha}}\gamma_{\xi}\}$. Then $S=\{\gamma_{\alpha}:\alpha<\omega_{1}\}$ is of order type $\omega_{1}$ and ${[S]}^{2}\subseteq{[S_{n}]}^{2}\subseteq A$.

In this exercise, for any infinite set of ordinal $A$ and ordinal $\alpha$, ${[A]}^{\alpha}$ denotes the set of all increasing $\alpha$-sequence in $A$. Let $\kappa$ be an infinite cardinal. For all $s,t\in{[\kappa]}^{\omega}$, let $s\equiv t$ if and only if $\{n:s(n)\neq t(n)\}$ is finite. Pick a representative for each equivalence class. Define a function $F$ on ${[\kappa]}^{{\omega}}$ by $F(s)=0$ if $s$ differs from the representative in its class at an even number of places and $F(s)=1$ otherwise. Let $H\subseteq\kappa$ of order-type $\omega$. Define by induction on $n\in\omega$ an increasing sequence of ordinal by $x_{n}=\min(H\setminus\{x_{i}:i<n\})$. Define an increasing $\omega$-sequence $s$ of elements of $H$ by $n\in\mathbb{N},s(n)=x_{{2n}}$. Let $\bar{s}$ be the representative of $s$. Consider the finite set $X=\{n:s(n)\neq\bar{s}(n)\}$ and pick $m>\max X$. Define $t(n)=s(n)=x_{{2n}}$ if $n\neq m$ and $t(m)=x_{{2m+1}}$. Then the set $t$ is still an increasing $\omega$-sequence of elements of $H$. We have $\{n:t(n)\neq\bar{s}(n)\}=X\cup\{m\}$ finite so $\bar{t}=\bar{s}$. Moreover, $F(s)\equiv|X|\mod 2$ and $F(t)\equiv|X\cup\{m\}|\equiv|X|+1\mod 2$. So $F(s)\neq F(t)$ and $F$ is not constant on ${[H]}^{\omega}$.

Let $T$ be a tree of height $\omega$ such that all levels are finite. For all $x\in T$, let $S_{x}$ be the successors of $x$. We construct by induction a sequence $x_{0}<x_{1}<x_{2}...$ such that $o(x_{n})=n$ and $T_{n}=S_{{x_{n}}}$ is infinite.

$T=\bigcup_{{\{x\in T:o(x)=0\}}}S_{x}$ is infinite and level $0$ is finite so we can find so $x_{0}$ at level $0$ such that $T_{0}=S_{{x_{0}}}$ is infinite. If $x_{n}$ is constructed, then $T_{n}=\{x_{n}\}\cup\bigcup_{{\{x\in T_{n}:o(x)=n+1\}}}$ is infinite and level $n$ is finite so we can find $x_{{n+1}}>x_{n}$ at level $n+1$ such that $T_{{n+1}}=S_{{x_{{n+1}}}}$ is infinite.

If $B$ is a maximal chain containing $X=\{x_{n}:n\in\mathbb{N}\}$ then $B$ is an infinite branch of $T$

Let $T$ be a normal $\alpha$-tree. Given $x\in T$, let’s $x_{\xi}$ denote the predecessor of $x$ at level $\xi\leq o(x)$. Define the application $f$ on $T$ by $f(x)={(x_{{\xi+1}})}_{{\xi<o(x)}}$ and $\bar{(}T)=f(T)$. If $x,y\in T$ are such that $f(x)=f(y)$ then in particular $o(x)=o(y)$. We show that for all $\beta<\alpha$, any two $x,y\in T$ at level $\beta$ such that $f(x)=f(y)$ satisfy $x=y$. If $\beta=\gamma+1$ is a successor ordinal then $f(x)=f(y)$ gives $x=x_{{\gamma+1}}=y_{{\gamma+1}}=y$. If $\beta$ is a limit ordinal then $f(x)=f(y)$ only gives $x_{{\xi}}=y_{{\xi}}$ for all successor ordinals $\xi<\beta$. Suppose $\xi$ is the least limit ordinal such that $x_{{\xi}}\neq y_{{\xi}}$. Then for all $\psi<\xi$ we have $x_{{\psi}}=y_{{\psi}}$ and so the predecessors of $x_{{\xi}}$ and $y_{{\xi}}$ are the same. Because $T$ is a normal tree and $\xi$ is limit we have $x_{{\xi}}=y_{{\xi}}$, a contradiction. Hence $x_{{\xi}}=y_{{\xi}}$ for all $\xi<\beta$ and again, because $T$ is normal, we get $x=y$.

We got a bijection $T\cong\bar{T}$. Let’s show that it is actually an order isomorphism $(T,<)\cong(\bar{T},\subsetneq)$. If $x\leq y$ then $o(x)\leq o(y)$ and for all $\xi\leq o(x)$, we have $x_{\xi}=y_{\xi}$. Hence $f(x)={(x_{{\xi+1}})}_{{\xi<o(x)}}={(y_{{\xi+1}})}_{{\xi<o(x)}}\subseteq{(y_{{\xi+1}})}_{{\xi<o(y)}}=f(y)$. Conversely, if $f(x)\subseteq f(y)$ then $o(x)\leq o(y)$ and $x_{{\xi}}=y_{{\xi}}$ for all successor ordinal $\leq o(x)$. As above, we get that this is true for all ordinal $\leq o(x)$ and in particular $x=x_{{o(x)}}=y_{{o(x)}}\leq y$.

Finally, $(\bar{T},\subsetneq)\cong(T,<)$ is a normal $\alpha$-tree. If $o(f(x))=\beta$ then $\operatorname{dom}f(x)=o(x)=o(f(x))=\beta$ and so the $\beta$-th level is $\{t\in\bar{T}:\operatorname{dom}t=\beta\}$. Suppose $t\subseteq s$ where $s\in\bar{T}$ and let $x\in T$ such that $f(x)=s$. We have $\operatorname{dom}t\subseteq\operatorname{dom}s=o(x)$ Then $f(x_{{|t|}})=(x_{{\xi+1}})_{{\xi<|t|}}=(s(\xi))_{{\xi<|t|}}=(t(\xi))_{{\xi<|t|}}=t$ so $t\in\bar{T}$.

Let $T$ be a normal $\omega_{1}$ tree that has an uncountable branch $B$. Each $x\in B$ has infinitely many immediate successor and only one in $B$ so we can pick $z_{x}\notin B$ immediate successor of $x$. Let $x<y$ two elements of $B$. Then $o(z_{x})=o(x)+1>o(y)+1=o(z_{y})$ so $z_{x}\leq z_{y}$ is impossible. Suppose $z_{y}<z_{x}$. We also have $x<z_{x}$. If $z_{y}\leq x$ then $z_{y}\in B$ and if $x<z_{y}$ we get $o(x)<o(z_{y})=o(y)+1\leq o(x)$. Both cases are impossible and so $x,z_{y}$ are incomparable predecessors of $z_{x}$, a contradiction. Finally, $z_{x},z_{y}$ are incomparable and so $A=\{z_{x}:x\in B\}$ is an uncountable antichain of $T$.

We let $\sup\emptyset=0$ and we define for all $x\in T$, $f(x)=\sup x$ If $x,y\in T$ and $x<y$ then there are $\alpha<\beta$ such that $x\in U_{\alpha}$ and $y\in Y_{\beta}$. We have $x\subseteq y$ and so $x=y_{{|\alpha}}\subsetneq y_{{\alpha+1}}\subseteq y$. By construction, $\sup y_{{|\alpha}}<supy_{{|\alpha+1}}$ and so $f(x)=\sup x<\sup y=f(y)$.

…

Let $W$ be an uncountable set of finite sets. Let $\{X_{\alpha}:\alpha<\omega_{1}\}\subseteq W$. We have $\left|\bigcup_{{\alpha<\omega_{1}}}X_{\alpha}\right|\leq\aleph_{1}\aleph_{0}=\aleph_{1}$. So we may assume $\bigcup_{{\alpha<\omega_{1}}}X_{\alpha}\subseteq\omega_{1}$. For all $\alpha<\omega_{1}$, we have $K_{\alpha}=X_{\alpha}\cup\alpha\subseteq\alpha$. As in exercise 9.2, we can find a stationary set $S$ and a finie set $X$ such that for all $\alpha<\omega_{1}$ we have $X=X_{\alpha}\cap\alpha\subseteq X_{\alpha}$.

We define by induction on $\alpha<\omega_{1}$ a sequence $\beta_{\alpha}$. If $\beta_{\xi}$ is defined for all $\xi<\alpha$ then $\gamma_{\alpha}=\sup_{{\xi<\alpha}}X_{{\beta_{\xi}}}<\omega_{1}$ since $\alpha<\omega_{1}$ and $|X_{{\beta_{\xi}}}|<\aleph_{0}$. Because $S$ is unbounded, we can find taking $\beta_{\alpha}>\gamma_{\alpha}$.

If $\alpha_{1}<\alpha_{2}<\omega_{1}$ then $X_{{\beta_{{\alpha_{1}}}}}\subseteq\beta_{{\alpha_{2}}}$ by construction and so $X_{{\beta_{{\alpha_{1}}}}}\cap X_{{\beta_{{\alpha_{2}}}}}\subseteq\beta_{{\alpha_{2}}}\cap X_{{\beta_{{\alpha_{2}}}}}=X\subseteq X_{{\beta_{{\alpha_{1}}}}}\cap X_{{\beta_{{\alpha_{2}}}}}$. Hence $Z=\{X_{{\beta_{{\alpha}}}}:\alpha<\omega_{1}\}$ is a $\Delta$-system.

Let $\kappa$ be an infinite cardinal such that $2^{{<\kappa}}=\kappa$. So if $S=\bigcup_{{\alpha<\kappa}}{\{0,1\}}^{\alpha}$ we have $|S|=\sum_{{\alpha<\kappa}}2^{{|\alpha|}}=2^{{<\kappa}}=\kappa$. For all $f:\kappa\rightarrow\{0,1\}$ we define $A_{f}=\{s\in S:s\subseteq f\}=\{f_{{|\alpha}}:\alpha<\kappa\}$. If $f\neq g$ are functions from $\kappa$ to $\{0,1\}$ then there is $\beta<\kappa$ such that $f(\beta)\neq g(\beta)$. We have ${|A_{f}\cap A_{g}|}\leq{|\{\alpha<\kappa:f_{{|\alpha}}=g_{{|\alpha}}\}|}\leq\beta<\kappa$. So $\{A_{f}:f\in{\{0,1\}}^{\kappa}$ is a family of $2^{\kappa}$ almost disjoint subsets of $S$.

Let $\mathcal{F}$ be a family of $\aleph_{2}$ almost disjoint functions $f:\omega_{1}\rightarrow\omega$. Each $f\in\mathcal{F}$ is regressive on $C=\omega_{1}\setminus\omega$ so there is a stationary set $S_{f}\subseteq C$ such that $f$ is constant on $S_{f}$ with value $n_{f}\in\omega$. We get an application $\mathcal{F}\rightarrow\omega$ by $f\mapsto n_{f}$. Because $|\mathcal{F}|=\aleph_{2}>\aleph_{0}=|\omega|$ there is $\mathcal{G}\subseteq\mathcal{F}$ of size $\aleph_{2}$ and $n\in\omega$ such that for all $f\in\mathcal{G}$ we have $n_{f}=n$. Then for all distinct $f,g\in\mathcal{G}$, we have $|S_{f}\cap S_{g}|\leq|\{\beta<\omega_{1}:f(\beta)=g_{{\alpha}}(\beta)\}|<\omega_{1}$.

So $\mathcal{G}$ is an almost disjoint family of $\aleph_{2}$ stationary sets. Let $\{S_{{f_{\alpha}}}:\alpha<\omega_{2}\}$ an enumeration of $\mathcal{G}$. We construct by induction on $\alpha<\omega_{2}$ a family of pairwise disjoint stationary sets $U_{\alpha}\subseteq S_{{f_{\alpha}}}$.

Let $\alpha<\omega_{2}$ and suppose we have constructed the pairwise disjoint stationary sets $U_{\xi}$ for all $\xi<\alpha$. $C_{\alpha}=\{\beta<\omega_{1}:\beta>\alpha\}$ is closed unbounded so $T_{\alpha}=S_{{f_{\alpha}}}\cap C_{\alpha}$ is stationary. Let $x\in T_{\alpha}$. By induction hypothesis, there is at most one $\xi$ such that $x\in U_{\xi}$. Let $f(x)=\xi$ if $x\in U_{\xi}$ and $f(x)=\alpha$ if $x$ does not belong to any $U_{\xi}$. Then $f$ is regressive on $T_{\alpha}$ and so is constant with value $\gamma$ on some stationary set $U_{\alpha}\subseteq T_{\alpha}$. If $\gamma<\alpha$ then $U_{\alpha}\subseteq U_{\gamma}$ and $|U_{\alpha}|=|U_{\alpha}\cap U_{\gamma}|\leq|S_{{f_{\alpha}}}\cap S_{{f_{\gamma}}}|<\omega_{1}$, contradicting the fact that $U_{\alpha}$ is stationary. So $\gamma=\alpha$ and $U_{\alpha}$ is disjoint from all the $U_{\xi}$, $\xi<\alpha$ as wanted.

For all $x\in{[\omega]}^{{<\omega}}$ define $F(x)=1$ if $|x|\in x$ and $F(x)=0$ otherwise. Let $H\subseteq\omega$ be an infinite set. Let $n\in H$ and $X,Y\subseteq H\setminus\{n\}$ such that $|X|=n$ and $|Y|=n-1$. Then $F(X)=0$ and $F(Y\cup\{n\})=1$ so $F$ is not constant on ${[H]}^{n}$. Thus $\omega\not\rightarrow{(\omega)}^{{<\omega}}$.