Infinite wacky race

Question

Dick Dastardly is taking part in an infinite wacky race. What is infinite about it, you ask? Well, just everything! There are infinitely many racers, every one of which can run infinitely fast and the finish line is infinitely far away.

To be more precise, the race will take place on the natural numbers, starting at zero. At every moment in time, every player can move further from its position to any natural number. However, Dick has an advantage: the power of cheating! Every racer he overtakes will be snatched by one of his traps and be out of the race for good.

What is the largest number of racers $\Delta$ Dick be sure to win against?

---

For the sake of clarity, say Dick and the rest of the racers alternate movements, i.e., first every player moves, then Dick moves, then it repeats.

So, for instance, if Dick is racing against countably many people, he is sure to win. All he has to do is number the racers and, at the $n$th moment, overtake the $n$th racer.

If there are continuum many people, however, he may lose the race. In fact, for every increasing sequence of natural numbers there might be a racer following its positions, so that we are guaranteed to have a racer who is always in front of Dick.

This already tells us $\aleph_0\le \Delta<\mathfrak c:=2^{\aleph_0}$ (check small cardinals) and the answer to this question is probably independent of ZFC.

Answer 1

As I understand it, the question is about the following game $G(\kappa)$ of length $\omega$ played on a set $S$ of cardinality $\kappa$. At the $n^\text{th}$ turn, first White chooses a function $\varphi_n:S\to\mathbb N$, and then Black (a.k.a. Dick) chooses a number $k_n\in\mathbb N$; Black wins if $\forall x\in S\ \exists n\in\mathbb N\ \varphi_n(x)\le k_n$. (More colorfully: at each turn, White cuts what's left of $S$ into countably many pieces, and Black eats any finite number of those pieces; Black wins if he ends up eating the whole thing.) For small values of $\kappa=|S|$ Black has a winning strategy, for large values White has a winning strategy, and for in-between values (if any) the game is undetermined. We want to find the cutoff points.

In the notation of Cichoń's diagram, $\mathfrak d$ is the minimum cardinality of a family of functions $F\subseteq\mathbb N^\mathbb N$ such that $\forall g\in\mathbb N^\mathbb N\ \exists f\in F\ \forall n\in\mathbb N\ g(n)\lt f(n)$, and $\operatorname{non}(\mathcal B)$ is the minimum cardinality of a non-meager (second category) set of real numbers. The "small uncountable cardinals" $\mathfrak d$ and $\operatorname{non}(\mathcal B)$ are "incomparable" in the sense that either one may be smaller than the other, or they may be equal.

As already shown in an answer by Alex Kruckman, if $\kappa\ge\mathfrak d$ then White has a winning strategy in $G(\kappa)$. I claim that the converse also holds, i.e., White has a winning strategy in $G(\kappa)$ if and only if $\kappa\ge\mathfrak d$. If Black has a winning strategy, it follows from Kruckman's observation that $\kappa\lt\mathfrak d$; I claim that we also have $\kappa\lt\operatorname{non}(\mathcal B)$, i.e., if Black has a winning strategy in $G(\kappa)$ then $\kappa\lt\min\{\mathfrak d,\operatorname{non}(\mathcal B)\}$. Of course Black has a winning strategy if $\kappa\le\aleph_0$, as was already noted by the OP. These observations (if correct) leave open what happens if $\aleph_1\le\kappa\lt\min\{\mathfrak d,\operatorname{non}(\mathcal B)\}$. It's easy to see that the least cardinal $\kappa$ for which Black has no winning strategy must have uncountable cofinality.

Theorem 1. White has a winning strategy in $G(\kappa)$ if and only if $\kappa\ge\mathfrak d$.

Proof. If $|S|=\kappa\ge\mathfrak d$ then we can choose functions $f_x\in\mathbb N^\mathbb N$ such that $\forall g\in\mathbb N^\mathbb N\ \exists x\in S\ \forall n\in\mathbb N\ g(n)\lt f_x(n)$. Now a winning strategy for White is to play $\varphi_n(x)=f_x(n)$ regardless of what Black does.

Conversely, suppose White has a winning strategy $\sigma$ in $G(\kappa)$; that is, on the $n^\text{th}$ turn, at each $x\in X$ White plays $\varphi_n(x)=\sigma(x;k_1,\dots,k_{n-1})$ where $k_1,\dots,k_{n-1}$ are the previous moves by Black. Now for each $x\in X$ define $f_x(n)$ recursively so that $$f_x(n)=\max\{\sigma(x;k_1,\dots,k_{n-1}):k_i\lt f_x(i)\text{ for }i=1,\dots,n-1\}.$$ Thus $f_x(n)$ is at least as big as any number that the strategy $\sigma$ will ever assign to $x$ at the $n^\text{th}$ turn, provided $x$ has not already been "eaten". I claim that $\{f_x:x\in S\}$ is a "dominating family", whence $|S|\ge\mathfrak d$. Cosider any function $g:\mathbb N\to\mathbb N$. Since $\sigma$ is a winning strategy for White, there is a point $x\in S$ which "survives" a play $\varphi_1,k_1,\varphi_2,k_2,\dots$ in which White follows the strategy $\sigma$ and Black plays $k_n=g(n)$. Then for all $n\in\mathbb N$ we have (by induction on $n$) $f_x(n)\ge\sigma(x;k_1,\dots,k_{n-1})=\varphi_n(x)\gt k_n=g(n)$.

Theorem 2. If Black has a winning strategy in $G(\kappa)$ then $\kappa\lt\min\{\mathfrak d,\operatorname{non}(\mathcal B)\}$.

Proof. Suppose Black has a winning strategy in $G(\kappa)$. Plainly $\kappa\lt\mathfrak d\le\mathfrak c$ by Theorem 1; Black and White can't both have winning strategies. Now assume for a contradiction that $\kappa\ge\operatorname{non}(\mathcal B)$. We may assume that the game is played on a non-meager set $S\subseteq\mathbb R$ of cardinality $\kappa$, and we may assume that $S\cap\mathbb Q=\varnothing$.

Let $\sigma$ be a fixed winning strategy for Black. We consider only plays in which Black follows the strategy $\sigma$ and White's moves are restricted as follows: At the $n^\text{th}$ turn White chooses a number $q_n\in\mathbb Q$ and plays the function $\varphi_n:S\to\mathbb N$ defined by $\varphi_n(x)=\left\lceil\frac1{|x-q_n|}\right\rceil$. With Black following the fixed strategy $\sigma$, the play of the game is determined by White's chosen sequence of rational numbers $q_1,q_2,q_3,\dots$.

If $q_1,\dots,q_n$ is a sequence of rational numbers, let $S_{q_1,\dots,q_n}$ be the set of points $x\in S$ which are "doomed" after White has chosen $q_1,\dots,q_n$, that is, Black (following his strategy $\sigma$) is sure to "eat" $x$ at the next turn, regardless of White's choice of $q_{n+1}$. Since $\sigma$ is a winning strategy, each point $x\in S$ is in some set $S_{q_1,\dots,q_n}$; otherwise White could play so that $x$ is never "eaten". So $S$ is the union of the (countably many) sets $S_{q_1,\dots,q_n}$. Since $S$ is non-meager, there is some sequence $q_1,\dots,q_n$ such that the set $S_{q_1,\dots,q_n}$ is dense in some interval $I$. After White's moves $q_1,\dots,q_n$, every point in $S_{q_1,\dots,q_n}$ is "doomed" to be eaten on the next turn. However, if White chooses $q_{n+1}\in\mathbb Q\cap I$ this is impossible, since $\varphi_{n+1}(x)$ is unbounded on $S_{q_1,\dots,q_n}\cap I$

Answer 2

It turns out I misunderstood the question, so my answer addresses a different, but related, problem. I'll leave it up anyway, since it might be of interest to some readers.

---

Every non-empty set of cardinals has a least element, but it is not true that every non-empty set of cardinals has a greatest element. Thus it is preferable to ask "what is the least cardinal $\kappa$ such that there exists a set of racers of cardinality $\kappa$ which Dick cannot win against?" rather than "what is the greatest cardinal $\kappa$ such that Dick can win against every set of racers of cardinality $\kappa$?"

Thus, I am interpreting your question as follows: What is the least cardinal $\kappa$ with the property that there exists a set $S$ of non-decreasing sequences with $|S| = \kappa$ such that for all non-decreasing $d$, there exists $f\in S$ such that for all $t\in \mathbb{N}$, $d(t) \leq f(t)$?

---

In fact, this cardinal $\kappa$ is the dominating number $\mathfrak{d}$, so its exact value is independent of ZFC, as you suspected.

Recall that for $f,g\in \mathbb{N}^\mathbb{N}$, we write $f\leq^* g$ if for all but finitely many $n\in \mathbb{N}$, $f(n)\leq g(n)$. We say a family of functions $D\subseteq \mathbb{N}^{\mathbb{N}}$ is dominating if for all $f\colon \mathbb{N}\to \mathbb{N}$, there exists $g\in D$ such that $f\leq^* g$. And $\mathfrak{d}$ is the smallest cardinality of a dominating family. It is straightforward to show that $\aleph_0<\mathfrak{d}\leq 2^{\aleph_0}$. It is more difficult to show that it is consistent with ZFC that $\aleph_0<\mathfrak{d} < 2^{\aleph_0}$.

---

Note that for any function $f\colon \mathbb{N}\to \mathbb{N}$, we can define a non-decreasing function $\hat{f}\colon \mathbb{N}\to \mathbb{N}$ with $f(n)\leq \hat{f}(n)$ for all $n$ by defining $\hat{f}(0) = f(0)$ and $\hat{f}(n+1) = \max(f(n),f(n+1))$.

Suppose $D$ is a dominating family. Define $S = \{\hat{g}+n\mid g\in D,n\in \mathbb{N}\}$, and note that $|S| = |D|$. I claim that $S$ is a winning set of racers. Let $d\colon \mathbb{N}\to \mathbb{N}$ be non-decreasing. Then there exists $g\in D$ such that $d\leq^* g$. If $d(t)\leq g(t)$ for all $t\in \mathbb{N}$, let $n = 0$. Otherwise, let $n = \max_{t\in \mathbb{N}} d(t)-g(t)$ (noting that $d(t)-g(t)$ is positive for only finitely many $t$, so the maximum exists). Now $\hat{g}+n\in S$, and for all $t\in \mathbb{N}$, $d(t)=g(t)+(d(t)-g(t)) \leq g(t)+n\leq \hat{g}(t)+n$, so Dirk always loses the race. Since $|S| = |D|$, this shows that $\kappa\leq \mathfrak{d}$.

Now suppose $S$ is a winning set of racers. I claim that $S$ itself is a dominating family. Let $g\colon \mathbb{N}\to \mathbb{N}$. We let Dirk race as $\hat{g}$. Then there exists $f\in S$ such that $\hat{g}(t)\leq f(t)$ for all $t\in \mathbb{N}$. In particular, $g(t)\leq \hat{g}(t)\leq f(t)$ for all $t\in \mathbb{N}$, so $g\leq^* f$. Thus $S$ is dominating. This shows $\mathfrak{d}\leq \kappa$.

Putting together the previous two paragraphs, we have shown $\kappa = \mathfrak{d}$.

---

Really, what the argument above shows is that in the definition of $\mathfrak{d}$, it would be equivalent to work with non-decreasing functions instead of arbitrary functions, and it would be equivalent to work with the order $f\leq g$ (defined by $\forall t\in \mathbb{N}$, $f(t)\leq g(t)$) instead of $f\leq^* g$. The reason why $\mathfrak{d}$ is usually defined in terms of $\leq^*$ is that the bounding number $\mathfrak{b}$, a "small cardinal" with a closely related definition, must be defined in terms of $\leq^*$, not $\leq$, in order to be non-trivial.