8
$\begingroup$

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*}

$\endgroup$
12
  • 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$ Commented Jul 9, 2016 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$ Commented Jul 9, 2016 at 13:38
  • $\begingroup$ Is $\approx$ supposed to be $=$? $\endgroup$
    – Todd Trimble
    Commented Jul 9, 2016 at 13:58
  • 1
    $\begingroup$ @ToddTrimble Yes; we use that symbol to indicate universal closure of the equations. $\endgroup$ Commented Jul 9, 2016 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$ Commented Jul 9, 2016 at 14:49

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for this information. I'm on a awful internet connection now, afterwards I'll check whether I can access the thesis. $\endgroup$ Commented Jul 11, 2016 at 13:48
2
$\begingroup$

As Benjamin stated in the comments, semigroups satisfying these identities are called right-regular bands. Let us call the partial orders underlying a right-regular band “associative”. There is no characterization of associative posets available yet; but there are many families of posets which are known to be associative.

Alejandro Petrovich noted that, in a right-regular band, left multiplying by a minimal element acts as a choice function of the minimal elements. P. Sánchez Terraf harnessed this idea to show that the associativity of trees of height 3 is equivalent, under ZF, to the Axiom of Choice. I provided a generalization of this result, showing that the Axiom of Choice can be used to define right-regular band operations over a broader family of trees called foliated trees.

These results lead to a collaboration, the results of which can be checked here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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