# Are these sets of functions finite?

Can there be a set of functions $$S\subseteq\{f \mid f:\mathbb{N}\to\mathbb{N}\}$$ of cardinality $$\mathfrak{c}$$ (real numbers) such that the set $$S_f:=\{g \in S \mid g(n)\leq f(n), \forall n \in \mathbb{N}\}$$ is finite for all $$f:\mathbb{N}\to \mathbb{N}$$?

My intuition says no, since there have to be uncountably many $$f$$s in $$S$$ that take a certain value at each $$n\in\mathbb{N}$$. How would you prove this?

• Do you mean $S_f$ is finite for all $f$ or do you mean $S_f$ is finite for all $f\in S$?
– user1318062
Commented May 5 at 1:02
• If you mean for all $f$ then the answer is no by the diagonal argument, if you mean for all $f\in S$ the answer is yes.
– user1318062
Commented May 5 at 1:21

Assume $$S$$ is uncountable.

Then there is some $$N\in \mathbb{N}$$ such that $$g(0) \leq N$$ for uncountably many $$g\in S$$. Let $$f(0)$$ be the smallest such $$N$$, define $$S_0$$ to be the set of all $$g \in S$$ such that $$g(0) \leq f(0)$$, and choose $$g_0 \in S_0$$.

Inductively perform the following:

• Note that there is some $$N$$ such that $$g(n) \leq N$$ for uncountably many $$g\in S_{n-1}$$. Let $$N_n$$ be the smallest such $$N$$ and define $$f(n) = N_n + \sum_{k=0}^{n-1}g_k(n)$$
• Define $$S_n$$ to be the set of all $$g \in S_{n-1}$$ such that $$g(n) \leq f(n)$$. Note that $$S_n$$ is uncountable and $$g_k \in S_n$$ for every $$k < n$$.
• Choose $$g_n \in S_n$$ such that $$g_n \neq g_k$$ for any $$k < n$$.

For such an $$f$$, $$S_f \supseteq \{g_k : k \in \mathbb{N}\}$$, so $$S_f$$ is not finite.

I initially read the condition on $$S_f$$ as $$S_f$$ is finite for each $$f \in S$$. With that [mis]reading, we have the following example:

For each subset $$A \subseteq \mathbb{N}$$ define the function $$f_A$$ by $$k \in A \implies f(2k) = 0, f(2k+1) = 2 \\ k \not\in A \implies f(2k)=f(2k+1) = 1$$

Then $$S = \{f_A : A \subseteq \mathbb{N}\}$$ is an antichain (i.e. $$|S_f|=1$$ for each $$f \in S$$) which is equipotent with $$\mathcal{P}(\mathbb{N})$$, which is uncountable.

• I had the same idea but instead I had $f$ the indicator function of $A$ and $g$ the indicator function of $A^c$ and then put them together. But as it stands $f$ is unrestricted so there is no such $S$.
– user1318062
Commented May 5 at 1:27

For $$N\subset\mathbb{N}$$ let $$f_N(n+1)=\mathbb{1}_{n\in N}$$ where $$\mathbb{1}_{n\in N}$$ is $$1$$ if $$n\in N$$ and $$0$$ else and let $$f_N(0)=-\vert N \vert.$$ Now let $$S=\{f_N:N\subset\mathbb{N}\}.$$ Clearly for $$N,M\subset\mathbb{N}$$ with $$N\neq M$$ we have $$f_N\not\le f_M\text{ and } f_M\not\le f_N$$ so $$\vert S_{f_N}\vert=1$$ for all $$N\subset\mathbb{N}$$.