1
$\begingroup$

I'm studying for an exam on lambda-calculus and algebraic specifications, and I'm having trouble figuring out this problem. I was wondering if anyone here could help??

The given specification:

S: sorts O

Σ: constants

a: -> O

b: -> O

c: -> O

function

f: O -> O

E: equations

[1] f(a) = c

[2] f(f(x)) = x

Now, first off, I'm looking for a model that has three elements and contains confusion, but no junk. Right now I have: A = {A,B,C} , a = A, b = B, c = C, f(a) = C, f(b) = B and f(c) = A. I thought the confusion would arise from f(b) = B = b, but I'm not sure this works...

As a second question, I'm looking for the correct initial model for this specification.

Any help would be greatly appreciated!!

Regards,

Linus

  • 0
    Doesn't $f(f(x))=x$ mean that $f(f(a))=f(c)=a$?2011-12-21
  • 0
    Yes, I guess it does... Does that prove anything? :)2011-12-21
  • 0
    Only that your definition of a model with $f(c)=C$ is not gonna work.2011-12-21
  • 0
    Oh, you're right! That was a typo, though :P2011-12-21
  • 0
    Can the initial model have $f(b)=b$? I don't know this area, but if "initial" is much like "initial" in category theory, then that would mean that every model had $f(b)=b$. Under the definition I'd expect for "initial," your initial model would be something like $\{A,B,C,D\}$ with $f(A)=C$, $f(C)=A$, $f(B)=D$ and $f(D)=B$. Basically, you're need to model $\{a,b,c,f(b)\}$.2011-12-21
  • 0
    Well, the question specifies that I must have three elements. Your solution has four...2011-12-21
  • 0
    Oh, I got the first and second question mixed up in my head. Yes, the first model is fine, although I'd write it as $f(A)=C$, $f(C)=A$, and $f(B)=B$ - you want the model definitions to be all about the model, and then define the mapping from the constants to the model. The initial model is the model I've given in my previous comment, assuming my intuition of what an initial model would mean. :)2011-12-21
  • 0
    (Although I guess I also don't know what "confusion" and "junk" mean, so I might be premature in saying your model for the first part satisfies the conditions.)2011-12-21

1 Answers 1

1

Ah, okay, I've found definitions:

http://jedidiah.stuff.gen.nz/essays/algebraic_specification.html 

Your model has "confusion" because $f(b)=b$ is an axiom for you model, which isn't true in your original algebraic specification. It doesn't have junk because all its elements correspond only to your constants.

$\{a=A,b=B,c=C,D\}$ and $\mathcal f$ defined to send $A\to C$, $C\to A$, $B\to D$, and $D\to B$, is an initial model. It has no junk because only $D$ doesn't correspond with any of the constants, but $D=\mathcal f(B)$.

On the other hand, this model has no confusion because no expressions in the specification language which is not deducible from the axioms is true for this model.[That seems non-trivial to me to prove, however. It seems more obvious that any expression true for this model will be true for all models.]

  • 0
    YES! Thank you so much! That's really helpful.2011-12-21