How can I solve tasks like this one?

Example task

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?

  • $\begingroup$ The term in English is "cardinality" not "power" $\endgroup$ – ℋolo Jan 30 '19 at 15:00
  • $\begingroup$ @Holo On the contrary, "power" is also a common expression for cardinality. $\endgroup$ – Andrés E. Caicedo Jan 30 '19 at 15:04
  • $\begingroup$ @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 $\endgroup$ – ℋolo Jan 30 '19 at 15:08
  • $\begingroup$ Interesting. I have never heard the word "power" used for "cardinality." $\endgroup$ – 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$

  • $\begingroup$ 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 $\endgroup$ – user617243 Jan 30 '19 at 15:06
  • $\begingroup$ @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$ $\endgroup$ – ℋolo Jan 30 '19 at 15:34
  • $\begingroup$ Thanks, I think that I have understood this way of thinking. Now I am going to solve some tasks like this, sometimes if I will have doubts I will post to that forum (of course with my solution, for corectness-checking). Thanks @Holo! $\endgroup$ – user617243 Jan 30 '19 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy