Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have an algebraic specification in the form: $\{S,F,w\}$ where $S$ are the sorts, $F$ are the functions and $w$ are the set of equations. For example, the specification for natural numbers:

  • $S = \{\mathrm{int}\}$
  • $F = \{ 0: \mathrm{int}, \; \mathrm{succ} : \mathrm{int}\rightarrow\mathrm{int}, \; \mathrm{pred}: \mathrm{int}\rightarrow\mathrm{int} \}$
  • $w = \{ \mathrm{succ}(\mathrm{pred}(x)) = x, \; \mathrm{pred}(\mathrm{succ}(x)) = x \}$

My question is, why and where do we need homomorphisms and isomorphisms in this case? How do homomorphisms and isomorphisms look like between algebras ?

share|cite|improve this question
Your question is very unclear. Are you looking for examples of (iso)morphisms? – Gilles Jan 21 '13 at 20:53
Yes, an example of (iso)morphisms between two algebras could help! – M.M Jan 22 '13 at 19:46
up vote 6 down vote accepted

Can you come up with two different algebras, say, one where the domain is $\mathbb{N}$ and one where the domain is $\{0,1\}$ and in the former, suc and pred work as you would assume, and in the latter, they are modulo 2 operations? Then, try to come up with a homomorphism from one to another.

Then, try to make an algebra, where the domain is $\{0, s0, ss0, sss0, \dots\}$ and define suc and pred as you would guess. Make an isomorphism from this one to the one with $\mathbb{N}$ as domain.

Finally, you can make the "term algebra", which has as domain all strings that are valid "terms", i.e.: "0" is in the domain, and for every element $t$ in the domain, "suc($t$)" is in the domain, and "pred($t$)" is in the domain. Their interpretation is simply that the constant 0 maps to the string "0". The term pred(suc(suc(suc(0)))) maps to the string "pred(suc(suc(suc(0))))". Now, you might have a hard time making an isomorphism from this to the standard algebra (the one with $\mathbb{N}$), since "0" and "pred(suc(0))" should both map to 0.

I'm not sure exactly what you ask for, but these two tasks should get you started, at least.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.