Journal Article

The Class of Representable Ordered Monoids has a Recursively Enumerable, Universal Axiomatisation but it is Not Finitely Axiomatisable

Robin Hirsch

in Logic Journal of the IGPL

Volume 13, issue 2, pages 159-171
Published in print March 2005 | ISSN: 1367-0751
Published online March 2005 | e-ISSN: 1368-9894 | DOI: https://dx.doi.org/10.1093/jigpal/jzi012
The Class of Representable Ordered Monoids has a Recursively Enumerable, Universal Axiomatisation but it is Not Finitely Axiomatisable

Show Summary Details

Preview

An ordered monoid is a structure with an identity element (1′), a binary composition operator (;) and an antisymmetric partial order (≤), satisfying certain axioms. A representation of an ordered monoid is a 1-1 map which maps elements of an ordered monoid to binary relations in such a way that 1′ is mapped to the identity relation, ; corresponds to composition of binary relations and ≤ corresponds to inclusion of binary relations.

We devize a two player game that tests the representability of an ordered monoid n times and show that these games characterise representability. From this we obtain a recursively enumerable, universal axiomatisation of the class of all representable ordered monoids.

For each n < ω we construct an unrepresentable ordered monoid An and show that the second player has a winning strategy in a game of length n. Hence we prove that the class of all representable ordered monoids is not finitely axiomatisable.

Keywords: Binary relation, ordered monoid, partial order, game, non finitely axiomatisable

Journal Article.  0 words. 

Subjects: Logic

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.