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.


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

| cite | improve this answer | |
  • 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$ – Andreas Blass Sep 1 '18 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$ – Andreas Blass Sep 1 '18 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$ – Douglas Ulrich Sep 1 '18 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.