2
$\begingroup$

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}$

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

$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|$.

$\endgroup$

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.