Polymorphism of a relation

Builds on Finitary operation Cartesian product Binary relation

Definition

Let $A$ be a set, let $m, n \ge 1$ , and let $R \subseteq A^m$ be an $m$ -ary relation on $A$ . An $n$ -ary operation $f \colon A^n \to A$ is a polymorphism of $R$ if for all tuples $(a_{1 1}, \dots, a_{m 1}), \; \dots, \; (a_{1 n}, \dots, a_{m n}) \in R$ the tuple $\bigl(f(a_{1 1}, \dots, a_{1 n}), \dots, f(a_{m 1}, \dots, a_{m n})\bigr)$ is also in $R$ . For a set $\Gamma$ of finitary relations on $A$ , $\operatorname{Pol}(\Gamma)$ denotes the set of operations that are polymorphisms of every $R \in \Gamma$ . For a set $F$ of finitary operations on $A$ , $\operatorname{Inv}(F)$ denotes the set of finitary relations on $A$ of which every $f \in F$ is a polymorphism.

Remarks

Example: on $\set{0, 1}$ , the majority operation $m$ is a polymorphism of the binary relation $R = \set{(0, 1), (1, 0)}$ . Check: given three pairs $(a_j, 1 - a_j)$ in $R$ , the second coordinates are the complements of the first, so $m(1 - a_1, 1 - a_2, 1 - a_3) = 1 - m(a_1, a_2, a_3)$ and the result lies in $R$ . Non-example: the operation $\wedge$ on $\set{0, 1}$ is not a polymorphism of the same $R$ , since applying it to $(0, 1)$ and $(1, 0)$ gives $(0, 0) \notin R$ . For a unary relation $B \subseteq A$ , the polymorphisms are the operations under which $B$ is closed, so $B$ is a subuniverse. For an equivalence relation, the polymorphisms are the operations compatible with it, as in the definition of a congruence. If $A$ carries a relational structure, its polymorphisms are the homomorphisms from its $n$ -th power to itself.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`A1MRBS3Z5C`
URI	`m2://A1MRBS3Z5C`
Kind	definition
Writing	W0 stub
MSC	08A40, 08A02
Defines	Polymorphism of a relation
Uses	Finitary operation, Cartesian product, Binary relation

Polymorphism of a relation

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here