Abstract:
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.
Fulltext:
PDF file (333 kB)