# How can this function be surjective when there is a finite set mapped to an infinite set?

Question:

Consider the set $W$ of words over the alphabet $\{a,b,c\}$, i.e., the set of all ﬁnite non-empty sequences of letters chosen among $a, b$ and $c$ – for example, $aa, babb$ and $bbc$ are all elements of $W$.

Let $\rm{counta}$ be the function from $W$ to $\mathbb{N}$(Natural Numbers) that counts the number of times the letter $a$ occurs, i.e., given $w \in W$, $\rm{counta}(w)$ is the number of times $a$ occurs in $w$.

I was told that $\rm{counta}$ is surjective but I don't understand why. Surjection $y = f(x)$, but the set $W$ is finite so how can you map all of $W$ to $\mathbb{N}$?

• W is not finite, it's just generated by a finite set Apr 13, 2017 at 14:41

The set $W$ is not finite. The alphabet is finite, but we can create arbitrarily long words out of this alphabet, and hence $W$ will be infinite (if you have heard of such things, $W$ is in fact countably infinite). For instance, consider the subset $$\{a,aa,aaa,\dots\}\subset W.$$ Does this help you see surjectivity?