11
$\begingroup$

A function $f:\omega\to\omega$ is called

$\bullet$ 2-to-1 if $|f^{-1}(y)|\le 2$ for any $y\in\omega$;

$\bullet$ almost injective if the set $\{y\in \omega:|f^{-1}(y)|>1\}$ is finite.

Let us introduce two critical cardinals, related to $2$-to-$1$ functions:

$\mathfrak{j}_{2:1}$ is the largest cardinal $\kappa\le\mathfrak c$ such that for any family $F\subset \omega^\omega$ of $2$-to-$1$ functions with $|F|<\kappa$ there exists an infinite subset $J\subset\omega$ such that for any $f\in F$, the restriction $f{\restriction}J$ is almost injective;

$\mathfrak{j}_{2:2}$ is the largest cardinal $\kappa\le\mathfrak c$ such that for any family $F\subset \omega^\omega$ of $2$-to-$1$ functions with $|F|<\kappa$ there are two infinite sets $I,J\subset\omega$ such that for any $f\in F$ the intersection $f(I)\cap f(J)$ is finite.

It can be shown that $\max\{\mathfrak s,\mathfrak b\}\le\mathfrak j_{2:1}\le\mathfrak j_{2:2}\le\mathrm{non}(\mathcal M)$.

I would like to have more information on the cardinals $\mathfrak j_{2:1}$ and $\mathfrak j_{2:2}$.

Problem 0. Is $\mathfrak j_{2:1}=\mathfrak j_{2:2}$ in ZFC?

Problem 1. Is $\mathfrak j_{2:2}=\mathrm{non}(\mathcal M)$ in ZFC?

Problem 2. What is the value of the cardinals $\mathfrak j_{2:1}$ and $\mathfrak j_{2:2}$ in the Random Model? (In this model $\mathfrak b=\mathfrak s=\omega_1<\mathfrak c=\mathrm{non}(\mathcal M)$, see $\S$11.4 in this survey paper of Blass).

Remark. It can be shown that the cardinal $\mathfrak j_{2:1}$ (resp. $\mathfrak j_{2:2}$) is equal to the smallest weight of a finitary coarse structure on $\omega$ that contains no infinite discrete subspaces (resp. contains no infinite asymptotically separated sets). In this respect $\mathfrak j_{2:1}$ can be considered as an asymptotic counterpart of the cardinal $\mathfrak z$, defined as the smallest weight of an infinite compact Hausdorff space that contain no nontrivial convergent sequences. The cardinal $\mathfrak z$ was introduced by Damian Sobota and deeply studied by Will Brian and Alan Dow.

The similarity between $\mathfrak j_{2:1}$ and $\mathfrak z$ suggests another

Problem 3. Is $\mathfrak j_{2:1}=\mathfrak z$ in ZFC?

$\endgroup$
  • 2
    $\begingroup$ A theorem of Koppelberg states that $\mathrm{cov}(\mathcal M) \leq \mathfrak{z}$. It's consistent that $\mathrm{non}(\mathcal M) < \mathrm{cov}(\mathcal M)$ (this happens in the Cohen model), and you've proved $\mathfrak{j} \leq \mathrm{non}(\mathcal M)$. So it is consistent that $\mathfrak{j} < \mathfrak{z}$. If you feel there's some connection between $\mathfrak{j}$ and $\mathfrak{z}$, maybe Problem 3 should ask whether $\mathfrak{j} \leq \mathfrak{z}$. If you could prove this upper bound, it would also solve Problem 1, since $\mathfrak{z}$ and $\mathrm{non}(\mathcal M)$ are incomparable. $\endgroup$ – Will Brian Feb 21 '20 at 20:35
  • 2
    $\begingroup$ Actually, Alan Dow has proved (though it's unpublished) that $\mathfrak{z} = \aleph_1$ in the Laver model. But we have $\mathfrak{b} = \aleph_2$ in the Laver model and hence $\mathfrak{j} = \aleph_2$ as well. So $\mathfrak{z} < \mathfrak{j}$ is consistent. Combined with my previous comment, this shows there is no ZFC-provable inequality between $\mathfrak{j}$ and $\mathfrak{z}$. $\endgroup$ – Will Brian Feb 21 '20 at 20:42
2
+100
$\begingroup$

I can answer problems 2 and 3, although I still don't know the answer to problems 0 and 1. The main point is that

$\mathfrak{j}_{2:1} = \mathfrak{c}$ in the random model.

I'll sketch a proof of this below. (It's a bit long, but I've tried to make it readable.) The proof actually shows a little more: it gives you $\mathrm{cov}(\mathcal{N}) \leq \mathfrak{j}_{2:1}$.

This result also answers problem 3, because we know that $\mathfrak{z} = \aleph_1$ in the random model. (This was first proved by Alan Dow and David Fremlin here. It is also a corollary to Theorem 4.2 in this paper by me and Alan.) Therefore $\mathfrak{z} < \mathfrak{j}_{2:2},\mathfrak{j}_{2:1}$ is consistent. On the other hand, Koppelberg proved that $\mathfrak{z} \leq \mathrm{cov}(\mathcal{M})$. (Actually, she proved the dual statement in the category of Boolean algebras here. Stefan Geschke wrote a purely topological proof here.) Because you have proved that $\mathfrak{j}_{2:2},\mathfrak{j}_{2:1} \leq \mathrm{non}(\mathcal{M})$, and because $\mathrm{non}(\mathcal{M}) < \mathrm{cov}(\mathcal{M})$ in the Cohen model, it follows that $\mathfrak{j}_{2:2},\mathfrak{j}_{2:1} < \mathfrak{z}$ is consistent. Thus there is no inequality between $\mathfrak{z}$ and either of $\mathfrak{j}_{2:2}$ of $\mathfrak{j}_{2:1}$ that is provable in $\mathsf{ZFC}$.

(I know I gave a different argument for this in the comments. I don't like that argument as much because it relies on Alan's unpublished -- and mostly unwritten -- argument that $\mathfrak{z} = \aleph_1$ in the Laver model. I'm sure he's right. But I like that the argument here relies on the fact that $\mathfrak{z} = \aleph_1$ in the random model, and you can go read one or two proofs of this if you like.)

Now let's sketch the proof that $\mathfrak{j}_{2:1} = \mathfrak{c}$ in the random model. For the sake of clarity, I'm going to avoid forcing jargon and give a probabilistic argument that (I hope) will give you the right idea.

To show that $\mathfrak{j}_{2:1} = \mathfrak{c}$ in the random model, let's first recall how random real forcing works. Roughly, we imagine ourselves to live in a universe $V$ of sets, containing real numbers, subsets of $\mathbb N$, lots of $2$-to$1$ functions, and whatever else. But we know that our universe is about to get bigger -- this is the forcing -- by the introduction of a "truly random" real number $r$. The new, bigger universe is called $V[r]$.

The first observation I'd like to make is that all continuous measures on uncountable Polish spaces are essentially isomorphic. This means that it doesn't matter whether we view $r$ as a random element of $\mathbb R$, or of $[0,1]$, or of $2^\omega$ with the standard product measure, or whatever. For this problem, we want to view $r$ as an infinite sequence of random selections from larger and larger finite sets $I_n$, where $I_n$ has size $n!$. We select, at random, only a single element from each set. (This can be formalized by saying that we'd like $r$ to be a random element of the Polish space $\prod_{n = 0}^\infty \{1,2,\dots,n!\}$, equipped with the usual product measure. But let's keep it informal.) So our universe is about to get bigger by introducing a truly random sequence of selections from some sets $I_0, I_1, I_2, \dots$ with $|I_n| = n!$.

Within $V$, we can try to anticipate objects that will be constructible from $r$ in $V[r]$. For example, we can anticipate that once we get $r$, we can build a set $J \subseteq \mathbb N$ according to the following recipe: first identify $I_n$ with the interval $[1+1+2+\dots+(n-1)!,1+1+2+\dots+(n-1)!+n!) \subseteq \mathbb N$, and then let the $n^{\mathrm{th}}$ element of $J$ be whatever $r$ randomly selects from this interval.

Now I claim that this set $J$ described above has the following property: if $f$ is any $2$-to-$1$ function in the ground model $V$, then the restriction of $f$ to $J$ is almost-injective. To prove this, it suffices to argue that it's true with probability $1$, given that $r$ makes its selections randomly. This suffices because this is precisely what we mean when we say that $r$ is a "truly random" addition to $V$: if there is a randomness test defined in $V$ (such as one defined from any $f \in V$), then $r$ is random with respect to that test.

So let's argue probabilistically. Fix a $2$-to-$1$ function $f \in V$. If $f(a) = f(b)$, we may view this as a "guess" that $f$ is making about our set $J$: the guess is that $a$ and $b$ are both in $J$. In other words, $f$ gets to guess at pairs from $J$ infinitely many times, and it is our job to prove that, with probability $1$, only finitely many of these guesses are correct.

So what is the probability that $f$ correctly guesses a pair of elements from $J$? If $f$ identifies a member of some $I_m$ with a member of some $I_n$, where $m \neq n$, then there is a probability of exactly $\frac{1}{m!n!}$ that $f$ will have correctly guessed a pair from $J$. When $f$ makes other kinds of guesses (not identifying some member of some $I_m$ with a member of some $I_n$, where $m \neq n$), then the probability is $0$ that $f$ will have correctly guessed a pair from $J$.

If $m < n$, then $f$ gets at most $|I_m| = m!$ chances to guess a pair from $J$ with one member in $I_m$ and the other in $I_n$. By the previous paragraph, the probability of one of these guesses being correct is $\leq\! m!\frac{1}{m!n!} = \frac{1}{n!}$. Summing over all $n > m$, it follows that the probability of $f$ correctly guessing any pair of elements from $J$ with one member in $I_m$ and the other in $I_n$ for some $n > m$ is $$\leq\! \sum_{n = m+1}^\infty \frac{1}{n!} < \frac{1}{(m+1)!} \sum_{k = 0}^\infty \frac{1}{(m+1)^k} = \frac{1}{(m+1)!}\frac{m+1}{m} < \frac{1}{m!m}.$$

Now fix $k > 0$. Summing over all $m > k$, we see that the probability of $f$ correctly guessing a pair of elements from $J$ with one member in $I_m$ and the other in $I_n$ for some $n > m > k$ is $$\leq\! \sum_{m = k+1}^\infty \frac{1}{m!m} < \sum_{m = k+1}^\infty \frac{1}{m!} < \frac{1}{k!k}.$$

Therefore the probability of $f$ correctly guessing a pair of elements from $J \setminus (I_0 \cup \dots \cup I_k)$ is at most $\frac{1}{k!k}$. For any fixed $\varepsilon > 0$, we can choose $K$ large enough that $\sum_{k = K}^\infty \frac{1}{k!k} < \varepsilon$. This means that for $K$ large enough, the probability of $f$ correctly guessing more than ${K+1} \choose 2$ pairs of elements of $J$ is less than $\varepsilon$. Therefore the probability of $f$ correctly guessing infinitely many pairs of elements of $J$ is less than $\varepsilon$. As $\varepsilon$ was arbitrary, the probability of $f$ correctly guessing infinitely many pairs of elements of $J$ is $0$.

This shows that our set $J$ in $V[r]$ "should" (probabilistically) have the property that $f \restriction J$ is almost injective for every $f \in V$. But as we said earlier, this means $J$ really does have this property.

Why does this mean $\mathfrak{j}_{2:1} = \mathfrak{c}$ in the random model? The random model is $V[G]$, where $G$ is a "random" element of the measure algebra $2^{\aleph_2}$. If $\mathcal F$ is any set of $\aleph_1$ $2$-to-$1$ functions in $V[G]$, then a standard "nice names" argument shows that there is some weight-$\aleph_1$ subalgebra $X$ of $2^{\aleph_2}$ such that $\mathcal F$ is already in the intermediate model $V[X \cap G]$. Because $|X| = \aleph_1$, there will be random reals added in moving from the intermediate model $V[X \cap G]$ to the final model $V[G]$ -- random over $V[X \cap G]$, not just over $V$. We've just showed that the addition of these random reals adds some $J$ that "works" for every $f \in \mathcal F$.

Why does this mean $\mathrm{cov}(\mathcal{N}) \leq \mathfrak{j}_{2:1}$? There are a few ways to see this. The easiest is probably just to go through the above argument and convince yourself that what we've really proved is that every $2$-to-$1$ function $f$ is "solved" by a measure-$1$ set of $J$'s in the Polish space $\prod_{n = 0}^\infty \{1,2,\dots,n!\}$. Equivalently, the set of $J$'s that fail to work for a given $2$-to-$1$ function $f$ is a null set $N_f$. Therefore, if $\mathcal F$ is any size $<\! \mathrm{cov}(\mathcal{N})$ family of $2$-to-$1$ functions, $\bigcup_{f \in \mathcal F}N_f$ does not cover our Polish space, and so there is some $J$ that works for every $f \in \mathcal F$.

$\endgroup$
  • $\begingroup$ Thank you Will, very much, for the detail explanation. But if I understood correctly, everything follows from the lower bound $\mathrm{cov}(\mathcal N)\le j_{2:1}$ which holds in ZFC. And then we can just apply the know information (see the Table 4 in the Blass' survey) that $\mathrm{cov}(\mathcal N)=\mathfrak c$ in the Random Model. Right? $\endgroup$ – Taras Banakh Feb 25 '20 at 15:59
  • $\begingroup$ Yes, that's right. We prove the lower bound by considering the construction of $J$ from a random sequence as described above, and then showing that a "sufficiently random" sequence makes $J$ work for a given $2$-to-$1$ function. To be honest, I phrased the whole thing in terms of forcing because that's how I thought of it, and by the time realized the argument can be modified to give us a ZFC inequality, I'd already written most of it down and didn't have the energy to go back and modify it too much! $\endgroup$ – Will Brian Feb 25 '20 at 16:09
  • 2
    $\begingroup$ @TarasBanakh: You would be correct if $J$ were defined by just randomly deciding (via a coin flip, for example) with probability $\frac{1}{2}$ whether any given integer is in $J$. This is what is often meant by "a random real" and it won't work here for the reason you state. Our set $J$ is constructed differently, by selecting just one member of each interval $I_k$, where $|I_k| = k!$. The probability that some particular $n$ is in our set $J$ is equal to $\frac{1}{k!}$, where $k$ is the unique number with $n \in I_k$. So the probability of selecting the doubleton $\{2n,2n+1\}$ is very small. $\endgroup$ – Will Brian Feb 25 '20 at 16:33
  • 1
    $\begingroup$ The lower bound $\mathrm{cov}(\mathcal N)\le \mathfrak j_{2:1}$ cannot be improved to $\mathrm{cov}(\mathcal E)\le\mathfrak j_{2:1}$ as it would imply the lower bound $\mathrm{cov}(\mathcal M)\le\mathrm{non}(\mathcal M)$ which does not hold in ZFC. $\endgroup$ – Taras Banakh Feb 25 '20 at 16:52
  • 2
    $\begingroup$ A good reference for that sort of question is the book by Bartoszynski and Judah -- Chapter 7 shows you how to separate any two cardinals in Cichon's diagram. There are three ways listed to get $\mathfrak{b},\mathrm{cov}(\mathcal N) < \mathrm{non}(\mathcal M)$, although none of them is particularly simple to describe. I would imagine all of them have $\mathfrak{s} = \mathfrak{b}$, although this isn't stated explicitly in the text. I'm not sure what the $\mathfrak{j}$'s would be in these models, but I think that would be a good place to look. $\endgroup$ – Will Brian Feb 25 '20 at 17:20

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.