The Class of Representable Ordered Monoids has a Recursively Enumerable, Universal Axiomatisation but it is Not Finitely Axiomatisable
Robin Hirsch · Logic Journal of IGPL · 2005
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.