Putting $\omega$ into $\alpha$ boxes where $\alpha \in \big(\omega\cup\{\omega\}\big)\setminus\{0,1\}$

Question

This is a follow-up question to an older question.

Let $\alpha \in \big(\omega\cup\{\omega\}\big) \setminus \{0,1\}$ be an ordinal. We say that a function $f: \omega \to \alpha$ is fair if $$|f^{-1}(\{j\})| = \aleph_0$$ for all $j\in\alpha$.

We call a set ${\frak F}$ of fair functions $f:\omega\to\alpha$ equalising for $\alpha$ if for all $a,b\in\omega$ there is $f\in{\frak F}$ with $f(a) = f(b)$. Let $B_\alpha$ be the minimum cardinality that an set equalising for $\alpha$ can have. This post establishes $B_2 \leq 3$.

Question. Can an explicit value for $B_\alpha$ be given for $\alpha \in \big(\omega\cup\{\omega\}\big) \setminus \{0,1\}$? I am particularly interested in $B_\omega$.

Answer 1

$B_\alpha = 3$ for every $\alpha \in (\omega \cup \{\omega\}) \setminus \{0,1\}$. Here is a construction that shows $B_\alpha \le 3$.

1. Let $g : \mathbb{N} \to \alpha$ be any function such that $g^{-1}(\{j\})$ is infinite for all $j \in \alpha$.
2. Let $h$ be any bijection from $\omega$ to $\{0,1,2\} \times \mathbb{N}$.
3. For $i \in \{0,1,2\}$ define $t_i : \{0,1,2\} \times \mathbb{N} \to \alpha$ as follows: $$t_i(r,s) = \begin{cases} g(s) & \text{if } i=r \\ 0 & \text{otherwise} \end{cases}$$ and define $f_i : \omega \to \alpha$ by $f_i = t_i \circ h$.

The functions $f_i$ are fair. In fact, $f_i^{-1}(\{j\}) = h^{-1} (t_i^{-1} (\{j\}))$, which is an infinite set because $h$ is a bijection and $t_i^{-1}(\{j\})$ contains $\{i\} \times g^{-1}(\{j\})$. The set $\{f_0,f_1,f_2\}$ is equalising for $\alpha$ because for all $a,b \in \omega$, if $h(a) = (r_a,s_a)$ and $h(b) = (r_b,s_b)$, then for any $i \not\in \{r_a,r_b\}$ we have $f_i(a)=f_i(b)=0$.

The reasoning used to show $B_2 > 2$ in the answer to this question extends to show $B_\alpha > 2$ for all $\alpha > 1$. Hence $B_\alpha = 3$ for all $\alpha \in (\omega \cup \{\omega\}) \setminus \{0,1\}$.

Answer 2

Let us first reduce this problem from an infinite combinatorics problem to a finite combinatorics problem.

Suppose that $g_{0},\dots,g_{n-1}:\omega\rightarrow\alpha$ are functions such that $g_{i}^{-1}[\{j\}]$ is infinite for each $m<\alpha$. Then let $\simeq$ be the congruence on $\omega$ where we set $x\simeq y$ iff $g_{i}(x)=g_{i}(y)$ for each $i$. Then let $X=\omega/\simeq$, and let $f_{i}:X\rightarrow\alpha$ be the surjective function where $f_{i}([x])=f_{i}(x)$. Then $X$ is a finite set with $|X|\leq\alpha^{n}$, each mapping $g_{i}:X\rightarrow\alpha$ is surjective, and whenever $x,y\in X$, there is some $i$ where $f_{i}(x)=f_{i}(y)$.

Fact: For $\alpha<\omega$, $B_{\alpha}$ is the least natural number $n$ such that there exists a finite set $X$ and surjective functions $f_{0},\dots,f_{n-1}:X\rightarrow\alpha$ such that if $x,y\in X$, then $f_{i}(x)=f_{i}(y)$ for some $i$.

We can use the probabilistic method to get upper bounds for $B_{\alpha}$ for all finite $\alpha$. I have made no attempt to optimize these upper bounds since I just wanted to use the probabilistic method and I want to see how much the other answerers can beat my probabilistic method technique.

Functions selected at random

Let $r$ be a natural number. Suppose that $X$ is a finite set and $\alpha$ is a finite ordinal. Let $f_{0},\dots,f_{n-1}:X\rightarrow\alpha$ be functions selected independently uniformly at random. Let $x,y\in X,x\neq y$ be selected at random.

Then for random $i$, we have $P(f_{i}(x)\neq f_{i}(y))=\frac{\alpha-1}{\alpha}$. Therefore, by the independence of the functions $f_{i}$, we know that $P(\forall i,f_{i}(x)\neq f_{i}(y))=(\frac{\alpha-1}{\alpha})^{n}$. Therefore, $$P(\exists x,y((x\neq y)\wedge\forall i,f_{i}(x)\neq f_{i}(y)))\leq\frac{|X|(|X|-1)}{2}\cdot(\frac{\alpha-1}{\alpha})^{n}$$.

Now, the number of functions from $X$ to $\alpha$ is $\alpha^{r}$ while the number of surjections from $X$ to $\alpha$ is $$\sum_{k=1}^{\alpha}(-1)^{\alpha-k}\binom{\alpha}{k}k^{r}$$.

Therefore, the probability that a randomly selected function from $X$ to $\alpha$ is surjective is $$\sum_{k=1}^{\alpha}(-1)^{\alpha-k}\binom{\alpha}{k}\big{(}\frac{k}{\alpha}\big{)}^{|X|}$$.

That is a complicated formula, so let's just work with an approximation.

The set of all functions $f:X\rightarrow\alpha$ with $i\not\in f[X]$ has cardinality $(\alpha-1)^{r}$. Therefore, the probability that $i\not\in f[X]$ is $(\frac{\alpha-1}{\alpha})^{r}$. Therefore, the probability that $f$ is not surjective is at most $\alpha\cdot(\frac{\alpha-1}{\alpha})^{r}$. Therefore, the probability that some $f_{i}$ is non-surjective is at most $$n\alpha\cdot(\frac{\alpha-1}{\alpha})^{r}.$$

We conclude that the probability that either some $f_{i}$ is non-surjective or there exists some $x,y$ where for all $i$, we have $f_{i}(x)=f_{i}(y)$ is at most $$n\alpha\cdot(\frac{\alpha-1}{\alpha})^{r}+\frac{r(r-1)}{2}\cdot(\frac{\alpha-1}{\alpha})^{n}.$$

Therefore, if we select $n$ and $|X|$ such that $$n\alpha\cdot(\frac{\alpha-1}{\alpha})^{r}+\frac{r(r-1)}{2}\cdot(\frac{\alpha-1}{\alpha})^{n}<1,$$ then we know that there are $f_{0},\dots,f_{n-1}$ where each $f_{i}$ is surjective and where for all $x,y$, there is some $i$ with $f_{i}(x)=f_{i}(y)$.

A modified distribution where functions are surjective

Let us now change the distribution of the functions $f_{0},\dots,f_{n-1}$ in order to guarantee that these functions are surjective.

Suppose that $X$ is a set where $|X|=r$. Let $A_{0},\dots,A_{n-1}$ be randomly selected subsets of $X$ of cardinality $\alpha$. Let $g_{i}:A_{i}\rightarrow\alpha$ be a random bijection for $0\leq i<n$, and let $h_{i}:X\setminus A_{i}\rightarrow\alpha$ for all $i$. Let $f_{i}:X\rightarrow\alpha$ be the function where $f_{i}=g_{i}\cup h_{i}$ for all $i$. We have now guaranteed that each function $f_{i}$ is surjective.

Let us now run the same calculation as before.

Suppose $x,y\in X$ are randomly selected with $x\neq y$. Suppose now that $0\leq i<n$ is selected at random. Then $P(x,y\in A_{i})=(\frac{\alpha}{|X|})^{2}$ and in this case $f_{i}(x)\neq f_{i}(y)$. Now, $$P(f_{i}(x)=f_{i}(y)|x\not\in A_{i}\text{ or }y\not\in A_{i})=\frac{1}{\alpha}.$$

Therefore, $$P(f_{i}(x)=f_{i}(y))=[1-(\frac{\alpha}{r})^{2}\cdot\frac{1}{\alpha}$$, and $$P(f_{i}(x)\neq f_{i}(y))=1+\frac{\alpha}{r^{2}}-\frac{1}{\alpha}.$$

Therefore, for randomly selected $x,y,x\neq y$, $$P(\forall i,f_{i}(x)\neq f_{i}(y))=(1+\frac{\alpha}{r^{2}}-\frac{1}{\alpha})^{n}.$$

Therefore, $$P(\exists x,y(x\neq y)\wedge\forall i,f_{i}(x)\neq f_{i}(y)) \leq\frac{r\cdot(r-1)}{2}(1+\frac{\alpha}{r^{2}}-\frac{1}{\alpha})^{n}.$$

Thus, if $r,n$ are selected such that $$\frac{r\cdot(r-1)}{2}(1+\frac{\alpha}{r^{2}}-\frac{1}{\alpha})^{n}<1$$, then we know that we can select surjective $f_{0},\dots,f_{n-1}$ such that if $x\neq y$, then there is some $i$ with $f_{i}(x)=f_{i}(y)$. We may now solve this inequality to obtain:

$$n>\frac{\ln(2)-\ln(r)-\ln(r+1)}{\ln(r^{2}\alpha+\alpha-r^{2})-\log(r^{2}\alpha)}$$.

Therefore, if $\alpha,r,n$ are integers with $r>\alpha$ and $$n>\frac{\ln(r)+\ln(r+1)-\ln(2)}{\log(r^{2}\alpha)-\ln(r^{2}\alpha+\alpha-r^{2})},$$ then $B_{\alpha}<n$.

Answer 3

The method from this answer leads to $B_\alpha\le\binom{\alpha+1}{2}$ for finite $\alpha$. Split $\omega$ into $\alpha+1$ infinite sets, say $X_i=\{n:n\equiv i \pmod{\alpha+1}\}$. For each $p\in[\alpha+1]^2$ let $f_p$ be constant on each $X_i$, with value $0$ if $i\in p$ and such that $f_p:\omega\to\alpha$ is surjective (that is why we have $\alpha+1$ sets). If $a\neq b$ then $\{a,b\}\subset X_i$ for some $i$ and we have $f_p(a)=f_p(b)$ for all $p$, or there are distinct $i$ and $j$ with $a\in X_i$ and $b\in X_j$ but then $f_p(a)=f_p(b)=0$ where $p=\{i,j\}$.