Embedding of the atomic theory of subsets of free semigroups to the atomic theory of subsets of free monoids

B. O. Konstantinovskiy ; F. D. Kholodilov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2022), pp. 76-79

Résumé

In this paper, we consider atomic formulas constructed from the binary predicate symbol $\subseteq$ and binary function symbols $\backslash$, $/$, $\cup$, and $\cap$. For $X$ and $Y$ from the powerset of a free semigroup, $X/Y$ denotes the set consisting of elements whose product with any element of $Y$ ( multiplying on the right) belongs to $X$. Similarly, one defines $Y \backslash X$ (multiplying on the left). We prove that every atomic formula that is true in every free semigroup powerset interpretation is also true in every free monoid powerset interpretation.