First, some context: I'm reading this blog post by Andrej Bauer.

So, I stumbled in these terms: "observational equivalence" and "contextual equivalence".

I know almost nothing about operational semantics ... I know it gives meaning for terms by it's reduction to normal form, if I'm not wrong.

Extensional equality says that two functions are equal if they always give the same result for the same input, for some definition of same result.

From what Wikipedia says about observational equivalence I can't see how is not the same thing as extensional equality .

So my question is: how these things (all three things) are related and what distinguish them?

My question maybe be simple to answer. But if not because I should know more operational semantics to be able to understand the answer, them I would be glad to be informed about some literature about this subject.

  • $\begingroup$ Your definition of extensional equality isn't a full definition yet, because you need to define what you mean by "same result", and there are multiple possible definitions of that. $\endgroup$
    – D.W.
    May 24, 2017 at 20:25
  • $\begingroup$ I confess that I'm having a hard time to define "same result". I could imagine as example alpha-equivalence of Lambda Calculus. $\endgroup$ May 24, 2017 at 20:32
  • $\begingroup$ Terms don't need to be functions or even represent functions. Typically the value of observational equality is when they don't represent (mathematical) functions. I'm not sure how you see them as the same when they don't even apply to the same things. $\endgroup$ May 24, 2017 at 22:01
  • $\begingroup$ @DerekElkins I hadn't noticed that they don't represent functions. Also, the Wikipedia says something about a notion of context that I'm not familiar with. As you can see, I don't know what "observational equivalence" is. $\endgroup$ May 25, 2017 at 1:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.