1

What are some good examples of partial combinatory algebras (a.k.a. Schoenfinkel algebras) with surjective pairing? I mean this in the sense that, if $\mathsf{D}$ is the pairing combinator and $\pi_0,\pi_1$ the projection combinators, then $\mathsf{D}(\pi_0x)(\pi_1x)=x$ for all $x$. Especially interesting would be examples where application is strictly partial, so that the PCA is not just a C-monoid.

(I'm not sure what some better tags are for this, so I'm open to suggestions on that front.)

Malice Vidrine
  • 9,653
  • What is a C-monoid? – tci Dec 21 '15 at 02:24
  • @tci: It's a monoid that is Cartesian closed except that it has no terminal object. It's the general class of structure that works as a model of untyped lambda calculus with surjective pairing. – Malice Vidrine Dec 21 '15 at 15:20

0 Answers0