Independent Sets and the Continuum Hypothesis

数学論理学アドベントカレンダー2022 の記事を書いてみました。遅れてすみません。

Let $[X]^{<\omega}:=\{Y\subseteq X:|Y|<\aleph_0\}$ denote the collection of all finite subsets of $X$ (also written $\mathscr{P}_\omega(X)$).

We have a folklore characterization of the Continuum Hypothesis ($\textsf{CH}$).

In this article, we'll see proofs of the following facts.

Items (i) and (ii) imply Theorem 1, since one sees that every $f:[X]^{<\omega}\to[X]^{<\omega}$ admits an independent set of size $3$ iff $|X|\ge\aleph_2$.

Item (iii) illustrates that the above $\textsf{CH}$ phenomenon is orthogonal to descriptive set theory. Indeed, if $f:[\mathbb{R}]^{<\omega}\to[\mathbb{R}]^{<\omega}$ is Borel, then moving to a generic extension with $(|\mathbb{R}|=2^{\aleph_0}>\aleph_\omega)^{V[G]}$ and using item (i), we see from $\mathbf{\Sigma^1_1}$-absoluteness that in $V$, $f$ admits independent sets of size $k$ for any $k\in\mathbb{N}$. I learned about this absoluteness argument from ジタさん's article here .

Proof of (i)

The following proof is from [1, Lemma 2.3].

We proceed via induction on $k$. When $k=0$, let $A=\{\alpha\}$ be any set with $\alpha\notin f(\varnothing)$, and this is an independent set of size $1$.

Let $k>0$ and $f:[\aleph_k]^{<\omega}\to[\aleph_k]^{<\omega}$, and fix $\aleph_{k-1}\subseteq \aleph_k$.

For a set $Y\subseteq\aleph_k$ (later taken to be $Y=\aleph_{k-1}$), we put $f[Y]:=\bigcup_{Y_0\in [Y]^{<\omega}}f(Y_0)$, so that a routine cardinality computation shows that $|f[Y]|\le|Y|+\aleph_0$. We can perform the "closure under $f$" operation
$$\overline{Y}:=Y\cup f[Y]\cup f[f[Y]]\cup\cdots=\bigcup_{n\in\mathbb{N}}f^n[Y]$$
such that $|Y|\le|\overline{Y}|\le|Y|+\aleph_0$ and moreover $f[\overline{Y}]\subseteq\overline{Y}$. This defines the least $\overline{Y}\supseteq Y$ with the property that $f[\overline{Y}]\subseteq\overline{Y}$.

Now since $|\overline{\aleph_{k-1}}|=\aleph_{k-1}<\aleph_k$, we can pick some arbitrary $\alpha\in \aleph_k\setminus \overline{\aleph_{k-1}}$ outside of this closure.

Define the "restriction to $\overline{\aleph_{k-1}}$" function $g:[\overline{\aleph_{k-1}}]^{<\omega}\to [\overline{\aleph_{k-1}}]^{<\omega}$ such that
$$g(X_0)=\big(f(X_0)\cup f(X_0\cup\{\alpha\})\big)\cap \overline{\aleph_{k-1}}\in[\overline{\aleph_{k-1}}]^{<\omega}$$
By induction on $k$, the function $g:[\overline{\aleph_{k-1}}]^{<\omega}\to [\overline{\aleph_{k-1}}]^{<\omega}$ has an independent set $A\subseteq \overline{\aleph_{k-1}}$ of size $k$.

We claim that $A\cup\{\alpha\}$ is an independent set of size $k+1$. It's clear from the $g$-independence of $A$ that if $\beta \in A$ and $A_0\subseteq A\setminus\{\beta\}$, then
$$\beta\notin f(A_0)\cup f(A_0\cup\{\alpha\})$$
Moreover for any $A_0\subseteq A$, we have
$$\alpha\notin f(A_0)\subseteq \overline{\aleph_{k-1}}$$
due to $\overline{\aleph_{k-1}}\supseteq A$ being closed under $f$. So $A\cup\{\alpha\}$ is indeed independent. $\square$

Proof of (ii)

Again we proceed by induction on $k\in\mathbb{N}$.

When $k=0$, we define $f:[\aleph_0]^{<\omega}\to[\aleph_0]^{<\omega}$ via
$$f(X_0)=\begin{cases}\{0,1,\ldots,n-1\}&\text{if }X_0=\{n\}\\\varnothing&\text{else}\end{cases}$$
Then any set $\{m,n\}\subseteq\aleph_0=\mathbb{N}$ of size $2$ cannot be independent since if $m< n$, then $m\in f(\{n\})$.

Let $k>0$. For each $\alpha<\omega_k$, since $|\alpha|\le\aleph_{k-1}$, we can fix by induction a function $f_\alpha:[\alpha]^{<\omega}\to[\alpha]^{<\omega}$ without independent sets of size $k+1$. Then we define $f:[\omega_k]^{<\omega}\to[\omega_k]^{<\omega}$ via
$$f(X_0)=\begin{cases}\varnothing&\text{if }X_0=\varnothing\\f_{\max(X_0)}(X_0\setminus\{\max(X_0)\})&\text{else}\end{cases}$$

We claim that $f$ admits no independent set of size $k+2$. Towards a contradiction, assume $X_0\in[\omega_k]^{<\omega}$ is an independent set with $|X_0|=k+2$. Let $\alpha=\max(X_0)$, and so $X_0\setminus\{\alpha\}$ is an independent set for $f_\alpha$ of size $k+1$, which is a contradiction. $\square$

A slight variation of the proofs above gives another equivalent formulation of $\textsf{CH}$:

Proof of (iii)

Recall that $[\mathbb{R}]^{<\omega}$ is a standard Borel space, when its Borel structure is inherited from the set of representatives $\{(x_i)\in\mathbb{R}^{<\omega}:x_0< x_1<\ldots< x_{n-1}\}$ as a Borel (in fact, open) subset of the Polish space $\mathbb{R}^{<\omega}:=\bigsqcup_{n\in\mathbb{N}}\mathbb{R}^n$.

Fix any Borel function $f:[\mathbb{R}]^{<\omega}\to[\mathbb{R}]^{<\omega}$.

Now let's recall the definition and some properties of the hyperspace $K(X)$ of (nonempty) compact subsets of $X$ (later taken to be $X=\mathbb{R}$).

Fixing the sets $R_n\subseteq\mathbb{R}^n$ from Lemma 4, we can use Lemmas 5 and 6 to find a comeager set of $P\in K(\mathbb{R})$ such that $P\subseteq\mathbb{R}$ is nonempty perfect and $(P)^n\subseteq R_n$ for all $n$. By definition of independent sets and using $(P)^n\subseteq R_n$, we see that any such $P$ is an independent set. $\square$

The same proof above applies to any Universally Baire measurable $f:[\mathbb{R}]^{<\omega}\to\mathbb{R}^{\le\omega}$ as well.

Cohen forcing

We can give an explicit combinatorial account of the previous proof of (iii), and some alternative lemmas to replace Lemmas 5 and 6.

For simplicity, instead of using $\mathbb{R}$, we replace it with the Baire space $\omega^\omega$. For our purposes, the Cohen forcing $\mathbb{C}=(\omega^{<\omega},{\prec})$ consists of conditions which are finite segments $p=(x_0,\ldots,x_{n-1})\in\omega^{<\omega}$, and we say that $p\preceq q$ ($p$ is stronger than $q$) if $p$ is an end-extension of $q$.

When $G\subseteq\omega^{<\omega}$ is $\mathbb{C}$-generic, we write the corresponding Cohen real as $x_G:=\bigcup G\in \omega^\omega$.

For a Borel set $B\subseteq\omega^\omega$, we can use $\mathbf{\Sigma^1_1}$-absoluteness to define it in $V[G]$ using the same Borel code, such that $B=B^{V[G]}\cap (\omega^\omega)^V$. Then recall that $B\subseteq\omega^\omega$ is comeager iff $\Vdash x_G\in B^{V[G]}$.

Now we define a notion of forcing that generically adds a nonempty perfect subset $P$ of $\omega^\omega$.

When $G\subseteq\mathbb{P}$ is generic, we can define a function $\varphi_G:=\lim G:2^\omega\to \omega^\omega$ such that for all $x\in (2^\omega)^{V[G]}$, $\varphi_G(x):=\bigcup_{n\in\mathbb{N}}(\bigcup G)(x\upharpoonright n)\in\omega^\omega$. (We will show $\operatorname{dom}(\varphi_G(x))=\omega$ in Lemma 7.)

This $\varphi_G$ is clearly continuous, and we will see that in fact it is an embedding, so that $P_G:=\operatorname{image}(\varphi_G)\subseteq\omega^\omega$ is a nonempty perfect set. The main lemma is the following:

The proof is mostly standard, and the only nontrivial step is the following.

When combined with Lemma 4, Lemma 7 implies that $P_G\subseteq(\omega^\omega)^{V[G]}$ is an independent nonempty perfect set. Then the statement “there exists an independent nonempty perfect set” is $\mathbf{\Sigma^1_2}$, so $\mathbf{\Sigma^1_2}$-absoluteness implies that it holds in $V$ as well. This gives an alternative proof of (iii). $\square$

Infinite independent sets

Questions of the form “Which $f:[\kappa]^{<\omega}\to[\kappa]^{<\omega}$ admits an infinite independent set?” is once again less related to the question of $(\textsf{G})\textsf{CH}$, but more related to partition properties of cardinals. For example:

Compared with the main phenomema (i) and (ii), the consistency of “every $f:[\aleph_\omega]^{<\omega}\to [\aleph_\omega]^{<\omega}$ admits an infinite independent set” seems to be still unclear. The best result I could find is the following:

So if $\textsf{V}=\textsf{L}$, then $\kappa=\aleph_\omega$ does not satisfy the critetion of this last theorem, see eg. [5, Proposition 7.15].

Strong Fubini's Theorem

We conclude this article with a connection to the strong Fubini's theorem. I first learned about strong Fubini's theorem from でぃぐさん's article [6].

Let $\textsf{null}\subseteq\mathscr{P}(\mathbb{R})$ denote the set of Lebesgue null sets in $\mathbb{R}$.

The reader may compare this statement with the statement of Theorem 3, where every $f:[\mathbb{R}]^{<\omega}\to[\mathbb{R}]^{\le\omega}$ admitting an independent set of size $2$ is equivalent to $\lnot\textsf{CH}$.

It's easy to see that statement (1) from Proposition 11 is equivalent to the following statement:

• Here, (1) ⇒ (1') is easy since given any $\hat{f}:[0,1]\to\textsf{null}$, we can let $f:[\mathbb{R}]^{<\omega}\to\textsf{null}$ be defined via $f(\{\cot\pi\alpha\})=\cot(\pi\cdot\hat{f}(\alpha))$ if $\alpha\in(0,1)$ and $f(S)=\varnothing$ otherwise, and so any $f$-independent set $\{\cot\pi\alpha,\cot\pi\beta\}\subseteq\mathbb{R}$ of size $2$ gives an $\hat{f}$-independent pair $\alpha,\beta\in [0,1]$.
• Next, (1') ⇒ (1) is also easy since if $f:[\mathbb{R}]^{<\omega}\to\textsf{null}$, then letting for every $\alpha\in[0,1]$, $\hat{f}(\alpha):=\{\alpha\}\cup f(\varnothing)\cup f(\{\alpha\})$, we see that any $\hat{f}$-independent pair $\alpha,\beta\in[0,1]$ gives an $f$-independent set $\{\alpha,\beta\}$ of size $2$.

A proof from [6, Lemma 2] showed that statement (2) of Proposition 11 is equivalent to the following statement:

Note that in [6, Lemma 2], the quantifiers for the sections' coordinates $x,y$ are "for almost every", but we can always modify $D$ over a Lebesgue null subset of $[0,1]^2$ to get to a set $\hat{D}$ of our desired form, where we can quantify over every vertical/horizontal section.

It remains to show that (1') ↔ (2'). The following proofs are essentially contained in [6, Theorem 3].