4
$\begingroup$

Consider a finite semigroup $S$ whose semigroup operation $\times$ is commutative and whose elements are idempotent.

Does there exist a finite union-closed family of finite sets $\mathcal{M}$ such that there is a bijection $\tau: S \rightarrow \mathcal{M}$ where $\forall a,b \in S, \tau(a \times b) = \tau(a) \cup \tau(b) $?

I feel that this may not be the case necessarily since I haven't encoded any information about "subsets,containment..." into the axioms i've stipulated on the semi group, but from a purely algebraic standpoint it would seem that this characterizes the union very well.

$\endgroup$
2
  • $\begingroup$ Retag your question, it is not set theory. $\endgroup$ Apr 4 '19 at 2:00
  • 1
    $\begingroup$ Re tagged to combinatorics since family of union closed sets originates from there $\endgroup$ Apr 4 '19 at 2:01
5
$\begingroup$

Yes. Given $a\in S$, consider the set $I(a)=\{b\in S:ab=b\}$. I claim that that $I(ab)=I(a)\cap I(b)$. Indeed, if $c\in I(a)\cap I(b)$ then $(ab)c=a(bc)=ac=c$ so $c\in I(ab)$. Conversely, if $c\in I(ab)$, then $ac=a(abc)=a^2bc=abc=c$ so $c\in I(a)$, and similarly $c\in I(b)$. Also, if $I(a)=I(b)$, then $a\in I(b)$ and $b\in I(a)$ so $a=ab=b$.

So, this is almost what you wanted, but with intersections instead of unions. To get unions, you can just take complements and define $\tau(a)=S\setminus I(a)$ and let $\mathcal{M}$ be the image of $\tau$.

Semigroups of this sort are known as (unbounded) semilattices and are a basic object of study in order theory. They are often thought of as ordered sets via the ordering $a\leq b$ if $ab=b$ (or $ab=a$, depending on the context); the algebraic structure can then be defined in terms of the ordering.

$\endgroup$
5
  • $\begingroup$ Ah, I had basically the same idea, but I was trying to define it using unions and kept failing at one point in the proof. $\endgroup$
    – M. Vinay
    Apr 4 '19 at 2:22
  • $\begingroup$ If I undelete my answer, could you take a look and tell me what I'm missing? $\endgroup$
    – M. Vinay
    Apr 4 '19 at 2:37
  • $\begingroup$ @M.Vinay: I can see it even while it's deleted. Your approach is basically the same as defining $\tau(a)=\{b\in S:ab=a\}$. That typically won't satisfy $\tau(ab)=\tau(a)\cup\tau(b)$. Indeed, suppose the operation on $S$ really is $\cup$. Then $\tau(ab)=\tau(a)\cup\tau(b)$ would be saying $c\subseteq a\cup b$ iff $c\subseteq a$ or $c\subseteq b$, which isn't true in general. $\endgroup$ Apr 4 '19 at 2:57
  • 1
    $\begingroup$ The corresponding fact for intersections is true, though: $c\subseteq a\cap b$ iff $c\subseteq a$ and $c\subseteq b$. That's why it's more natural to first get a representation where the operation becomes intersection, as in my answer. $\endgroup$ Apr 4 '19 at 2:59
  • $\begingroup$ Ah, nice argument, I see the problem now. Thank you so much! $\endgroup$
    – M. Vinay
    Apr 4 '19 at 3:01

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.