文献あり

Independent Sets and the Continuum Hypothesis

132

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

Let $[X]^{< ω} := {Y \subseteq X : | Y | < ℵ_{0}}$ denote the collection of all finite subsets of $X$ (also written $P_{ω} (X)$ ).

Independent set

Let $f : [X]^{< ω} \to P (X)$ be any function. A set $A \subseteq X$ is called independent if for all finite $A_{0} \in [A]^{< ω}$ and $α \in A ∖ A_{0}$ , we have $α \notin f (A_{0})$ .

For example, if $F$ is a field, $X$ is an $F$ -vector space, and ${span}_{F} : [X]^{< ω} \to P (X)$ is the $F$ -span, then a set $A \subseteq X$ is independent with respect to ${span}_{F}$ iff $A$ is $F$ -linearly independent.

We have a folklore characterization of the Continuum Hypothesis ( $CH$ ).

The following are equivalent:

For any $f : [R]^{< ω} \to [R]^{< ω}$ , there exists an independent set of size $3$ .
$\neg CH$ .

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

For any $k \in N$ and $f : [ℵ_{k}]^{< ω} \to [ℵ_{k}]^{< ω}$ , there exists an independent set $A \subseteq ℵ_{k}$ of size $| A | = k + 1$ .
For $k \in N$ , there exists some $f : [ℵ_{k}]^{< ω} \to [ℵ_{k}]^{< ω}$ without any independent set $A \subseteq ℵ_{k}$ of size $| A | = k + 2$ .
For any Borel $f : [R]^{< ω} \to [R]^{< ω}$ , there exists an independent nonempty perfect set $P \subseteq R$ . (Thus $| P | = 2^{ℵ_{0}}$ .)

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

Item (iii) illustrates that the above $CH$ phenomenon is orthogonal to descriptive set theory. Indeed, if $f : [R]^{< ω} \to [R]^{< ω}$ is Borel, then moving to a generic extension with $(| R | = 2^{ℵ_{0}} > ℵ_{ω})^{V [G]}$ and using item (i), we see from $Σ_{1}^{1}$ -absoluteness that in $V$ , $f$ admits independent sets of size $k$ for any $k \in 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 = {α}$ be any set with $α \notin f (\emptyset)$ , and this is an independent set of size $1$ .

Let $k > 0$ and $f : [ℵ_{k}]^{< ω} \to [ℵ_{k}]^{< ω}$ , and fix $ℵ_{k - 1} \subseteq ℵ_{k}$ .

For a set $Y \subseteq ℵ_{k}$ (later taken to be $Y = ℵ_{k - 1}$ ), we put $f [Y] := ⋃_{Y_{0} \in [Y]^{< ω}} f (Y_{0})$ , so that a routine cardinality computation shows that $| f [Y] | \leq | Y | + ℵ_{0}$ . We can perform the "closure under $f$ " operation
$\overset{―}{Y} := Y \cup f [Y] \cup f [f [Y]] \cup \dots = ⋃_{n \in N} f^{n} [Y]$
such that $| Y | \leq | \overset{―}{Y} | \leq | Y | + ℵ_{0}$ and moreover $f [\overset{―}{Y}] \subseteq \overset{―}{Y}$ . This defines the least $\overset{―}{Y} \supseteq Y$ with the property that $f [\overset{―}{Y}] \subseteq \overset{―}{Y}$ .

Now since $| \overset{―}{ℵ_{k - 1}} | = ℵ_{k - 1} < ℵ_{k}$ , we can pick some arbitrary $α \in ℵ_{k} ∖ \overset{―}{ℵ_{k - 1}}$ outside of this closure.

Define the "restriction to $\overset{―}{ℵ_{k - 1}}$ " function $g : [\overset{―}{ℵ_{k - 1}}]^{< ω} \to [\overset{―}{ℵ_{k - 1}}]^{< ω}$ such that
$g (X_{0}) = (f (X_{0}) \cup f (X_{0} \cup {α})) \cap \overset{―}{ℵ_{k - 1}} \in [\overset{―}{ℵ_{k - 1}}]^{< ω}$
By induction on $k$ , the function $g : [\overset{―}{ℵ_{k - 1}}]^{< ω} \to [\overset{―}{ℵ_{k - 1}}]^{< ω}$ has an independent set $A \subseteq \overset{―}{ℵ_{k - 1}}$ of size $k$ .

We claim that $A \cup {α}$ is an independent set of size $k + 1$ . It's clear from the $g$ -independence of $A$ that if $β \in A$ and $A_{0} \subseteq A ∖ {β}$ , then
$β \notin f (A_{0}) \cup f (A_{0} \cup {α})$
Moreover for any $A_{0} \subseteq A$ , we have
$α \notin f (A_{0}) \subseteq \overset{―}{ℵ_{k - 1}}$
due to $\overset{―}{ℵ_{k - 1}} \supseteq A$ being closed under $f$ . So $A \cup {α}$ is indeed independent. $◻$

Proof of (ii)

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

When $k = 0$ , we define $f : [ℵ_{0}]^{< ω} \to [ℵ_{0}]^{< ω}$ via
$f (X_{0}) = {\begin{cases} {0, 1, \dots, n - 1} & if X_{0} = {n} \\ \emptyset & else \end{cases}$
Then any set ${m, n} \subseteq ℵ_{0} = N$ of size $2$ cannot be independent since if $m < n$ , then $m \in f ({n})$ .

Let $k > 0$ . For each $α < ω_{k}$ , since $| α | \leq ℵ_{k - 1}$ , we can fix by induction a function $f_{α} : [α]^{< ω} \to [α]^{< ω}$ without independent sets of size $k + 1$ . Then we define $f : [ω_{k}]^{< ω} \to [ω_{k}]^{< ω}$ via
$f (X_{0}) = {\begin{cases} \emptyset & if X_{0} = \emptyset \\ f_{max (X_{0})} (X_{0} ∖ {max (X_{0})}) & else \end{cases}$

For example, when $k = 1$ , our function $f : [ℵ_{1}]^{< ω} \to [ℵ_{1}]^{< ω}$ defined above can be made more explicit. For each $α < ω_{1}$ , fix an enumeration $α = {α_{0}, α_{1}, \dots}$ with indices from $ω$ . Then
$f (X_{0}) = {\begin{cases} {α_{0}, α_{1}, \dots, α_{n - 1}} & if X_{0} = {α_{n} < α} \\ \emptyset & else \end{cases}$
One may use this explicit form to check that $f$ has no independent set of size $3$ . [Hint: Let ${α_{m} < α_{n} < α}$ be the independent set.]

We claim that $f$ admits no independent set of size $k + 2$ . Towards a contradiction, assume $X_{0} \in [ω_{k}]^{< ω}$ is an independent set with $| X_{0} | = k + 2$ . Let $α = max (X_{0})$ , and so $X_{0} ∖ {α}$ is an independent set for $f_{α}$ of size $k + 1$ , which is a contradiction. $◻$

A slight variation of the proofs above gives another equivalent formulation of $CH$ :

Let $[X]^{\leq ω} := {Y \subseteq X : | Y | \leq ℵ_{0}}$ denote the collection of all countable subsets of $X$ (also written $P_{ω_{1}} (X)$ ).

The following are equivalent:

For any $f : [R]^{< ω} \to [R]^{\leq ω}$ , there exists an independent set of size $2$ .
$\neg CH$ .

Proof of (iii)

Recall that $[R]^{< ω}$ is a standard Borel space, when its Borel structure is inherited from the set of representatives ${(x_{i}) \in R^{< ω} : x_{0} < x_{1} < \dots < x_{n - 1}}$ as a Borel (in fact, open) subset of the Polish space $R^{< ω} := ⨆_{n \in N} R^{n}$ .

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

For every positive integer $n > 0$ , the set
$R_{n} := {(x_{i}) \in R^{n} : {x_{i}} \in [R]^{< ω} is an independent set of size n}$
is a comeager Borel subset of $R^{n}$ .

Fix $n > 0$ , and let
$C_{n} := {(x_{i}) \in R^{n} : x_{0} \notin f ({x_{1}, \dots, x_{n - 1}})} \subseteq R^{n}$
It's clear that $C_{n}$ is Borel.

Then for each $(x_{1}, \dots, x_{n - 1}) \in R^{n - 1}$ , the section
$C_{n}^{(x_{1}, \dots, x_{n - 1})} = {x_{0} \in R : x_{0} \notin f ({x_{1}, \dots, x_{n - 1}})} = R ∖ f ({x_{1}, \dots, x_{n - 1}})$
is a cofinite subset of $R$ , and so is comeager.

By Kuratowski–Ulam [2, Theorem 8.41], every section of $C_{n}$ is comeager implies that the set $C_{n}$ is comeager Borel.

In a similar way and by modifying the proof above, Kuratowski–Ulam also implies that the desired set
$R_{n} = {(x_{i}) \in R^{n} : \forall j \in n, \forall x_{j} \notin A_{0} \subseteq {x_{i}}, x_{j} \notin f (A_{0}) \cup A_{0}}$
is comeager Borel. Here we may use that comeager Borel sets are closed under finite intersections, and also preimages under canonical projections $π : R^{n} ↠ R^{m}$ . $◻$

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 = R$ ).

The hyperspace

K (X)

Let $X$ be a Polish space. Denote by $K (X)$ the set of (nonempty) compact subsets of $X$ . When $K (X)$ is endowed with the Vietoris topology (see [2, §4.F]), $K (X)$ becomes a Polish space.

More explicitly, if $d$ is a compatible complete metric on $X$ , then the Hausdorff metric $d_{H}$ is a compatible complete metric on $K (X)$ (see [2, Theorem 4.25]).

[2, Exercise 8.8]

Recall that a Polish space $X$ is perfect if $X$ has no isolated points.

If $X$ is a perfect Polish space, then comeagerly many $K \in K (X)$ is (nonempty) perfect.

[2, Theorem 19.1]

For $K \subseteq X$ and $n \in N$ , define $(K)^{n} := {(x_{i}) \in K^{n} : \forall i \neq j, x_{i} \neq x_{j}}$ to be the set of tuples in $K^{n}$ with pairwise distinct entries.

Let $X$ be a Polish space. For all $i \in N$ , we fix a natural number $n_{i} \in N$ and a comeager subset $R_{i} \subseteq X^{n_{i}}$ . Then comeagerly many $K \in K (X)$ satisfies that $\forall i \in N, (K)^{n_{i}} \subseteq R_{i}$ .

Fixing the sets $R_{n} \subseteq R^{n}$ from Lemma 4, we can use Lemmas 5 and 6 to find a comeager set of $P \in K (R)$ such that $P \subseteq 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. $◻$

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

For example, let $F \subseteq R$ be a countable subfield of $R$ . The $F$ -span ${span}_{F} : [R]^{< ω} \to R^{\leq ω}$ can be defined to be a Borel function. So by Example 1, there must exist a nonempty perfect set $P \subseteq R$ which is $F$ -linearly independent.

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 $R$ , we replace it with the Baire space $ω^{ω}$ . For our purposes, the Cohen forcing $C = (ω^{< ω}, ≺)$ consists of conditions which are finite segments $p = (x_{0}, \dots, x_{n - 1}) \in ω^{< ω}$ , and we say that $p ⪯ q$ ( $p$ is stronger than $q$ ) if $p$ is an end-extension of $q$ .

When $G \subseteq ω^{< ω}$ is $C$ -generic, we write the corresponding Cohen real as $x_{G} := ⋃ G \in ω^{ω}$ .

For a Borel set $B \subseteq ω^{ω}$ , we can use $Σ_{1}^{1}$ -absoluteness to define it in $V [G]$ using the same Borel code, such that $B = B^{V [G]} \cap (ω^{ω})^{V}$ . Then recall that $B \subseteq ω^{ω}$ is comeager iff $⊩ x_{G} \in B^{V [G]}$ .

Now we define a notion of forcing that generically adds a nonempty perfect subset $P$ of $ω^{ω}$ .

The notion of forcing $P$ consists of conditions $p$ such that for some $n \in N$ , $p$ is a function $p : 2^{< n} \to ω^{< ω}$ , satisfying for all $s, t \in 2^{< n}$ ,
$s \subseteq t \Rightarrow p (s) \subseteq p (t)$
where $\subseteq$ denotes end-extension.

For conditions $p, q \in P$ , we say that $p ⪯ q$ ( $p$ is stronger than $q$ ) if $p$ is an end-extension of $q$ , that is $q = p ↾ dom (q)$ .

When $G \subseteq P$ is generic, we can define a function $φ_{G} := lim G : 2^{ω} \to ω^{ω}$ such that for all $x \in (2^{ω})^{V [G]}$ , $φ_{G} (x) := ⋃_{n \in N} (⋃ G) (x ↾ n) \in ω^{ω}$ . (We will show $dom (φ_{G} (x)) = ω$ in Lemma 7.)

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

For all $x_{0}, x_{1}, \dots, x_{n - 1} \in (2^{ω})^{V [G]}$ pairwise distinct ( $i \neq j \Rightarrow x_{i} \neq x_{j}$ ), $(φ_{G} (x_{0}), φ_{G} (x_{1}), \dots, φ_{G} (x_{n - 1}))$ is $C^{n}$ -generic over $V$ .

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

Let $p \in P$ with $dom (p) = 2^{< n}$ , and let $D \subseteq C^{2^{n}}$ be a dense set. Then there exists some $q ≺ p$ with $dom (q) = 2^{\leq n}$ and $⟨ q (t) : t \in 2^{n} ⟩ \in D$ .

Lemma 8

Consider $\hat{p} := ⟨ p (t ↾_{(n - 1)}) : t \in 2^{n} ⟩ \in C^{2^{n}}$ . Then since $D \subseteq C^{2^{n}}$ is dense, there exists some $\hat{q} ⪯ \hat{p}$ such that $\hat{q} \in D$ . Define $q : 2^{\leq n} \to ω^{< ω}$ such that
$q (t) = {\begin{cases} p (t) & if t \in 2^{< n} \\ \hat{q} (t) & if t \in 2^{n} \end{cases}$
Now we finish by checking that $q \in P$ , $q ≺ p$ . $◻$

Lemma 7

Fix $m \in N$ such that $x_{i} ↾ m \in 2^{m}$ are pairwise distinct for $i \in n$ .

For any open dense set $D \subseteq C^{n}$ and $k \in N$ , define ${\hat{D}}_{k} \subseteq C^{k}$ such that
$(p_{0}, \dots, p_{k - 1}) \in {\hat{D}}_{k} \Leftrightarrow \forall i_{0} \neq \dots \neq i_{n - 1} \in k, (p_{i_{0}}, \dots, p_{i_{n - 1}}) \in D$
Note that for every $i_{0} \neq \dots \neq i_{n - 1} \in k$ (pairwise distinct), the set ${(p_{i}) \in C^{k} : (p_{i_{0}}, \dots, p_{i_{n - 1}}) \in D}$ is open dense in $C^{k}$ , and so ${\hat{D}}_{k}$ as a finite intersection of these $(\binom{k}{n}) \cdot n!$ many open dense sets is open dense in $C^{k}$ .

Define $E \subseteq P$ such that for any $p \in P$ with $dom (p) = 2^{\leq k}$ ,
$p \in E \Leftrightarrow (k \geq m) \land (⟨ p (t) : t \in 2^{k} ⟩ \in {\hat{D}}_{2^{k}})$
Since we've shown that ${\hat{D}}_{2^{k}}$ is open dense in $C^{2^{k}}$ , Lemma 8 implies that $E \subseteq P$ is dense, so we can fix some $p \in E \cap G$ and let $dom (p) = 2^{\leq k}$ .

Since $k \geq m$ , $x_{i} ↾ k \in 2^{k}$ are pairwise distinct for $i \in n$ . By definition of $E$ and ${\hat{D}}_{2^{k}}$ , we have
$(p (x_{0} ↾ k), p (x_{1} ↾ k), \dots, p (x_{n - 1} ↾ k)) \in D$
Since $p \in G$ , we also have $(p (x_{i} ↾ k)) \subseteq (φ_{G} (x_{i}))$ as an initial segment, so $(φ_{G} (x_{i}))$ meets $D$ as desired. $◻$

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

Infinite independent sets

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

[3, Theorem 45.2]

Let $κ$ be a Ramsey cardinal and let $λ < κ$ . Then every $f : [κ]^{< ω} \to [κ]^{< λ}$ admits an independent set of size $κ$ .

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

[4, Theorem 2]

Assume $V = L$ . The following are equivalent:

Every $f : [κ]^{< ω} \to [κ]^{\leq ω}$ admits an independent set of size $ω$ .
$κ \to (ω)_{2}^{< ω}$ .

So if $V = L$ , then $κ = ℵ_{ω}$ 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 $null \subseteq P (R)$ denote the set of Lebesgue null sets in $R$ .

The following are equivalent:

Every $f : [R]^{< ω} \to null$ admits an independent set of size $2$ .
For any function $f : [0, 1]^{2} \to [0, 1]$ , it holds that
$\int_{0}^{1} \int_{0}^{1} f d x d y = \int_{0}^{1} \int_{0}^{1} f d y d x$
whenever both integrals exist in the sense of Lebesgue integration.

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

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

(1') Every $\hat{f} : [0, 1] \to null$ admits an independent pair $α, β \in [0, 1]$ , in the sense that $α \notin \hat{f} (β)$ and $β \notin \hat{f} (α)$ .

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

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

(2') There does not exist a set $\hat{D} \subseteq [0, 1]^{2}$ , such that:

For every $x \in [0, 1]$ , the vertical section ${\hat{D}}_{x} := {y \in [0, 1] : (x, y) \in \hat{D}}$ is Lebesgue conull;
For every $y \in [0, 1]$ , the horizontal section ${\hat{D}}^{y} := {x \in [0, 1] : (x, y) \in \hat{D}}$ is Lebesgue null.

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].

\neg (1^{'}) \Rightarrow \neg (2^{'})

Let $f : [0, 1] \to null$ admit no independent pair. That is, for all $α, β \in [0, 1]$ , we have $α \in f (β)$ or $β \in f (α)$ .

Define the set $D := {(x, y) \in [0, 1]^{2} : x \in f (y)}$ .

Fix any $x \in [0, 1]$ . For any $y \in [0, 1]$ , we have either $x \in f (y)$ so then $y \in D_{x}$ , or $y \in f (x)$ . So every possible $y \in [0, 1]$ is covered by $D_{x} \cup f (x) = [0, 1]$ . Then since $f (x) \in null$ , the section $D_{x} \supseteq [0, 1] ∖ f (x)$ is Lebesgue conull.
Fix any $y \in [0, 1]$ . Then the section $D^{y} = f (y) \in null$ is Lebesgue null.

So $D \subseteq [0, 1]^{2}$ violates (2'). $◻$

\neg (2^{'}) \Rightarrow \neg (1^{'})

Let $D \subseteq [0, 1]^{2}$ violate (2'). So for every $x, y \in [0, 1]$ , we have $[0, 1] ∖ D_{x} \in null$ and $D^{y} \in null$ .

Define the function $f : [0, 1] \to null$ such that
$f (x) := ([0, 1] ∖ D_{x}) \cup D^{x}$

Fix any $α, β \in [0, 1]$ .

If $(α, β) \in D$ , then $α \in D^{β} \subseteq f (β)$ .
If $(α, β) \notin D$ , then $β \in [0, 1] ∖ D_{α} \subseteq f (α)$ .

So $f$ admits no independent pair. $◻$

参考文献

[1]

John T. Baldwin, Sy D. Friedman, Martin Koerwien, Michael C. Laskowski, Three Red Herrings around Vaught’s Conjecture, Transactions of the American Mathematical Society, 2016, pp. 3673-3694

[2]

Alexander S. Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Springer-Verlag, 1995

[3]

P. Erdős, A. Hajnal, A. Máté, R. Rado, Combinatorial Set Theory: Partition Relations for Cardinals, Studies in Logic and the Foundations of Mathematics, North-Holland, 1984

[4]

K.J. Devlin, J.B. Paris, More on the free subset problem, Annals of Mathematical Logic, 1973, pp. 327-336

[5]

Akihiro Kanamori, The Higher Infinite: Large Cardinals in Set Theory from their Beginnings, Springer Monographs in Mathematics, Springer, 2009

[6]

Unknown, 取得中..., Mathlog, アクセス日: Sat Apr 22 2023

投稿日：2022年12月22日