数理解析研究所講究録 1325 巻 2003 年 146-151

146

Centralizers and Monoids in Mathematical
Clone Theory
町田

ローゼンバーグ (Ivo G.Rosenberg)

元 (Hajime Machida)

一橋大学 (Hitotsubashi University)

machida@math.hit-u.ac.jp

Abstract

モントリオール大学 (Universit\’e de Montr\’eal)rosenb@DMS.UMontreal.CA([Po 41]) andknown for each.
if,
To get better understanding of the lattice
we started in [MMR 01] to study the clones corresponding to monoids of unary operations on by
anatural Galois connection.
This paper is an attempt to briefly summarize.
the work of [MMR 01], [MMR 02] and$k\geq 2:|\mathcal{L}_{2}|=\aleph_{0}$$3\leq k<\mathrm{N}_{0}([\mathrm{I}\mathrm{M}59])$$|\mathcal{L}_{k}|=2^{\aleph_{0}}$Aclone is aset of multi-variable operations which contains all projections and is closed under composition.
is the clone
For aset of operations the centralizerof operations which commute with all operations in .
In this paper we consider some monoids consisting of unary operations and the centralizers of suchmonoids. We study (1) the centralizers of somemonoids which contain the symmetric group, (2) the
centralizers of permutation groups and (3) some rela
tively small monoids whose centralizer is the least clone.
$S$$\mathrm{S}^{\mathrm{r}}$$S$

Keywords: Clone; centralizer; monoid$\mathcal{L}_{k}$$k$$[\mathrm{M}\mathrm{R}03]$

is transDefinition 1. 2A subset $M$ offormation monoid (or, simply, monoid) on
if it satisfies the following conditions:$O_{k}^{(1)}$

$a$

$k$

$a$

(i) For any , $t\in M$ , the compositionofand belongs to $M$ .
belongs(ii) The identity operation$t\circ s$

$s$

$t$

$s$

$\mathrm{i}\mathrm{d}k(=e_{1}^{1})$1Preliminaries

to

Let $k=\{0,1, \ldots, k-1\}$ for a fixed $k>1$ . For
apositive integer
be the set of all nlet
into ,
ary operations on , that is, maps from. Denote by Jh the set ofand letall projections , $1\leq i\leq n$ , over whereis defined as $e_{*}^{n}(x_{1}, \ldots, X:, \ldots, x_{n})=X$ :for every$O_{k}^{(n)}$$n$$k^{n}$$k$$k$$(x_{1}, \ldots, x_{n})\in k^{n}$$e_{\mathrm{i}}^{n}$

Denote byby inclusion.

$\mathcal{M}_{k}$the set of all monoids on k orderedandWe say that operations
commute (or permute), in symbol $f[perp] g$ , if forevery
matrix $B=(b:j)$ over$g\in O_{k}^{(n)}$$f\in O_{k}^{(m)}$$k$$m\cross n$.

$f(g(b_{11}, \ldots, b_{1n}), \ldots, g(b_{m1}, \ldots, b_{mn}))$is a clone on
Definition 1. 1A subset C of
k if the following conditions are satisfied:$O_{k}$

(i)
(ii)

.

$k$

$O_{k}= \bigcup_{n=1}^{\infty}O_{k}^{(n)}$$e_{i}^{n}$$M$

contains $Jk$ .
$C$ isclosed under (functional) composition.

$g(f(b_{11}, \ldots, b_{m1}), \ldots, f(b_{1n}, \ldots, b_{mn}))$$=$Clearly, the relation$[perp] \mathrm{o}\mathrm{n}O_{k}$.

is symmetric.

$C$

Definition 1. 3For a subset $F$ of$O_{k}$, define. The
is denote by
The set of all dones onsetordered by inclusion is called the lattice of.
clones on and is denoted by

The setis completely known
The structure offor every([Po 41]); however, the structure of$k\geq 3$ is extremely complex and still mostly unknown. The cardinality of the lattice of clones isis aclone on
Note: (1) It is easy to see thatfor any subset of .
(2) Clearly from the definition, $F\subseteq G$ implies
for any subsets , of .

$k$

$L_{k}${ g $\in O_{k}|g[perp] f$ for all f$F^{*}=$$\in F$}.

$L_{k}$$k$$\mathcal{L}_{k}$$\mathcal{L}_{2}$$\mathcal{L}_{k}$$F^{*}$

is called the centralizer of F.
$F^{*}$$F$$G^{*}\subseteq F^{*}$$O_{k}$$F$$G$$O_{k}$$k$

147

Definition 1. 4 For a positive integer an h-ary
relation on is a subset of , $i.e.$ , a set of hpreserves
tuples over . An operationif, for every $h\cross m$ mat $\dot{m}B=(b_{ij})$ over whose
column vectors all belong to , the -tuple of values,of on the rows of $B$ also belongs to$h_{J}$$k^{h}$$k$$\rho$$k$$f\in \mathit{0}_{k}^{(m)}$$\rho$$k$$h$$\rho$$f$short, p-expressible, by
if there exist (i) in, and (ii) $(m+\ell+1)- ary$
tegers $m\geq 1$ andsuch that
operations , $h_{\dot{f}}(i=1, \ldots, m)$ in
consists of all $(x_{1}, \ldots, x_{n+1})\in k^{n+1}$ satisfying thesystem of equations$\Sigma$$\ell\geq 0$$\langle$$g_{i}$$f^{\square }$$\Sigma)$$\rho ji.e.$$g_{i}(x_{1}, \ldots, x_{n+\ell+1})=h_{i}(x_{1}, \ldots,x_{n+\ell+1})$$(f(b_{11}, \ldots, b_{1m}), \ldots, f(b_{h1}, \ldots, b_{hm}))\in\rho$$(i=1, \ldots, m)$whenever $(b_{1j}, \ldots, b_{hj})\in\rho$ for all $j=1$ , $\ldots,m$ .
For an h-ary relation on k set

$/or$

some

$x_{n+2}$,$\ldots$,$X_{n+}\ell\dagger 1\in k$, $i.e.$ ,$\rho$

Pol $\rho=$ { f $\in O_{k}|f$ preserves$\rho$$f^{o}=\{(x_{1}, \ldots, x_{n},x_{n+1})|$}.

$\exists x_{n\dagger 2}$,, $x_{n+\ell+1}\in k$$\ldots$$\forall i\in\{1, \ldots,m\}$$g_{i}(x_{1}, \ldots, x_{n+\ell+1})=h:(x_{1}, \ldots, x_{n+l+1})\}$

It is easy to see that Pol is a clone on k.

.

$\rho$In this paper we shall mostly deal with the following special type of relations. For f
set$\in O_{k}^{(m)}$$f^{\square }=\{(a_{1}, \ldots, a_{\mathrm{m}}, f(a_{1}, \ldots, a_{m}))|$$a_{1}$,$\mathrm{C}7\dot{\mathrm{B}}terion$

Even more specificaly, our main concern is thecase $m=1$ , that is, the case of binary relations
induced by unary operations. To repeat, for an
operation
we setFor

and $s\in O_{k}^{(1)}$ ,$f\in \mathit{0}_{k}^{(n)}$$\Sigma$$p$$\Sigma^{*}\subseteq\{f\}^{*}$of Monoids
containing the SymmetricGroup

2Centralizers$s\in O_{k}^{(\mathrm{J})}$$s^{\square }=\{(x, s(x))|x\in k\}$$f$$\Sigma\subseteq O_{k}$This property turns out to be quite useful in the
study of clones, in particular, of centralizers.

, $a_{m}\in k\}$ .

$\ldots$) Let $f\in O_{k}$Theorem 1. 1 (Kuznetsov. Then is -expressible by if andand.
only if.

$S_{k}$$f\in \mathrm{P}\mathrm{o}1(s^{\mathrm{o}})$isequivalent to

2.1

The Sequence$\{N\dot{.}\}$of Monoidsof monoids whichFirst we consider the, monoids,group
symmetric“above”
thesitcontaining .
In [MMR 01] we introduced the operations
afollows: For every $i=0,1$ , , $k-1$ , a unary: $karrow k$ is defined byoperation$\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}1\mathrm{i}_{l}\prime \mathrm{e}\mathrm{r}\mathrm{s}$$f(s(x_{1}), s(x_{2})$,$\ldots$, $s(x_{n}))=s(f(x_{1}, x_{2}, \ldots, x_{n}))$for every $(x_{1}, x_{2}, \ldots, x_{n})\in k^{n}$ . To put it in alge
braic terminology,means that is anendomorphism of the algebra.
$f\in \mathrm{P}\mathrm{o}1(s^{\square })$$s$$\langle k;f\rangle$

From the definition of f-L
of 1we obtain for , $g\in O_{k}$$\Leftrightarrow$$f\in \mathrm{P}\mathrm{o}1g^{\mathrm{o}}$$d_{i}’ \mathrm{s}$$\ldots$$d_{\dot{\mathrm{t}}}$$d_{i}(x\rangle=\{$$\Leftrightarrow$$g\in \mathrm{P}\mathrm{o}1f^{\square }$$\mathrm{i}.\mathrm{e}.$$s_{k}$and the symmetry

$g$

$f$

$f[perp] g$$S_{k}$,

0if$0\leq x\leq i$$x$$i<x\leq k-1$

if(the identity operation on )In particular,
satisfies the following: $d_{k-2}(x)=0$ forand$x\in k\backslash \{k-1\}$ and $d_{k-2}(k-1)=k-1$ .
$k$$d_{0}=e_{1}^{1}$and hence the centralizer$F^{*}=f\in F\cap$$p*\mathrm{o}\mathrm{f}F\subseteq O_{k}$Pol$f^{\square }$

is

.

.

$d_{k-2}$

for $i\in k$ is defined as the clone
The monoid
on and thegenerated by the symmetric group,
operation ,$N_{\dot{l}}$$s_{k}$,
For
denotes the clone generated
is the least clone containing $F$ .
by $F$ , that is,
The following definition and theorem are from
[Da77, 79].
$F\subseteq O_{k}$$\langle F\rangle$$\langle F\rangle$$d_{\dot{l}}$$k$$\mathrm{i}.\mathrm{e}.$.

$N_{*}$$=\langle S_{k}\cup\{\mathrm{A}.\}\rangle$.

.
It is easy to see that $N_{0}=S_{k}$ andand all constant unaryAlso, $N_{k-1}$ consists ofoperations.
$N_{1}=\mathit{0}_{k}^{(1)}$

, the
and
Definition 1. 5For
operationis parametrically expressible, in$f\in O_{k}^{(n)}$$f$$\Sigma\subseteq O_{k}$$s_{k}$

148

Proof Denote by
the binary relation on theright side of the above equation.
, $k-1$ , we consider which
For each $x=0,1$ ,satisfies
where $y\in\{0, \ldots, k-1\}$ .
Case 0: Suppose $x=0$ . Then it is easy to seethat $c_{0}(0)=\chi_{1}(y)$ implies $y\neq 1$ . Similarly, it is
implied from $c_{0}(0)=\chi j(y)$ that $y\neq j$ for every, . Next, from $\chi:+1(0)=\chi:+1(y)$ it is$j=1$ ,
implied that $y\neq i+1$ . Similarly, it is implied
ffom $\chi\ell(0)=\chi p(y)$ that $y\neq\ell$ for every $\ell=i+$,, $k-1$ . So the only possibility is $y=0$ , andclearly $(0, 0)\in\rho:$ .
Analogously, we can check, for every, that $(x, 0)$ is the only pair that satisfies,
for $y=0$ , , $k-1$ .
Case $i+1$ :Suppose $x=i+1$ . In this case$c_{0}(i+1)=\chi j(y)$ implies that $y\neq i$ for every $i=$
, . Now, $\chi:+1(i+1)=\chi_{\dot{\iota}+1}(y)$ implies $y=$,$i+1$ . And, $\chi\ell(i+1)=\chi\ell(y)$ implies $y\neq\ell$ for
every $\ell=i+2$ , , $k-1$ . Hence $(i+1, i+1)$ is the
only pair that belongs to with $i+1$ as the firstcomponent.
In the similar way we can check, for every $x=$
$i+1$ ,
, $k-1$ , that $(x, x)$ is the only pair thatsatisfies $(x, y)\in\rho$:for $y=0$ ,, $k-1$ .
Thus we have proved that.
$\rho_{i}$01$ii+1i+2$$k-1$$\ldots$$(x,y)\in\rho_{\dot{l}}$$y$$i+1\mathrm{I}i+2[\cdots$$k-1\mathrm{I}$$i$$\ldots$

Figure 1. The unary operation$d_{i}$$1$

We have asequence

$x$

$0$

$S_{k}\subset N_{k-1}\subset N_{k-2}\subset\cdots\subset N_{3}\subset N_{2}\subset O_{k}^{(1)}$where the$\mathrm{s}\mathrm{y}\mathrm{m}\mathrm{b}\mathrm{o}\mathrm{l}\subset \mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{s}$proper inclusion.

$\mathrm{a}\mathrm{k}\mathrm{o}$as$\tau$$1$$\ldots$$i$$\ldots$$\ldots$$\sigma(x)=\{$$\beta_{\dot{|}}$

if $x\in k\backslash \{k-1\}$
if $x=k-1$

$x+1$

0

and

$\ldots$

1
if$\tau(x)=\{$ 0if

$x=0$
$x=1$

i.e., in the cyclic notation$\tau=(01)$Let$\square$$\rho:=d_{\dot{1}}$$\mathrm{a}=$$(0 1 \cdots k-1)$.

; $karrow k$ be$c0$

for all
For every $i\in k$ let
operation defined as$\mathrm{c}\mathrm{o}(\mathrm{x})$$\ldots$

$=0$

and

$\chi$.

: : $karrow k$ be the unary{Xi |i$\in k$

if

Proof

.

$\in k$It is easily verified that.

$\square$$\in$$O_{k}^{(n)}$.

Lemma 2. 4For
is consemative.

$f\in O_{k}^{(n)}$, if$f\in(O_{k}^{(1)})^{*}$

then

$f$

$N_{\dot{l}}^{*}=N_{k-2}^{*}$

$p$

A.

$N_{i}’ \mathrm{s}$In this subsection we assert without proof that$(O_{k}(1))^{*}=$
Jk- Then, as a corollary, we have
Ni ’= @ for every $1\leq i\leq k-2$ .
An operation
is called conservative if $f(a_{1}, \ldots, a_{n})\in\{a_{1}, \ldots, a_{n}\}$ for every$(a_{1}, \ldots, a_{n})\in k^{n}$

Proposition 2. 2 For $1\leq i\leq k-2$ , the operationis -ezpressible frvrn $N_{k-2}$ , namely,$d_{i}$The Centralizers of$f$Application of the Kuznetsov

Criterion :

.

Proof
Clear ffom the Kuznetsov criterion,
Lemma 2.1 and Proposition 2.2.

2.3

, xi is genemted by$\chi_{i}=\sigma d_{k-2}\sigma^{-1}d_{k-2}\sigma^{-(:+1)}$

2.2$N_{\dot{1}}^{*}=N_{k-2}^{*}$$x=i$ ,}.

Lemma 2. 1 For every i$\{\sigma, d_{k-2}\}$$i$$\square$1$\Gamma_{k}=$Corollary 2. 3 For every , $1\leq i\leq k-2$ ,a constant operation defined$x\in k$Xi $(x)=\{$ 0otherwise.

Set$\square$otherwise,

$x$

as

$=$

$\ldots,i$$(x, y)\in\rho_{\dot{l}}$prepare the following unary operations.
We
Let , : $karrow k$ be the permutations defined$\sigma$$\ldots$$=\{(x, y)\in k^{2}|c_{0}(x)=\chi_{1}(y)=\cdots=\chi:(y)$,,$\chi:+1(x)=\chi:+1(y)$ $\ldots,\chi_{k-1}(x)=\chi_{k-1}(y)\}$Moreover, we can show the following:
Proposition 2. 5For $f\in O_{k}^{(n)}$ , if $f\in(O_{k}^{(1)})^{*}$
then is a projection. I. , $(O_{k}^{(1)})^{*}=Jk$ .
$f$

.

$e.$

The proof is tedious and omitted

148149

Corollary 2. 6 For every $i=1,2$ ,$N_{i}*=J_{k}$, $k-2$ ,$\ldots$

Proof Suppose that $H_{1}\neq H_{2}$ and.
Without loss of generality we may assume that
there exists aunary operation. Thenit holds that
$H_{1}^{*}=H_{2}^{*}$.

$s\in H_{2}\backslash H_{1}$To summarize, we have the following:$H_{1}^{*}(=H_{2}’)\subseteq(s^{\square })^{*}(=\mathrm{P}\mathrm{o}1 \mathrm{s}’)$$N_{0}$’$(=S_{k}*)=$$N_{k-1}${ $f\in O_{k}|f$ is synchronous}$’=\{f\in O_{k}|f$is synchronous andidempotent}since$H_{2}^{*}=\cap t\in H_{2}$$N_{k-2}^{*}=\ldots=N_{2}*=N_{1}*$ $(=(O_{k}^{(1)})^{*})=J_{k}$3

The Centralizers
Subgroups ofof the$s^{\square }$$H_{1}$$\square$

The Centralizer of the Symmetric Group3.2$S_{k}$$S_{k}$

Next we turn to the centralizers of monoids which
sit “below” the symmetric group ,, monoids, that is, permutation groups.
contained in$S_{k}$$\mathrm{i}.\mathrm{e}.$$S_{k}$

3.1

The Centralizers of the Permutation Groups

As we have seen in the previous section, many different monoids have the same clone $Jk$ as their centralizer. But, surprisingly, the situation is quite different for permutation groups on , i.e., subgroupsof the symmetric group . In fact,-operator
is proved to be an injective mapping on the set of$k$$S_{k}$

Polt’.

It follows from the Kuznetsov criterion thatis
. Hence by Lemma 3.1 we have-expressible by$s\in H_{1}$ , a contradiction.

$\mathrm{p}$(The defintion of a“synchronous” operation aPpears in the next section.),$\mathrm{t}\mathrm{h}\mathrm{e}*$permutation groups.

Marczewski [Ma 64] initiated the study of homogeneous algebras and homogeneous operations. An
operation
is homogeneous if it belongs to
the centralizer of the symmetric group .
$f\in \mathit{0}_{k}$$S_{k}$,
Definition 3. 1 For, we say thatis similar toif the following condition is satisfied:$(y_{1}, \ldots, y_{n})$for any

X: $=xj\Leftrightarrow y:=y\mathrm{j}$$s_{k}$$0\leq i,$

j $<n$ .

Definition 3. 2 An operation $f\in O_{k}^{(n)}$ is synchronous if the following condition is satisfied forin .
any element$k^{n}$$(x_{1}, \ldots, x_{n})$$If|\{x_{1}, \ldots, x_{n}\}|\neq k-1$

Lemma 3. 1 For any subgroup $H$ ofand any$H$ then $s\in H$ .
$s\in S_{k}$ ,isby-expressibleif$(y_{1}, \ldots, y_{n})\in$$(x_{1}, \ldots, x_{n})$$(x_{1}, \ldots, x_{n})$$k^{n}$(1) $f(x_{1},$$x_{n})=x\ell$\ldots ,thenfor have$1\leq\ell\leq n$, and$s^{\square }$$P$

Proof If
subgroup of$s^{\square }$is -expressible by $H$ , which is a
, thencan be expressed as\ldots$S_{k}$$s^{\square }$

,

$t$

as

$s^{\mathrm{o}}=\{(x, y)\in k^{2}|(u^{-1}t)(x)=y\}$$x_{n}\}|=k-1$ and $f(x_{1},$\ldots ,$x_{n})=u$

and, $if|\{x_{1},$\ldots ,for have ufor some , $u\in H$ . This equation cm be rephrased

(1)

$u$

$=$

then

$\in k$$x\ell$for sorne 1
for any$\leq$$f(y_{1}, \ldots, y_{n})=y\ell$

which is sirnilar to.

implies $s=u^{-1}t$ and thus $s\in H$ as desired.

$v$

where

$v$

$(x_{1}, \ldots, x_{n})$Theorem 3. 2 For any subgroups
, if
.
then
$H_{1}\neq H_{2}$$H_{1}^{*}\neq H_{2}^{*}$$H_{1}$

and$H_{2}$

of$\ell$$\leq$$n$

implies$(y_{1}, \ldots,y_{n})\in k^{n}$$(x_{1}, \ldots, x_{n})$, and(2) $u\in k\backslash \{x_{1}, \ldots, x_{n}\}implies.f(y_{1}, \ldots,y_{n})=$$(y_{1}, \ldots, y_{n})$$s_{k}$$(y_{1},$$y_{n})\in k^{n}$\ldots ,$x_{n})$$\mathrm{p}$$s^{\mathrm{O}}=\{(x, y)\in k^{2}|t(x)=u(y)\}$$\mathrm{T}\mathrm{h}\mathrm{i}\mathrm{s}\square$(2) $f(y_{1},$\ldots ,$y_{n})=y\ell$ for any
which is similar to $(x_{1},$ ,.

for any
which is sirnilar to$\in$$k\backslash \{y_{1}, \ldots, y_{n}\}$$\in$$k^{n}$The set of all synchronous operations in.
noted by$S\mathcal{Y}N_{k}$$O_{k}$

is de-

150

Theorem 3. 3 For the symmetric group$S_{k}^{*}=S\mathcal{Y}N_{k}$$S_{k}$on ,$k$“Small” Monoids
Centralizer is Jk

5,

that is, an operation $f\in O_{k}$ is homogeneous if andonly if it is synchronous.

Again, we skip the proof. (See [MMR01].)

whose

Since -operator induces aGalois connection between monoids and clones, it seems natural to consider that asmaller monoid corresponds to alarger
clone and vice versa. However, relatively small, themonoids were found whose centralizer issmallest clone.
$*$$J_{k}$The Centralizer of the Alternating Group3.3$A_{k}$

on , Theorem 3.2
For the alternating group. In the following we show how the
impliesis characterized.
centralizer$k$$A_{k}$

Application of the Kuznetsov

5.1

Criterion :$S_{k}^{*}\neq A_{k}^{*}$$A_{k}^{*}$. ThenTheorem 3. 4 Let $n\geq 1$ andareconditions
following
and
the
only
if
if
on
relationequivalence
every-blocksatisfied for$\{1, \ldots,n\}$ with $h\leq k$ :$f\in O_{k}^{(n)}$$f\in A_{k}^{*}$$h$(1) If h$\leq k$$\theta$-3 then f is a projection on(2) If $h=k-2$ then on$\Pi_{n}(\theta)$$\mathrm{I}\mathrm{I}_{n}(\theta)$.

the operation $f$ iseither a projection or is uniquely determined
by $f(a)\in\{k-2, k-1\}$ where $a\in\Pi_{n}(\theta)$$f$$(0, 1, \ldots, k-3)$ .
satisfies(3) If $h=k-1$ then $fori=0$ , 1 the operation on$\mathrm{s}\mathrm{g}\mathrm{n}a=$Now we look for small monoids whose centralizer.
is$J_{k}$

Proposition 5. 1 The-expressible frvrn

is either a projection or it is uniquelydete rmined by $f(a^{:})=k-1$ .

transposition, namely,is$\tau$$\{\sigma, d_{k-2}\}$$p$$\tau^{\square }=\{(x, y)\in k^{2}|\chi_{0}(x)=\chi_{1}(y)$$\chi_{2}(x)=\chi_{2}(y)$

Proof

,

$\ldots$,, $\chi_{1}(x)=\chi_{0}(y)$ ,$\chi_{k-1}(x)=\chi_{k-1}(y)\}$Similar to the proof of Proposition 2.2.

Corollary 5. 2 Let$M_{1}=\langle\{\sigma, d_{k-2}\}\rangle$$M_{1}*=N_{k-2}^{*}$$f$$H_{k-1,:}$$\langle\{\sigma, d_{k-2}\}\rangle^{*}=N_{k-2}^{*}$$(=J_{k})$.
$\square$. Then.

generates theProof It is well-known thatsymmetric group . So the assertion is clear
Proposition 5.1.
$\{\sigma, \tau\}$$S_{k}$(4) If $h=k$ then for $i=0$ , 1 the operation $f$ on. is a projection.

$\square$$H_{k},|$For the proof refer to$\mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m}\square$$[\mathrm{M}\mathrm{R}03]$

are those
Remark: (1) The permutations in. Thus,generated by , that is,,,
not all permutations are contained in$M_{1}$.

$M_{1}\cap S_{k}=\langle\sigma\rangle$$\sigma$$M_{1}$

4

Monoid whose Centralizer
is$\mathcal{O}_{k}$,Here we look at the largest clone in the lattice. It is obvious that the leastthat is, the clone
monoidconsisting only of the identity oper. We show that no otheration corresponds to.
monoid corresponek to$M_{1}\mathrm{z}$$S_{k}$$\mathrm{i}.\mathrm{e}.$.

(2) An implication from above is that amonoid $M$
does not need to contain all permutations in orderto satisfy $M^{*}=Jk$ .

$L_{k}$$O_{k}$$\{\mathrm{i}\mathrm{d}\}$$O_{k}$$O_{k}$

Proposition 4. 1 For any monoid$M^{*}=O_{k}$Proof$(\Leftarrow)$

if and only if

Clear.

$(\Rightarrow)$

Proposition 2.5 we have

$M\subseteq O_{k}^{(1)}$$M=\{\mathrm{i}\mathrm{d}\}$$M=\{\mathrm{i}\mathrm{d}\}$.

$\Gamma_{k}$’It should be reminded that $\Gamma_{k}=\{\chi:|i\in k\}$ .
Analogous constructions to the one in the preceeding subsection give us the following:,.

Let $M^{*}=O_{k}$ . Then by

Proposition 5. 3 The transposition $(ij)(i\neq j)$.
is -expressible from$p$$\mathrm{i}\mathrm{d}\in M\subseteq M^{**}=O_{k^{*}}\subseteq(O_{k}^{(1)})^{*}=Jk$which shows

5.2Application of the Kuznetsov’$=N_{k-2}$
Criterion :$\square$$\Gamma_{k}$Proof Aconstruction for $\tau=(01)$ was given
in Proposition 5.1. Any transposition $(ij)$ can beconstructed similarly.
$\square$151 151

Corollary 5. 4$\Gamma_{k}*=N_{k-2}*$$k$.

$(=J_{k})$[Da 79] Danil’tchenko, A. F. (1979). On parametricalexpressibility of the functions of -valued logic,
Colloquia Mathematica Societatis Jdnos Bolyai,
28, Finite Algebra and Multiple-Valued Logic,

Proof It is well-known that the set of all transpo
sitions generates the symmetric group. So theassertion is clear.
$S_{k}$$\square$147-159.
[IM59] Ianov, Iu. I. and Mutchnik, AA. (1959). Existence of -valued closed classes without a Finite
basis (in Russian), Dokl. Akad. Nauk., 127, 44-46.
$\mathrm{k}$coixsists only of two-valued operRemark: (1)has no permutations, i.e.,
ations. In particular,$\Gamma_{k}$$\Gamma_{k}$$\Gamma_{k}\cap S_{k}=\emptyset$.

(2) An implication from above is that transitivity
is not necessarily required for amonoid $M$ to sat-

isfy $M^{*}=J_{k}$ .

5.3

The Centralizer of$\langle\Gamma_{k}\rangle\backslash \{\chi_{0},\overline{\chi}_{1}\}$

Even asmaller monoid thancan be proved tohave $Jk$ as its centralizer.
The monoid
generated byconsists ofthe following operations:$\mathrm{r}_{k}$$\Gamma_{k}$$\langle\Gamma_{k}\rangle$$\langle\Gamma_{k}\rangle=\{\chi_{0}$,$\chi_{1}$,$\ldots$,$\chi_{k-1}$,$\overline{\chi}_{0},\overline{\chi}_{1}$,$\ldots$$c_{\mathrm{O}}$where$\overline{\chi}_{\dot{1}}(x)=1-\chi_{i}(x)$$i=0,1$ ,Set$\ldots$

and

,

,

$\overline{\chi}_{k-1}$$c_{1}$,,$\mathrm{i}\mathrm{d}_{k}\}$$c_{\dot{\mathrm{s}}}(x)=i$for all, $k-1$ .
, that is,$\Theta_{k}=\{\chi_{1}, \ldots, \chi_{k-1},\overline{\chi}_{0},\overline{\chi}_{2}, \ldots,\overline{\chi}_{k-1}, c_{0}, c_{1}, \mathrm{i}\mathrm{d}_{k}\}$.

.
It is readily verified thatis asubmonoid of
we can prove the following:
For this monoid$\langle\Gamma_{k}\rangle$$\Theta_{k}$Proposition 5. 5 Let $k>2$ . Then $_{k}^{*}=Jk$ .
Thus the centralizer$J_{k}$’of$\Theta_{k}$$_{k}$[MMR 01] Machida, H., Miyakawa, M. and Rosenberg,
I. G. (2001). Relations between clones and fullmonoids, Proc. 31st Int. Symp. Multiple-Valued
Logiq IEEE, 279-284.
[MMR 02] Machida, H., Miyakawa, M. and Rosenberg,
I. G. (2002). Some result8 on the centralizers of
monoids in clone theory, Proc. S2st Int. Symp.
Mikiple-Valued Logic, IEEE, 10-16.

[MR03] Machida, H. and Rosenberg, I. G. (2003). On
the Centralizers of Monoids in Clone Theory, submitted.
[Ma 64] Marczewski, E. (1964). Homogeneous algebras
and homogeneous operations, Fund. Math., 56, 81-

103.
[PK79] P\"oschel, R. and Kaluzhnin, L. A. (1979).
Funkbionen- und Relationenalgebren’ Deutscher
Verlag der Wissenschaften, 259pp.

$\mathrm{O}-k=\langle\Gamma_{k}\rangle\backslash \{\chi 0,\overline{\chi}_{1}\}$$\Theta_{k}$[Ku61] Kuznetsov, A. V. (1961). Lattices with closureand criteria for functional completeness (in Russian), Uspehi Mat Nauk, 16/2(98), 201-202.

is the least clone. The proof is long and omitted here. (See$[\mathrm{M}\mathrm{R}03])$[Po 41] Post, E.L. (1941). The two valued iterative systems of mathematical logic, Ann. Math. Studies, 5,
Princeton Univ. Press.
[Ro 70] Rosenberg, I.G. (1970). On the functional
completeness in many-vfiued logics (Uber die
funktionale Volkt\"andigkeit in dem mehrwertigen
Logiken, in German), Rozpravy Ceskoslovensk\’e.
Akad. ved. Rada Mat. Pramd. V&d., 80, 3-93.

[Ro 78] Rosenberg, I. G. (1978). On a Galois connection between algebras and relations and its
plications, Contributions of General Algebra, 273-$\mathrm{a}\mathrm{p}\sim$

References[Bu 87] Burris, S. (1987). Primitive positive clones
which are endomorphism clones, Algebra Universalis, 24, 41-49.
[BW87] Burris, S. and Willard, R. (1987). Finitely
many primitive positive clones, Proc. $Amel\dot{7}can$Mathematical Society, 101, N0.3, 427-430.
[Co 65] Cohn, P. M. (1965). Universal Algebra, Harperand Row, 412pp.

[Da 77] Danil’tchenko, A. F. (1977). Parametric expres8ibi1ity of functions of three-valued logic (inRussian), Algebra i Logika, 16, 397-416; English
traslation: Algebra and $L\wp\dot{\iota}c(1977)$ , 16, 266-280.

289.

[Sza 78] Szab6, L. (1978). Concrete representation ofrelated structures of universal algebras. I, Act,a.
Sci. Math., 40, 175-184.
[Sza 85] Szab\’o, L. (1985). Characterization of clones
acting bicentrally and containing aprimitive
group, Acta. Cybernet., 7, 137-142.

[Sze 86] Szendrei, \’A. (1986). Clones in Universal Algebra, SMS Series 99, Les Presses de L’Universit\’e deMontr\’eal, 166pp