7
$\begingroup$

Let $\kappa$ be the smallest cardinality of a family $\mathcal F$ of subsets of $\omega$ such that for any bijective function $f:A\to B$ between disjoint infinite subsets of $\omega$ there exists a set $F\in\mathcal F$ such that the set $\{x\in A\cap F:f(x)\notin F\}$ is infinite.

It can be shown that $\mathfrak s\le \kappa\le\mathfrak c$, where $\mathfrak s$ is the splitting number.

Question. Is it consistent that $\kappa<\mathfrak c$? Or $\kappa=\mathfrak c$ in ZFC?

Remark. The affirmative answer to the first part of this question will imply a consistent negative answer to this MO-problem.

$\endgroup$

1 Answer 1

8
$\begingroup$

Recall that $\mathbf{non}(\mathcal{B})$ is the least cardinality of a non-meager subset of $\mathbb{R}$; the choice of presentation of $\mathbb{R}$ does not matter for this, so we take $\mathbb{R} = \mathcal{P}(\omega)$. It is well-known that consistently, $\mathbf{non}(\mathcal{B}) < \mathfrak{c}$; indeed, start from a model of CH and add $\aleph_2$-many Cohen reals.

Theorem. $\kappa \leq \mathbf{non}(\mathcal{B})$.

Proof. Suppose $\mathcal{F} \subseteq \mathcal{P}(\omega)$ is nonmeager. It suffices to show that $\mathcal{F}$ works for the definition of $\kappa$. Let $A, B$ be disjoint infinite subsets of $\omega$. Let $X$ be the set of all $F \subseteq \omega$ such that there are infinitely many $n \in A \cap F$ with $f(n) \not \in F$. I claim that $X$ is comeager. Indeed, for each finite $J \subseteq A$, let $X_J$ be the set of all $F \subseteq \omega$ such that there is some $n \in A \backslash J$ with $n \in A \cap F$ and $f(n) \not \in F$. Each $X_J$ is open dense, and $X = \bigcap_J X_J$.


Thus, consistently $\kappa < \mathfrak{c}$.

Incidentally, the following is perhaps a cleaner formulation of $\kappa$:

Claim. Let $\lambda$ be the least cardinality of a family $\mathcal{G}$ of subsets of $\omega$, such that for each increasing sequence $(x_n: n < \omega)$, there is some $F \in \mathcal{G}$ such that for infinitely many even $n < \omega$, $x_{n} \in F$ but $x_{n+1} \not \in F$. Then $\kappa = \lambda$.

Proof. It is straightforward to check that $\lambda \leq \kappa$: given $\mathcal{F}$ witnessing the definition of $\kappa$ and $(x_n: n < \omega)$, write $A = \{x_{2n}: n < \omega\}$, $B = \{x_{2n+1}: n < \omega\}$ and let $f: A \to B$ be $x_{2n} \mapsto x_{2n+1}$.

So we show $\kappa \leq \lambda$. Let $\mathcal{G}$ witness the definition of $\lambda$; let $\mathcal{F} = \mathcal{G} \cup \{\omega \backslash S: S \in \mathcal{G}\}$. We show that $\mathcal{F}$ is as in the definition of $\kappa$.

Suppose $A, B$ are infinite disjoint sets and $f: A \to B$ is a bijection. Note that since $\mathcal{F}$ is closed under complements, we are free to replace $(A, B, f)$ by $(B, A, f^{-1})$, if desired.

Choose $A' \subseteq A$ infinite such that either for all $x \in A'$, $f(x) > x$, or else for all $x \in A'$, $f(x) < x$. After possibly interchanging $A$ and $B$, we can suppose that for all $x \in A'$, $f(x) > x$. Write $B' = f[A']$.

Define an increasing sequence $(x_n: n < \omega)$ inductively so that for all $n$, $x_{2n} \in A'$ and $x_{2n+1} = f(x_{2n}) \in B'$. Namely, let $x_0 = \min(A')$, let $x_1 = f(x_0)$, and having defined $x_{2n-1}$, let $x_{2n}$ be the least element of $A'$ bigger than $x_{2n-1}$, and let $x_{2n+1} = f(x_{2n})$.

Choose $F \in \mathcal{F}$ such that there are infinitely many even $n < \omega$ with $x_n \in F$ but $x_{n+1} \not \in F$. Then for each such $n$, $x_n \in A \cap F$ but $f(x_n) = x_{n+1} \not \in F$, so $F$ is as desired.

Remark. For each infinite $I \subseteq \omega \times \omega$, we get a variant notion $\kappa_I$ of $\kappa$, namely $\kappa_I$ is the least cardinality of a family $\mathcal{G}$ of subsets of $\omega$, such that for each increasing sequence $(x_n: n < \omega)$, there is some $F \in \mathcal{G}$ such that for infinitely many $(n, m) \in I$, $x_n \in F$ but $x_m \not \in F$ (possibly $\kappa_I = \infty$).

It is easy to check that $\kappa = \kappa_{\{(2n, 2n+1): n < \omega\}}$ and $\mathfrak{s} = \kappa_{\{(n, n+1): n < \omega\}}$. The above proof shows that each $\kappa_I \leq \mathbf{non}(\mathcal{B})$, provided that for each finite $J \subset \omega$, there are infinitely many $(n, m) \in I$ with $n, m \not \in J$. It is interesting to ask which of these $\kappa_I$'s can be separated...

$\endgroup$
3
  • 3
    $\begingroup$ A very similar argument gives that $\kappa\leq\mathbf{non}(\mathcal L)$, the least cardinality of a set of positive outer Lebesgue measure. For any fixed $f:A\to B$, almost all subsets $F$ of $\omega$ are as required in the definition of $\kappa$. Indeed, for any fixed $a\in A$, the probability that $a\in F$ and $f(a)\notin F$ is $1/4$. So the probability that this happens for at least one $a\in A$ is $1$. $\endgroup$ Commented Sep 1, 2018 at 21:36
  • 2
    $\begingroup$ Looking at the two non cardinals in Cichon's diagram, and "connecting the dots", one might conjecture that $\kappa\leq\mathfrak d$. (If that turns out to be true, my next conjecture would be $\kappa=\mathfrak s$.) $\endgroup$ Commented Sep 1, 2018 at 21:39
  • 1
    $\begingroup$ $\kappa \leq \mathfrak{d}$ was what I looked at first, but I wasn't able to figure out an easy argument. $\endgroup$ Commented Sep 1, 2018 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .