# Find cardinality of $B = \left\{ f : \mathbb N \rightarrow \mathbb N \mid \forall n. f(n)\le n) \wedge \forall m\; \exists n( f(n) > m) \right\}$

Find cardinality of $$B = \left\{ f : \mathbb N \rightarrow \mathbb N \mid \forall n(f(n)\le n) \wedge \forall m\; \exists n (f(n) > m) \right\}$$

## My try

I have solved this, but I am not sure if it is correct (I have not a lot of experience in set theory). Can somebody check that or give some tips (or both)?
$$|B| < \mathfrak{c}$$ because $$|B| < |\mathbb N|^{|\mathbb N|}$$
from the other hand I can define $$G$$ injective such as:
$$G: (\mathbb N \rightarrow \left\{0,1 \right\}) \rightarrow B$$ $$G(\alpha)(n) = \begin{cases} \alpha(n) + G(\alpha)(n-1), &\text{if }n \neq 0 \\ 0, &\text{if }n = 0. \end{cases}$$

The function $$G$$ increases and is injective, and its power is $$\mathfrak{c}$$ so $$|B| = \mathfrak{c}$$

• Note that if $\alpha$ takes the value $1$ only finitely many times, then $G(\alpha) \notin B$. – Mees de Vries Jan 30 at 16:26
• Why do you say $|B| < |\mathbb{N}|^{|\mathbb{N}|}$? – Clive Newstead Jan 30 at 17:06
• It's stil not clear what is $\mathfrak{c}$, it should be defined when first used. Which power of $G$ ? – Soleil Jan 30 at 18:21
• continuum - why is it not clear? – VirtualUser Jan 30 at 18:35
• @VirtualUser Because it s not defined in usual set theory / decriptive set theory books, and you did not defined it. Hence $\mathfrak{c}:= 2^{\mathbb N} = \aleph_1$. – Soleil Jan 30 at 18:48

$$B$$ is the set of functions $$\mathbb{N} \to \mathbb{N}$$ that are unbounded in absolute terms, but are bounded by the identity function.
Evidently $$|B| \le \mathfrak{c}$$ since $$B$$ is a subset of $$\mathbb{N}^{\mathbb{N}}$$.
To see that $$\mathfrak{c} \le |B|$$, let $$\mathcal{P}_{\mathsf{inf}}(\mathbb{N}) \subseteq \mathcal{P}(\mathbb{N})$$ be the set of infinite subsets of $$\mathbb{N}$$. Then $$|\mathcal{P}_{\mathsf{inf}}(\mathbb{N})| = \mathfrak{c}$$, since the set of all finite subsets of $$\mathbb{\mathbb{N}}$$ is countable.
For each $$U \in \mathcal{P}_{\mathsf{inf}}(\mathbb{N})$$, define $$f_U \in B$$ inductively by $$f_U(0) = 0 \quad \text{and} \quad f_U(n+1) = \begin{cases} f_U(n) & \text{if } n \not\in U \\ f_U(n)+1 & \text{if } n \in U \end{cases}$$
The fact that $$f_U$$ is unbounded follows from the fact that $$U$$ is infinite. You can prove by induction that $$f_U(n) \le n$$ for all $$n \in \mathbb{N}$$, and that $$U \mapsto f_U$$ defines an injection $$\mathcal{P}_{\mathsf{inf}}(\mathbb{N}) \to B$$.
Hence $$\mathfrak{c} \le |B|$$.