1
$\begingroup$

I'm trying to prepare for an exam and am revising the cardinalities of sets of functions. However, I became interested in cardinalities of sets of functions some of which are outside the course and am trying to find them myself. So here goes:

$1) f:\mathbb{R} \rightarrow \mathbb{R} $

$2) f:\mathbb{R} \rightarrow \mathbb{N} $

$3) f:\mathbb{N} \rightarrow \mathbb{N}$

$4) f:\mathbb{N} \rightarrow \mathbb{R}$ with finite support, i.e. equal to $0$ for all but finitely many values (essentially sequences)

$5) f:\mathbb{N} \rightarrow \mathbb{R}$ for which exists $a \in \mathbb{R}$ such that $|f(n)|=a \forall n\in \mathbb{N}$

My answers:

$1)$ By definition the cardinality is $|\mathbb{R}^\mathbb{R}|=2^{w2^w}=2^{2^w}$

$2)$ $|\mathbb{N}^\mathbb{R}|=w^{2^w}$ and I don't think this can be simplified more

$3)$ $|\mathbb{N}^\mathbb{N}|=w^{w}$ and I don't think this can be simplified moresimilarly to $2)$

$4)$ This is where I am stuck. An informal argument gave me the answer $(2^w+1)^w=2^w$ where I looked at the number of sequences with support $n$ and used the expansion of $(x+1)^n$. Finally, I used that there is a bijection between $\mathbb{R}\bigcup\{\infty\}$ and $\mathbb{R}$ where $\infty$ is regarded as an element outside $\mathbb{R}$

$5)$ Again, informally I got $2^w$ as an answer since we for a fixed $a$ we can interpret those sequence as a function $f:\mathbb{N}\rightarrow 2$. What is left is to take into consideration the number of values of $A$.

As you can see, I am having some troubles with formalizing my arguments. Also, when I am given an awkward function such as "all total orders on a set(say the positive integers)" or "all open sets somewhere" I don't know what to do. My ideas are limited to finding a bijection between the set and some set I know everything about. In general, how do you procede when you want to find the cardinality of a not-so-obvious set? Are there any tips and tricks?

Cheers!

$\endgroup$
4
  • 1
    $\begingroup$ 3) has the same cardinality as the real number set. $\endgroup$ Apr 10 '18 at 11:07
  • $\begingroup$ Also finding bijections between sets you know and you don’t. $\endgroup$ Apr 10 '18 at 11:13
  • 1
    $\begingroup$ Does this follow from $2^w<w^w<2^{w*w}=2^w$? $\endgroup$
    – asdf
    Apr 10 '18 at 11:16
  • 1
    $\begingroup$ Similarly, $2^{2^w}<w^{2^w}<2^{w2^w}=2^{2^w}$ $\endgroup$
    – asdf
    Apr 10 '18 at 11:23
2
$\begingroup$

I will assume $w$ in your question is $\omega$, a cardinality of the set of natural numbers.

We can simplify $\omega^{2^\omega}$ to $2^{2^\omega}$ by following simple inequlaities: $$2^{2^\omega} \le \omega^{2^\omega} \le (2^\omega)^{2^\omega} = 2 ^{\omega\cdot 2^\omega} = 2^{2^\omega}.$$

If my understanding is correct, your fifth set is the set of all constant functions from $\mathbb{N}$ to $\mathbb{R}$. The only factor deciding constant function is its value, so there are $|\mathbb{R}| = 2^\omega$ such functions.

Now evaluate the number of elements of your fourth set. Your guess is right but I don't understand your informal argument. However, there is more simple way to check its cardinality: we can find an injection from your fourth set to $\mathbb{R}^\mathbb{N}$ - the inclusion map. Moreover you can easily see that $|\mathbb{R^N}| = 2^\omega$. Hence your fourth set has at most $2^\omega$ elements. Checking your fourth set has at least $2^\omega$ elements is also easy, so the cardianlity of our set is $2^\omega$.

$\endgroup$
3
  • $\begingroup$ My argument was combinatorial - consider the sequences which have one non-zero entry. You can choose its position in $\omega$ ways and its value by $2^{\omega}$ ways. For $2$ entries you have ${\omega} \choose {2}$ ways for the entries and $2^{2\omega}$ possible values etc. In general, can you give me any advice on finding cardinalitites? Is it just "solve lots of problems until you get the hang of it"? Many thanks in advance! $\endgroup$
    – asdf
    Apr 10 '18 at 11:42
  • $\begingroup$ @asdf Infinite combinatorics is not exactly same as finite one. You basically should be careful when dealing with infinity. Your argument seems to exclude all functions with cofinitely many zeros. However it does not exclude functions which has infinitely, but not cofinitely many zeros. $\endgroup$
    – Hanul Jeon
    Apr 10 '18 at 11:47
  • $\begingroup$ @asdf I don't think there is an easy combinatorial argument. We must rely on the property of the set of reals. $\endgroup$
    – Hanul Jeon
    Apr 10 '18 at 11:49

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.