# Is $\mathfrak j_{2:1}=\mathfrak{j}_{2:2}$ in ZFC?

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?

• 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. – Will Brian Feb 21 '20 at 20:35
• 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}$. – Will Brian Feb 21 '20 at 20:42

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

• 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? – Taras Banakh Feb 25 '20 at 15:59
• 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! – Will Brian Feb 25 '20 at 16:09
• @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. – Will Brian Feb 25 '20 at 16:33
• 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. – Taras Banakh Feb 25 '20 at 16:52
• 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. – Will Brian Feb 25 '20 at 17:20