Homomorphisms and isomorphisms in an equational calculus

Question

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 ?

Answer 1

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.