2
$\begingroup$

Let $T$ denote an algebraic theory.

Terminological Question. Let $X$ denote a $T$-algebra. Is there a name for the preorder $\mid$ defined on $X$ by asserting that $a \mid b$ iff there is a term operation $f : X^n \times X \rightarrow X$ such that $f(\tilde{x},a)=b$ for some $\tilde{x} \in X^n$?

Even if no such name exists, I am interested to read more about this relation. In particular, I'd like to know:

Main Question. For which algebraic theories $T$ does it hold that the $\mid$ preorder (as defined above) is antisymmetric on all free $T$-algebras?

Examples/counterexamples.

  • Let $T$ denote the theory of Abelian monoids. Then every free $T$-algebra has the property of interest.
  • Let $T$ denote the theory of Abelian groups. Then no non-trivial $T$-algebra has the property of interest.

Here is a related terminological question I asked the other day.

Improve this question
$\endgroup$
7
  • $\begingroup$ In model theory, one has some notion (algebraic with respect to parameters a) that is related to this. I don't know if there is a standard name for the preorder. For finite algebras, there is a classification of such algebras for which (I suspect) the relation is total. You might find Hobby and McKenzie's text on tame congruence theory of interest, especially the foundational part. Your notion can be extended by replacing = by an arbitrary congruence of X, and may have been considered for finite X by Hobby and McKenzie. Gerhard "Doing This With Fuzzy Memory" Paseman, 2014.07.13 $\endgroup$
    – Gerhard Paseman
    Commented Jul 13, 2014 at 20:24
  • $\begingroup$ I also suspect that such algebras will yield a normal form, or provide a small "unnormalizable" core. You might look at Knuth-Bendix to see if someone has come to a similar conclusion. Gerhard "Or Tweak The Relational Properties" Paseman, 2014.07.13 $\endgroup$
    – Gerhard Paseman
    Commented Jul 13, 2014 at 20:32
  • $\begingroup$ This relation is antisymmetric for monoids and semigroups without abelian and for many natural subvarieties. $\endgroup$
    – Benjamin Steinberg
    Commented Jul 14, 2014 at 2:00
  • $\begingroup$ @BenjaminSteinberg, or rather, for free monoids / semigroups etc. Some monoids happen to be groups, after all. $\endgroup$
    – goblin GONE
    Commented Jul 14, 2014 at 7:19
  • $\begingroup$ But the theory is the theory of monoids and semigroups. In your question you only ask about the relation on free objects. $\endgroup$
    – Benjamin Steinberg
    Commented Jul 14, 2014 at 12:45

1 Answer 1

Reset to default
4
$\begingroup$

Here is an idea to construct examples generalizing those above. It certainly works for varieties of algebras with a binary operation and should work more generally.

I prefer to give an answer using the old-fashioned language of universal algebra. Suppose we have some signature $\Omega$. Infinitely many operations are ok but let me assume they are all finitary to be safe.

The free algebra of type $\Omega$ on a set $X$ is built up inductively by starting with variables and applying formally operations in $\Omega$. We can represent elements as strings in the obvious way. Let us define the length of an expression as the total number of symbols appearing in the term including all parentheses.

Now let $\mathcal V$ be a variety of algebras of type $\Omega$ defined by identities in which each side has the same length and the variables appearing on each side are the same with multiplicities. Then the preorder is an order for the free objects because equivalent terms in $\mathcal V$ will have the same length and so length is well defined on the free objects and gives an obstruction to what you want. There are some details to check.

For example commutative monoids are defined by identities $ab=ba$ and $(xy)z=x(yz)$ satisfy the above conditions.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .