This should be fun.

Let $\mathfrak{sd}$ be the least cardinal $\kappa$ such that there exists $\langle s_i : i < \kappa \rangle$ satisfying the following.

(1) Each $s_i: \omega^{\omega} \to \omega^{\omega}$.

(2) For every $n$, knowing $n$ bits of input gives you $n+1$ bits of output for each $s_i$ - i.e., for every $x, y \in \omega^{\omega}$, if $x \upharpoonright n = y \upharpoonright n$ then $s_i(x) \upharpoonright (n+1) = s_i(y) \upharpoonright (n+1)$.

(3) For every $x \in \omega^{\omega}$ there is some $i < \kappa$ such that $s_i(x)$ dominates $x$, i.e., $|\{n< \omega: s_i(x)(n) \leq x(n)\}| < \omega$.

Must $\mathfrak{sd} = \mathfrak{d} = $ least size of a family $F \subseteq \omega^{\omega}$ such that $(\forall x \in \omega^{\omega})(\exists y \in F)(|\{n < \omega: y(n) \leq x(n)\}| < \omega)$?

Here's some history.

  • $\begingroup$ I am sorry. Hopefully all the typos are fixed now. $\endgroup$ – hot_queen May 15 '15 at 23:56

Temporarily consider one fixed "strategy" $s_i$, consider one fixed natural number $n$, consider one sequence $t$ of $n$ natural numbers, and consider the set $M(i,n,t)$ of all the functions $x:\omega\to\omega$ such that $x(k)=t(k)$ for all $k<n$ and $x(k)\leq s_i(x)$ for all $k\geq n$. I claim that the functions $x\in M(i,n,t)$ are all majorized (everywhere, not just eventually) by a single function $f_{i,n,t}$. Namely, let $f_{i,n,t}$ agree with $t$ at the first $n$ arguments $k$, and then, for larger $k$ define $f_{i,n,t}(k)$ inductively as follows. Consider all the finite sequences of length $k-1$ that are majorized by the initial segment of $f_{i,n,t}$ of length $k-1$; apply $s_i$ to all those finite sequences, and let $f_{i,n,t}(k)$ be larger than all the (finitely many) outputs produced by $s_i$.

Now un-fix $i$, $n$, and $t$. If the functions $s_i$ are as in your definition of $\mathfrak{sd}$, then every $x:\omega\to\omega$ is in $M(i,n,t)$ for some $i<\kappa$, some $n\in\omega$ and some $t\in{}^n\omega$. So the functions $f_{i,n,t}$ constitute a dominating family. Since there are only countably many $n$"s and $t$'s, this dominating family has size only $\mathfrak{sd}$. So $\mathfrak d\leq\mathfrak{sd}$.

The reverse inequality is trivial as you can take all the $s_i$'s to be constant.

  • 1
    $\begingroup$ In "apply $s_i$ to all those finite sequences, I was tacitly thinking of $s_i$, by virtue of your requirement 2, as taking finite sequences of length $k-1$ as inputs and producing sequences of length $k$ as outputs, and in particular producing as outputs the last components of those sequences. $\endgroup$ – Andreas Blass May 16 '15 at 2:10
  • 2
    $\begingroup$ Although I'm responsible for a few multi-character names of cardinal characteristics, I would advise against combinations like $\mathfrak{sd}$ that can be easily read as the product of $\mathfrak{s}$ and $\mathfrak{d}$ (thereby making the question really easy.) $\endgroup$ – Andreas Blass May 16 '15 at 2:12
  • $\begingroup$ $~$Thanks! $~~$ $\endgroup$ – hot_queen May 18 '15 at 20:00

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.