I'm reading A Rendezvous of Logic, Complexity and Algebra, my first introduction to the world of CSP. Let $\Gamma$ be a finite constraint language. It says in Pg. 9 that

$Pol(\Gamma)$ is used to denote the set of all polymorphisms of $\Gamma$, that is, $$Pol(Γ) = \{f : \forall R \in \Gamma, \textrm{ f is a polymorphism of }R\}.$$ Also, for a set of operations $O$, we use $Inv(O)$ to denote the set of relations having all operations in $O$ as a polymorphism, that is, $$Inv(O) = \{R : \forall f \in O, \textrm{ f is a polymorphism of } R\}.$$

The answer to my question is: No (in fact it is a subset of $\Gamma$). But I don't understand why:

  1. Isn't every $R\in \Gamma$ in $Inv(Pol(\Gamma))$?
  2. Are the $R$'s from $Inv(O)$ allowed to come only from $\Gamma$?

The operation $\operatorname{Inv}(\operatorname{Pol}(\cdot))$ is a closure operation. This means that

  1. $\Gamma \subseteq \operatorname{Inv}(\operatorname{Pol}(\Gamma))$.
  2. $\operatorname{Inv}(\operatorname{Pol}(\Gamma)) = \operatorname{Inv}(\operatorname{Pol}(\operatorname{Inv}(\operatorname{Pol}(\Gamma))))$.

See for example lecture notes of Jin-Yi Cai.


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.