On Cartesian monoids
A Cartesian monoid is a structure \((M,*,I,L,R,\langle\rangle)\), where \((M,*,I)\) is a monoid with \(L\) and \(R\) members of \(M\) and \(\langle\rangle: M^2\to M\) s.t. \[ L*\langle x,y\rangle= x, \] \[ R*\langle x,y\rangle= x, \] \[ \langle x,y\rangle* z=\langle x* z,y* z\rangle, \] \[ \langle L,R\rangle= I. \] Cartesian monoids re easy to come by. Any surjective pairing function lifts pointwise to a \(\langle\rangle\) on the monoid \(M\) of all functions under composition with \(L\) and \(R\) the lifted projections. Cartesian monoids were first introduced by \textit{D. Scott} [``Relating theories of the lambda-calculus, in: J. P. Seldin et al. (eds.), To H. B. Curry: Essays on combinatory logic, lambda calculus and formalism, 403-450 (1980; Zbl 0469.03006)] and independently by \textit{J. Lambek} [``From lambda-calculus to Cartesian closed categories, ibid., 375-402]. There are many connections to lambda calculus. It is the purpose of this paper to collect in one place our observations on Cartesian monoids, especially the free Cartesian monoid, which are useful for applications to lambda calculus. In particular, we shall derive the undecidability of the matching and unification problems for \(F\) (in a very strong form). Our approach is to treat the free Cartesian monoid as an algebraic structure of the sort that we learned about in school. This is not to say that we have any argument with the category theoretic approach; it is only to say that we are not competent to carry out that approach. For the entire collection see [Zbl 0868.00033].
- On the representation of semigroups and other congruences in the lambda calculus
- Cartesian monoids
- Realization of monoids on sets
- scientific article; zbMATH DE number 4127172 (Why is no real title available?)
- CARTAN SUBMONOIDS OF ALGEBRAIC MONOIDS
- Products in a category with only one object
- On Barron and Strachey's Cartesian product function
- Monoids on the 2-disk
This page was built for publication: On Cartesian monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4362934)
