Consider the function $$f:\mathbb{N}\rightarrow\mathbb{N} ;n\mapsto n3^r+s$$ And the set M of functions such that, $$M=\{f:n\mapsto n3^r+s :r,s\in\mathbb{N}\}$$ Show that M is a monoid of functions on the base set $\mathbb{N}$.

My Attempt: We must show that $(f\circ g)(n)$ is also an element of M thus making M closed under composition. $$(f \circ g)(x)=f(g(x))=(n3^r+s)3^r+s$$ $$=n3^{2r}+s3^r+s$$ $$=n3^{2r}+s(3^r+1)$$ From here I am unsure how to write it in a form that shows that this is an element of M. I also know we must show that there exists an identity element such that $$(f \circ h)={id}_X$$ Any help is appreciated, thanks!

  • 4
    $\begingroup$ In order to encourage replies, you should accept at least some of the answer you received. You have accepted 1 answer over 30 questions. $\endgroup$ – rubik Feb 3 '17 at 21:29
  • $\begingroup$ To briefly address your concern in the first part of the question, note that $2r \in \mathbb N$ and $s(3^r + 1) \in \mathbb N$. Therefore $(f \circ g)(x)$ is in the form $n3^r + s$, with $r,s \in \mathbb N$ and so it's an element of $M$. However, to prove that $M$ is a monoid, you have to prove that the composition is associative and the existence of an identity element $h \in M$ such that $(f \circ h) = (h \circ f) = f$ for all $f \in M$. What you wrote with $id_X$ does not have particular meaning, and $X$ is undefined here. $\endgroup$ – rubik Feb 3 '17 at 21:37
  • 1
    $\begingroup$ The sentence "we must show that there exists an identity element such that $(f\circ h) = id_X$" is unclear and I suspect your are confusing with the existence of an inverse (which is not part of the definition of a monoid). What is $X$? What is $h$? What is the identity element? $\endgroup$ – J.-E. Pin Feb 4 '17 at 11:55

Your Answer

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

Browse other questions tagged or ask your own question.