Mati Rubin (Ben-Gurion University of the Negev)

יום שלישי, 22 בדצמבר, 2015, 12:15 – 13:40, Math -101

תקציר:

Ralph McKenzie proved that if $G$ is a group of permutations of a set $A$ with cardinality different from $6$ and $1$, then the action of $G$ on $A$ can be recovered from the group G using first order formulas.

The analogous problems for semigroups of functions from a set $A$ to itself and for clones on $A$ have not been considered (so it seems).

I shall present four analogues of McKenzie‘s theorem.

Here is one of them.

Theorem 1: Let $A$ be a set whose cardinality is different from $6$ and $1$, and let $S$ be a semigroup of functions from $A$ to $A$ containing all transpositions of $A$. Then the action of $S$ on $A$ can be recovered from the algebraic structure of the semigroup $S$ using first order formulas.

A function $f$ from $A$ to $A$ is called a semi-transposition, if there are distinct $a,b$ in $A$ such that $f(a)$ equals $b$, and for every $c$ in $A$: if $c\neq a$, then $f(c) = c$.

Theorem 2: Let A be a set whose cardinality different from $1$, and let $S$ be a semigroup of functions from $A$ to $A$ containing all semi-transpositions of $A$. Then the action of $S$ on $A$ can be recovered from the algebraic structure of the semigroup $S$ using first order formulas.

Theorem 3: The analogues of Theorems 1 and 2 for clones are also true.

I shall present several open questions both for semigroups of functions and for clones.