# Find the cardinality of $A= \left\{ f : \mathbb N \rightarrow \mathbb N \mid \forall x:f(x)\le x\right\}$

How can I solve tasks like this one?

Find the cardinality of $$A= \left\{ f : \mathbb N \rightarrow \mathbb N \mid \forall x:f(x)\le x\right\}.$$

I know that $$|A| \le \mathfrak{c}$$ but how to deal with lower bound?

• The term in English is "cardinality" not "power" – ℋolo Jan 30 '19 at 15:00
• @Holo On the contrary, "power" is also a common expression for cardinality. – Andrés E. Caicedo Jan 30 '19 at 15:04
• @AndrésE.Caicedo really? Because when I only started studying set theory I used power, and couldn't find almost anything. You learn something new every day – ℋolo Jan 30 '19 at 15:08
• Interesting. I have never heard the word "power" used for "cardinality." – Matematleta Jan 30 '19 at 15:14

Notice that the set $$\{f:\Bbb N\to\{0,1\}\mid f(0)=0\}=B⊆A$$, so $$|A|≥|B|=2^{|\Bbb N|}=\frak c$$
• Ah, it is really clever. I am learning how to solve tasks like that. There I can find subset of my set and it works. Can you tell me - can I use similar trick as you showed in finding cardinality of $B = \left\{ f \in A | S(f,\mathbb N) \right\}$ where $S(f,C)$ means that $f$ is surjective to $C$? I suspect that no because I can't define surjective by one "prefunction" but maybe I am wrong – user617243 Jan 30 '19 at 15:06
• @VirtualUser surjective functions are always harder to work with. For this case the easiest way I can see is: let $f$ be in $A$ such that $f\restriction_{\Bbb N\setminus\{2^n\mid n\in \Bbb N\}}$ is surjective. Now for each $g$ in $A$ define $h_g(x)=\begin{cases} f(x)&x\ne 2^n\\g(n)&x=2^n\end{cases}$, you can notice that for all $g$ we have $h_g\in B$, and if $g\ne g'$ then $h_g\ne h_{g'}$, so you found a lower bound: $|A|=\frak c$ – ℋolo Jan 30 '19 at 15:34