Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups

DOI10.1007/S00012-016-0409-9MaRDI QIDQ2520764zbMATH OpenOpenAlexFDO

Authors Murray Neuzerling

Publication date 16 December 2016

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.03192

zbMATH Keywords

undecidabilityrelation algebras

Mathematics Subject Classification ID

Ordered semigroups and monoids (06F05) Cylindric and polyadic algebras; relation algebras (03G15) Undecidability and degrees of sets of sentences (03D35)

Abstract: We prove that the problems of representing a finite ordered complemented semigroup or finite lattice-ordered semigroup as an algebra of binary relations over a finite set are undecidable. In the case that complementation is taken with respect to a universal relation, this result can be extended to infinite representations of ordered complemented semigroups.

Recommendations

• Undecidability of representability as binary relations
• Undecidable Varieties of Semilattice—ordered Semigroups, of Boolean Algebras with Operators, and logics extending Lambek Calculus
• Decision problems for distributive lattice-ordered semigroups
• On representing semigroups with subsemilattices.
• Representations of distributive lattice-ordered semigroups with binary relations

Cites work

• scientific article; zbMATH DE number 67045 (Why is no real title available?)
• Axiomatizability of positive algebras of binary relations
• Embeddability and the Word Problem
• On representable relation algebras
• Relation algebras
• Representability is not decidable for finite relation algebras
• Representations of distributive lattice-ordered semigroups with binary relations
• The representation of relational algebras
• Undecidability of representability as binary relations

Cited in

(10)

• Representable semilattice-ordered monoids
• Domain and range for angelic and demonic compositions
• On representing semigroups with subsemilattices.
• Finite representability of semigroups with demonic refinement
• Domain range semigroups and finite representations
• The algebra of functions with antidomain and range
• The Class of Representable Ordered Monoids has a Recursively Enumerable, Universal Axiomatisation but it is Not Finitely Axiomatisable
• Undecidability of representability as binary relations
• Undecidability of Algebras of Binary Relations
• Implication algebras and implication semigroups of binary relations

This page was built for publication: Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2520764)