Is the equational theory generated by this set of equations the same as the set itself?

33 Views Asked by At

This is related somewhat to my previous question, here: What is a finite equational basis for this equational theory?. As before, our signature is a single binary operation $*$. Also as before, let $E$ be the set of all equations $s=t$, where $s$ and $t$ have the same set (the set, not the multiset) of variables. Let $Th(E)$ be the equational theory generated by $E$. Is it true that $Th(E)=E$?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes. Let $A$ be any set with at least two elements $1,2$, let $X=\mathcal{P}(A)$ (note that the set of finite subsets of $A$ would also work), and let $*$ be union. Then the algebra $\mathcal{X}=(X;*)$ satisfies exactly those equations of the desired form: it's easy to check that $\mathcal{X}$ satisfies every equation in $E$, but if $s,t$ are terms and $x$ is a variable in $s$ but not in $t$ we can get a failure of $s=t$ in $\mathcal{X}$ by interpreting every variable except $x$ as $\{1\}$ and interpreting $x$ as $\{2\}$.

Since $E$ is the equational theory of $\mathcal{X}$, $E$ is equationally deductively closed.


BELATED EDIT: there's also a "purely syntactic" proof via Birkhoff's Completeness Theorem. See e.g. pages 104-105 of Burris/Sankappanavar - the argument I have in mind is analogous to their Example (2) on page 107, which is what you'd get if you replaced "set" by "multiset" in your question. Basically, you can show by induction on derivation length that no equational derivation can get you from a set of "good" equations - in these cases "same variable (multi)set on each side" - to a "bad" equation. Personally I prefer semantic arguments, but they each have their place, and in a sense the whole point of a completeness theorem is to freely allow us to move between them so it seems good to mention this alternate approach here.