A po-groupoid is a groupoid $\langle A,\cdot\rangle $ such that the relation defined by $$ x \leq y \text{ if and only if } x \cdot y = x $$ is a partial order on $A$, the order related to $\langle A,\cdot\rangle $.

For every poset $\langle A,\leq\rangle $ one can define a po-groupoid operation $*$ on $A$ setting $$ x * y := \begin{cases} x & \text{if } x\leq y \\ y & \text{if } x\not\leq y. \end{cases} $$ such that $\leq$ is the order related to $\langle A,*\rangle $.

Po-groupoids are obviously idempotent, but need not be associative nor commutative. In spite of this, I think that every down-directed poset is related to a commutative po-groupoid. An important example is given by semilattices: Commutative idempotent semigroup; these are exactly the po-groupoids related to posets $\langle A,\leq\rangle $ such that for every $x,y\in A$, $\inf\{x,y\}$ exists (where the product is given by the infimum).

I think I have an example of a poset that has no associative po-groupoid (a po-semigroup) related to it. My question is,

Is there any characterization in the literature of posets related to po-semigroups?

An important piece of information is that po-semigroups form a variety axiomatized by the following identities:

\begin{align*} (x \cdot y) \cdot z &\approx x \cdot (y \cdot z) \\ x \cdot x &\approx x \\ x \cdot y \cdot x &\approx y \cdot x. \end{align*}

  • 3
    $\begingroup$ Semigroups satisfying these identities are called right regular bands. Not all posets can have structure of this sort. One of my friends says he can prove it is NP-hard to determine if a poset comes from a right regular band if I remember rightly. $\endgroup$ – Benjamin Steinberg Jul 9 '16 at 13:26
  • $\begingroup$ @BenjaminSteinberg Thank you very much. Anyway, I don't know if this implies that there is no characterization of the form "omit these subposets/configurations". $\endgroup$ – Pedro Sánchez Terraf Jul 9 '16 at 13:38
  • $\begingroup$ Is $\approx$ supposed to be $=$? $\endgroup$ – Todd Trimble Jul 9 '16 at 13:58
  • $\begingroup$ @ToddTrimble Yes; we use that symbol to indicate universal closure of the equations. $\endgroup$ – Pedro Sánchez Terraf Jul 9 '16 at 14:18
  • $\begingroup$ There are some obvious conditions like if a is below b then the principal diem set generated by a is a retract of that generated by b. $\endgroup$ – Benjamin Steinberg Jul 9 '16 at 14:49

This is far from a complete answer, but you might be interested in taking a look at Section 3.5 of Lawrence Valby's 2015 PhD thesis, Some Case Studies in Algebra Motivated by Abstract Problems of Language. It is available on ProQuest, but I can email you a copy if you don't have access to ProQuest.

Lawrence gives a simple (second-order) characterization of a class of posets he calls $\downarrow$-posets and proves that this class of posets is not first-order axiomatizable. Here are the definitions:

An action (of $S$ on $C$ on the right) is an algebra in the signature consisting of two sorts, $C$ and $S$, and a function $C\times S\to C$. Any action $(C,S,\cdot)$ gives rise to a poset $(C,\leq)$, defined by $c\leq d$ if and only if there is a finite sequence $s_1,\dots,s_n$ (possibly the empty sequence) of elements of $S$ such that $ds_1\dots s_n = c$.

Instead of $S$, we can look at the set $S'$ of all functions $C\to C$ induced by the action of finite sequences of elements from $S$ on $C$. Then $S'$ is a monoid (with identity given by the empty sequence and multiplication given by composition), and we can equivalently define the poset $(C,\leq)$ by $c\leq d$ if and only if there exists $s\in S'$ such that $ds = c$. So if we're interested in the induced posets, we might as well be looking at monoid actions.

If $C$ and $S$ are collections of sets, we say that $S$ acts on $C$ by intersection if whenever $A\in C$ and $B\in S$, then $A\cap B\in C$. A $\downarrow$-action is an (abstract) action which is isomorphic to an action by intersection. It turns out that these are exactly the idempotent commutative actions (satisfying $css = cs$ and $cst = cts$, for all $c\in C$ and $s,t\in S$). If we replace $S$ by $S'$, we get exactly the semilattice actions. A $\downarrow$-poset is a poset arising from a $\downarrow$-action.

So $\downarrow$-posets are simpler than yours in that the algebras are commutative, but they're more general in that they come from actions on arbitrary sets, not necessarily the action of the algebra on itself. And they're not just the posets with finite meets! Anyway, the ideas in Lawrence's thesis might be relevant to your case.

  • $\begingroup$ Thanks for this information. I'm on a awful internet connection now, afterwards I'll check whether I can access the thesis. $\endgroup$ – Pedro Sánchez Terraf Jul 11 '16 at 13:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.