4
$\begingroup$

Several properties that hold in nonempty finite semigroups also hold in nonempty compact semigroups. Furthermore, many of these properties can be formulated by a first order sentence. For instance, the existence of a minimal element for the preorder $\leqslant_{\mathcal J}$ can be translated as follows $$ \exists x\ \forall y\ \exists a\ \exists b\quad x = ayb $$ Similarly, the fact that the Green relations $\mathcal{D}$ and $\mathcal{J}$ coincide can be expressed by a first order formula, etc.

Now, I am looking for a first order sentence satisfied in every nonempty finite semigroup but not in every nonempty compact semigroup. I would prefer a sentence sitting low in the $\Sigma_n$ or $\Pi_n$ hierarchy, that is, a sentence with a small number of quantifier alternations.

Edit. A topological semigroup is a semigroup equipped with an Hausdorff topology for which the map $(x, y) \to xy\ $ is continuous. A compact semigroup is a topological semigroup which is compact as a topological space.

$\endgroup$
  • $\begingroup$ Do you want the sentence to define the class of finite semigroups in the class of compact semigroups, or is it really ok if there are infinite semigroups which satisfy the sentence? $\endgroup$ – f-h Mar 19 '15 at 13:17
  • $\begingroup$ @f-h The sentence has to be true in any finite semigroup, but should fail in at least one compact semigroup. But it can be true in some infinite semigroup. $\endgroup$ – J.-E. Pin Mar 19 '15 at 13:30
  • $\begingroup$ How about "there exists an idempotent"? Certainly true in any nonempty finite semigroup, but not true in a free semigroup, which is compact. $\endgroup$ – f-h Mar 19 '15 at 14:08
  • $\begingroup$ @f-h The free semigroup is not compact. And actually there exists an idempotent in any nonempty compact semigroup. $\endgroup$ – J.-E. Pin Mar 19 '15 at 17:40
  • $\begingroup$ In this case, I suppose we ment different definitions of compact. I was referring to the definition that can be found in the wikipedia entry for compact semigroup (not the topological one). $\endgroup$ – f-h Mar 19 '15 at 18:02
3
$\begingroup$

Here a possible answer: we can express "there is an element which is not the unity and which is a $\mathcal{J}$-maximal element (if we remove the unity)". I propose the following formula, where the Green relations could be thought as first-order formulae: $$∃x (x\neq 1) \land ∀y (y\neq 1 \land x\leq_{\mathcal{J}} y) \to x\mathop{\mathcal{J}} y $$ Since we are in semigroups (and not monoids) the formula $x\neq 1$ is actually a macro for $$\exists z (zx\neq z)\lor (xz\neq z)$$ I believe that this is true in every nonempty finite semigroup except the trivial one. This can be easily fixed with a simple disjunction with the formula: $$\forall x (x=1)$$

However the semigroup $[0,1]$ is a compact semigroup and does not satisfy this first-order formula. Indeed, the $\mathcal{J}$-order on [0,1] match with the classical order on real numbers. By removing the unity we obtain the interval [0,1[ that does not have a maximal element.

$\endgroup$
  • $\begingroup$ The semigroup $[0,1]$ is a very nice counterexample. One could also consider the negation of the formula saying that if $x <_{\mathcal{J}} y$ then there is a $z$ such that $x <_{\mathcal{J}} z <_{\mathcal{J}} y$. $\endgroup$ – J.-E. Pin Mar 26 '15 at 17:52

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.