World's most popular travel blog for travel bloggers.

[Solved]: Homomorphisms and isomorphisms in an equational calculus

, , No Comments
Problem Detail: 

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 ?

Asked By : M.M

Answered By : Pål GD

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9005

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback