In Universal Algebra, by an equational variety of algebras we mean the class of all algebraic structures of a given signature satisfying certain (conjunctions of) identities. Dually, an antivariety satisfies certain disjunctions of negated equations (a.k.a. anti-identities). Moreover, by a disjunction of polynomial equations (DE) we mean a disjunction of identities. Obviously, an identity is a particular (degenerate) case of DE. Furthermore, one might note that anti-identities and DEs are, respectively, particular cases of Horn clauses and dual Horn clauses.

Some well-known classes of algebraic structures are very naturally characterized by a set of axioms containing both anti-identities and DEs. For instance, field axioms include an anti-identity (the 'zero-one law'), and a number of DEs, including a non-degenerate one that consists in a disjunction that deals with the multiplicative inverses of non-zero elements ('for any given field element, either it is zero or it has a multiplicative inverse'). If one generalizes the above definitions for signatures having relational symbols in the natural way (having positive literals replace identities, and negative literals replace anti-identities), other more or less natural examples of structures whose axiomatizations mix generalized anti-identities and generalized DEs may be found in Graph Theory (an example: connected oriented graphs).

Are there other well-known 'natural' and 'useful' examples of algebraic structures axiomatized by both DEs and anti-identities, in Mathematics or Computer Science?

  • $\begingroup$ The first-order theory of graphs is not an algebraic structure, so it's not a good example. Also a disjunction of equations is not a particular case of a Horn clause. $\endgroup$ – Rob Arthan Apr 12 '17 at 20:58
  • $\begingroup$ Thanks for the comment, @RobArthan. I will omit the example from Graph Theory, as it indeed requires the signature to be augmented with relation symbols. As for DEs not being a particular case of a Horn clause, I had meant to write dual Horn clauses (i.e., "disjunctions of literals with at most one negated literal"), exactly as in the link that I had added from the beginning. Shall fix that. Thanks again. $\endgroup$ – J Marcos Apr 12 '17 at 21:22
  • $\begingroup$ Fixed, @RobArthan. Note that I ended up not omitting the example from Graph Theory, but rather modifying it minimally to have it making sense (I do hope it is clear now!). $\endgroup$ – J Marcos Apr 12 '17 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.