1
$\begingroup$

Question:

Consider the set $W$ of words over the alphabet $\{a,b,c\}$, i.e., the set of all finite 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}$?

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

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Thanks for catching that; I was thinking of infinite sequences, not finite words $\endgroup$
    – TomGrubb
    Apr 13, 2017 at 14:46
  • $\begingroup$ Thank you so much, I really appreciate this! $\endgroup$
    – MAON
    Apr 13, 2017 at 14:47

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.