A Note on Witnesses of Centralizing Monoids (Algebraic system, Logic, Language and Computer Science)

A Note

on

Witnesses

of

Centralizing

Monoids

Hajime

Machida Ivo

G.

_Rosenberg

Tokyo, Japan Montreal,Canada

Abstract

We consider multi‐variable functions definedover afixed finitesetA. Acentralizing

monoid M isasetof_unaryfunctionsonA whichcommutewith all membersofsomeset

Fof functionsonA_,where Fiscalledawitness of M. We show thateverycentralizing

monoid hasawitness whosearitydoesnotexceed

_|A|

. Thenwepresentamethodto

countthe number of_centralizing monoids which havesets ofsome _specific functions

as their witnesses. Finally, some results on the three‐element set E3 are reported

concerningwitnesses_consistingof_{binary idempotent functions, majority}functions or

ternarysemiprojections.

Keywords: commutation;centralizing monoid; witness

1

Preliminaries

LetA beanon‐emptyset. For

n\geq 11\mathrm{e}\mathrm{t}\mathcal{O}_{A}^{(n)}

denote the set ofn‐variable functions definedon

\mathrm{F}_{0\mathrm{r}n>0\mathrm{a}\mathrm{n}\mathrm{d}1\leq $\iota$\leq n\mathrm{t}\mathrm{h}\mathrm{e}v\mathrm{t}\mathrm{h}(n-\mathrm{v}\mathrm{a}\dot{\mathrm{n}}\mathrm{a}\mathrm{b}1\mathrm{e})\mathrm{n}}A,\mathrm{i}.\mathrm{e}.,\mathcal{O}_{A}^{(n)}=A^{A^{n}\infty}\mathrm{a}\mathrm{n}\mathrm{d}\mathcal{O}_{A}

denotet\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{i}_{\mathrm{J}}nctionsdefinedo

\displaystyle \mathrm{n}A,\mathrm{i}.\mathrm{e}.,\mathcal{O}_{A}=\bigcup_{n=1}\mathcal{O}_{A}^{(n)}

projection

e \mathrm{i}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{f}unction i

\mathcal{O}_{A}^{(n)}

which

always

takesthe valueof the i‐thvariable. The setof

_projections

isdenoted

_by

\mathcal{J}_{A}. A clone

overAisasubset C of

\mathcal{O}_{A}

whichisclosed under

(functional)

_composition

and includes

_{\mathcal{J}_{A}.}

For _{m,n\geq 1,}

f\in \mathcal{O}_{A}^{(n)}

and

g\in O_{A}^{(m)},

_f

commuteswith g, or

f

andg commute, ifthe

equation

f(g(^{t_{C_{1}),\ldots,g(}t_{C_{n}))}}=g

(

f

(r1),

..._,

f

(rm))

holdsforeverym\times nmatrixover Awiththe i‐throw

r_{i}(1\leq i\leq m)

andthe

j‐th

column

c_{\mathrm{j}}(1\leq j\leq n)

. Wewrite

f\perp g

when

f

commuteswithg.

In this paper we areconcerned with a

particular

caseof_commutation, that

_is,

commu‐

tation ofan n‐variablefunctionwith a_unary function. It follows from the definition above

that,

for

f\in \mathcal{O}_{A}^{(n)}

and

g\in \mathcal{O}_{A}^{(1)},

_f

_{and g commute}if

f(g(x_{1}), \ldots, g(x_{n}))=g(f(x_{1}, \ldots, x_{n}))

holdsforallx_{1},..._,

x_{n}\in A.

Fora subset F of

O_{A}

theset of functions in

_{\mathcal{O}_{A}}

whichcommutewith all members ofF

isdenoted

_by

F^{*},

i.e.,

F^{*}=

_{

_{g\in \mathcal{O}_{A}|g\perp f}

for all

_{f\in F}

_}.

When

_F=\{f\}

we write

f^{*}

instead ofF^{*}.

Also,

we write F^{**} for

(F^{*})^{*}

. The

following

Lemma 1.1 For any

F, G\subseteq \mathcal{O}_{A},

F\subseteq G^{*}

if

and

_{only if}

_{G\subseteq F^{*}.}

Asubset C of\mathcal{O}_{A} isacentralizer ifthereisasubsetFof_{O_{A}}

_satisfying

C=F^{*}. Forany

subset Fof

_{O_{A}}

, the centralizer F^{*} is

clearly

aclone. A subset M of

\mathcal{O}_{A}^{(1)}

isamonoid ifit

isclosed under _composition and contains the

_identity.

Since_anycentralizer F^{*} isa

clone,

the_{unary part}ofF^{*}, i.e.,

F^{*}\cap \mathcal{O}_{A}^{(1)}

, isamonoid.

A subset M of

\mathcal{O}_{A}^{(1)}

is a

centralizing

monoid if there exists a subset F of

\mathcal{O}_{A}

which

satisfies

M=F^{*}\cap \mathcal{O}_{A}^{(1)}

. Inother

words,

a

centralizing

monoidistheunarypartofsome

centralizer. The set F inthe definition ofa

centralizing

monoidM iscalledawitnessofM.

The

_centralizing

monoidM will be denoted

_by

_M(F)

if F is a witness ofM. When F is

\{f\}

we

_simply

write

_M(f)

for

_M(\{f\})

.

It iswell‐known_{and easy to}see

_that,

for asubset M of

\mathcal{O}_{A}^{(1)},

Mis a

centralizing

monoid

if and

_only

if Mistheunarypart ofM^{**},

i.e.,

M=M^{**}\cap \mathcal{O}_{A}^{(1)}.

2

_Arity

of Witnesses

We shall considerafundamental

problem

onthe

arity

ofwitnesses: How smallcanthe

arity

ofawitness be?

Definition 2.1 Fora

(non‐empty)

finite

subset W

of \mathcal{O}_{A}

_{, the}

_arity

_of

_W is

_defined

to be

the maximal_arty

_of

all

_functions

inW.

We establish the

_following

theorem.

Theorem2.1

_{Every centralizing}

monoidM onA hasawitnesswhose

_arty

isless than or

equal

to

_|A|.

Proof follows afteradefinition andalemma.

Definition 2.2 For n>1 let

f\in \mathcal{O}_{A}^{(n)}

be an n‐variable

function

and _i,

j\in \mathcal{N}

_satisfy

1\leq i<j\leq n

.

Define

(n-1)

‐variable

function

f_{i\equiv j}\in \mathcal{O}_{A}^{(n-1)}

by

f_{i\equiv j} (xl,

..._,x_{n-1}

)

=

f

(xl,

..._,xi,..._,x_{j-1}_,x_{i},x_{j+1},\ldots_, x_{n-1}

)

for

allx_{1},..

.,x_{i},.._.,x_{j}_,..._,x_{n}\in A. The

function

f_{i\equiv j}

is called

(i, j)

‐minor

of f

. Denote

by

Minor

_(f)

theset

_of

allminors

_{of f}

, i.e.,

Minor

_(f)

=

\{f_{i\equiv j}|1\leq i<j\leq n\}

Lemma2.2 Let

f\in \mathcal{O}_{A}^{(n)}

bean n‐variable

junction.

Ifn>|A|

then

M(f)=M(\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f))

,

i. e.,

f^{*}\cap \mathcal{O}_{A}^{(1)}=\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f)^{*}\cap \mathcal{O}_{A}^{(1)}.

Proof

₍

\subseteq

₎

: Let

s\in \mathcal{O}_{A}^{(1)}

bein

M(f)

. Itfollowsthat

s\perp f

, whichis

equivalent

to

saying

that

s

(

f

(xl,

... x_{n}

))

=

f(s(x_{1}), \ldots, s(x_{n}))

holds for all x_{1},..._,

x_{n}\in A

. In

particular,

for anypair

(i, j)

such that

1\leq i<j\leq n

we

have

for all x_{1},...

,x_{n}\in A

satisfying

x_{i}=x_{\dot{}}. This

implies

s\perp f_{i\equiv j}

. Hence s

belongs

to

M(\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f))

,whichconcludes

M(f)\subseteq M(\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f))

.

(

\supseteq

)

: We_{prove the}

_{contraposition,}

that _is, if

s\not\in f^{*}

then

s\not\in \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f)^{*}

_{for any}

s\in \mathcal{O}_{A}^{(1)}.

Now the condition

_{s\not\in f^{*} implies}

_{s_{7}\mathrm{L}f}

, whichmeansthat

s

(

f

(al,

..._,a_{n}

))

\neq

f(s(a_{1}), \ldots, s(a_{n}))

holds for some _{a_{1}},..._,

a_{n}\in A

. Since

n>|A|

_, there existi,

j\in \mathcal{N}

satisfying 1\leq i<j\leq n

and a_{i}=a_{j}. Fornotational

simplicity,

let i=n-1 and j=n. Thenwe have

s(f_{n-1\equiv n}(a_{1}, \ldots, a_{n-1})) \neq f_{n-1\equiv n}(s(a_{1}), \ldots, s(a_{n-1}))

,

which

_{implies s_{ $\eta$}Lf_{n-1\equiv n}}

. Thus

s\not\in \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f)^{*}

and, consequently,

M(f)\supseteq M(\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f))

.

\square

ProofofTheorem2.1 LetW beawitnessofa

centralizing

monoid M. For each

f

in

W,

if

f\in \mathcal{O}_{A}^{(n)}

and

_n>|A|

,

replace f

with all minors of

f

. The set

(W\backslash \{f\})\cup \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{r}(f)

is

awitness ofM, duetoLemma2.2.

Repeat

this

procedure

untilnofunction inthe witness

has

_arity

_greaterthan

_|A|

. Thenwe getadesired witness forM. \square

3

_Strategy

LetHbeasubset of

\mathcal{O}_{A}

.

Suppose

wewant todetermine all

centralizing

monoidsonA which

have subsets ofHastheir

_witnesses,

or

simply

thenumberofsuch

centralizing

monoids. If

h isthe number of elements inHthe number of subsets ofH is2^{h},whichtendstobe

huge

and, therefore,

insuchcases, itrequiressometricktoachieve the task above.

Our_strategytoavoidthis

_difficulty

isthe

_following.

Instead of

_starting

froma function

f

inHand determine

M(f)=f^{*}\cap \mathcal{O}_{A}^{(1)}=\{s\in \mathcal{O}_{A}^{(1)}|f\perp s\}

,we do it inthereverseway.

Namely,

we startfroma_unaryfunction

s\in \mathcal{O}_{A}^{(1)}

, and consider the

following

set.

C_{H}(s) = s^{*}\cap H (=\{f\in H|f\perp s\})

Duetothenext_proposition,weasserts: Thereexistsa

bijection

between thesetof central‐

izing

monoids

_having

subsets ofHastheir witnessesand theset

_consisting

of

_{C_{H}(s1)\cap\cdots\cap}

C_{H}(s_{r})

for

_{1\leq r\leq|A|^{|A|}}

ands_{1},..._,

s_{r}\in \mathcal{O}_{A}^{(1)}.

Proposition

3.1 Let H be a _{non\rightarrow empty} subset

of

\mathcal{O}_{A} and

C_{H}(s)=s^{*}\cap H

_for

_every

s\in \mathcal{O}_{A}^{(1)}.

(1)

For anynon‐emptysubsetF

of

H, let G be theset

of functions defined by

G=\cap\{C_{H}(s)|s\in \mathcal{O}_{A}^{(1)}, F\subseteq s^{*}\}.

Then,

M(F)=M(G)

, thatis, the

centralizing

monoid

having

F as its witness is the

same asthe

centralizing

monoid

having

G asits witness.

_(A

witness F canbe

replaced

(2)

Foranys_{1},...

,s_{r},t_{1},...

,

t_{q}\in \mathcal{O}_{A}^{(1)}

, let

G_{1}=\displaystyle \bigcap_{i=1}^{r}C_{H}(s_{i})

and

G_{2}=\displaystyle \bigcap_{j=1}^{q}C_{H}(t_{j})

.

If

M(G_{1})=M(G_{2})

thenG_{1}=G_{2}.

Proof

₍₁₎

Itsufficestoshowthe

_following

_(i)

and

_(ii)

for _any

s\in \mathcal{O}_{A}^{(1)}:(\mathrm{i})s\in G^{*}

_implies

s\in F^{*} and

_(ii)

s\in F^{*}

_implies

s\in G^{*}.

(i)

Obvious from _{F\underline{\subseteq}} G.

_(ii)

Condition s\in F^{*}

_implies

F\subseteq s^{*}

_(Due

to Lemma

_1.1).

Then, by

thedefinition of G,wehave

G\subseteq C_{H}(s)

,which

implies

G\subseteq s^{*}

and, hence,

s\in G^{*}.

(2)

Proof

_{by contraposition.}

Assume that G_{1} and

_{G_{2}}

are different.

_Then,

w.l._{0.\mathrm{g}.}, we

may assumethat thereexists

_f

in

_{G_{2}\backslash G_{1}}

. Thenwe have

f\not\simeq s_{i}

for some

i\in\{1, . . . , r\},

which

_implies

_{s_{i}\not\in M(G_{2})}

.

However,

since

G_{1}\subseteq C_{H}

(si),

we have

s_{i}\in M(G_{1})

. Hencethe

conclusion,

M(G_{1})\neq M(G_{2})

, follows. \square

Corollary

3.2 The number

_of

the

_centralizing

monoids

_having

subsets

_of

H as their wit‐

nessesis

equal

to the number

_of

sets

_{\displaystyle \bigcap_{s\in S}C_{H}(s)}

_for

all

S\subseteq \mathcal{O}_{A}^{(1)}.

Proofisimmediate from

_Proposition

3.1.

In this paper, we are concerned

only

with the numbers of

_centralizing

monoids

_having

specific

setsastheirwitnesses.

However,

ifwe_want,not

_only

toobtainthe numbers of such

centralizing monoids,

but also todetermine

_explicitly

elements ofeach ofsuch

_centralizing

monoids,

the

_following

_propertyisuseful.

For unaryfunctionss_{1},..._,

s_{r}\in \mathcal{O}_{A}^{(1)}

let

S=\{s_{1}, . . . , s_{r}\}

. Then Sissaidto\mathrm{b}\mathrm{e}* ‐mavimal

if

_{C_{H}(s_{1})\cap\cdots\cap C_{H}(s_{r})\not\leqq C_{H}(t)}

for_any

t\in \mathcal{O}_{A}^{(1)}\backslash S.

Proposition

3.3 Fors_{1}, ..._,

s_{r}\in \mathcal{O}_{A}^{(1)}

_,

if

\{s_{1}, . . . , s_{r}\}is*

‐maximal then

\{s_{1}, . . . , s_{r}\}

is a

centralizing

monoid

_having

_{C_{H}(s_{1})\cap\cdots\cap C_{H}(s_{r})}

asits witness.

4

_Specific

_Types

of

_Centralizing

Monoids

on

E3

Fromnow_on, we deal withthe casewhere the base setAis

_{E_{3}=\{0}

,

1,

2

\}

. Wewrite

\mathcal{O}_{3}^{(n)}

and

_{\mathcal{O}_{3}}

for

\mathcal{O}_{A}^{(n)}

and\mathcal{O}_{A},

respectively.

Inthepast

work,

centralizers onE3 were

discussed,

e.g., in

[Da79].

Due to Theorem 2.1 in Section

_2,

_every

_centralizing

monoidon E3 has a witness whose

arity

isless thanor

equal

to 3.

We haveconsidered witnesses which consist ofsetsof functionsin eachofthe

_following

threeclasses:

_{Binary idempotent functions, majority}

functions and_ternary

_{semiprojections.}

Thereasonbehind the selection of these classes of functionscomesfrom the fact that minimal

functions on _{E_{3}}, except unary

functions,

all

belong

to these

classes,

which is the result of

B.

_Csákány

_([Cs83])

obtainedin 1983.

For the reader’s

_sake,

we reviewthe definition of each of these functions.

(i)

For

f\in \mathcal{O}_{3}^{(2)},

_f

isa

binary

idempotent function

if

f(x, x)=x

forall

_{x\in E_{3}.}

(ii)

For

f\in \mathcal{O}_{3}^{(3)},

_f

isa

majority

function

if

f(x, x, y)=f(x, y, x)=f(y, x, x)=x

for all

(iii)

For

f\in \mathcal{O}_{3}^{(3)},

_f

isa

semiprojection

ifthereexists

i\in\{1

,2,3

\}

suchthat

f(x_{1}, x_{2}, X3)=

x_{i} whenever

|\{x_{1}, x_{2}, x_{3}\}|<3

for allx_{1}, x_{2},X3\in E_{3}.

Thus,

for the set H in Section _3, we took _up the set of

_majority

_functions,

the set of

ternary

semiprojections

and the set of

_{binary idempotent functions,}

and enumerated all

centralizing

monoids whichhave those setsastheirwitnesses

_{([GMR15], [MR16]).}

Proposition

4.1

_(i)

The number

_{of centralizing}

monoids on

E3

which havesets

_of

_binary

idempotent functions

as theirwitnesses is 67.

(ii)

The number

_{of centralizing}

monoids onE3 which have sets

of

majority

functions

as

their witnesses is15.

(iii)

Thenumber

_{of centralizing}

monoidson

E3

which have sets

_of

_ternary

_{semiprojections}

as theirwitnesses is 13.

More detailed

description concerning

the statements

_(ii)

and

_{(iii) (respectively, (i))}

is

foundin

_{[GMR15] (respectively, [MR16]).}

Note that thenumber of

_{binary idempotent}

functions on

E_{3}

, as well asthe number of

ternarymajorityfunctionson

E_{3}

,is3^{6}=729.

Also,

ifwe mean

by

aternary

semiprojection

only

such_ternary

_{semiprojection}

_{p which takes the}value of the first_argumentwhenever at least twoof the_arguments

_{coincide, i.e.,}

_{p(x_{1}, x_{2}, X3)=x_{1}}

whenever

_{|\{x_{1}, x_{2}, x_{3}\}|<3}

,then

the number of such functions on E3 is

3^{6}=729

. We observe that the numbers

67,

15 and

13aresmallas

_compared

with the number729 and

_remarkably

smallas

compared

with the

cardinality

of thepower setof each class ofsuch

functions,

whichis2^{729}.

References

[Cs83]

Csákány, B.,

All minimal clones onthe three element_set, Acta

Cybernet.,

_{6, 1983,}

227‐238.

[Da79]

Danil’čenko,

A.

_F.,

On

_{parametrical expressibility}

ofthefunctions of k‐valued

_logic,

Colloquia

Mathematica Societatis János

_Bolyai,

_28,Finite

_Algebra

and

_{Multiple‐Valued}

Logic,

1979, 147‐159.

[GMR15]

Goldstern, M., Machida,

H. and

_Rosenberg,

I.

_G.,

Some classes of

_centralizing

monoidson athree‐element_set,

Proceedings 45th

International

Symposium

on

Multiple‐

Valued

_{Logic, IEEE, 2015,}

205‐210.

[MR16]

Machida,

H. and

_Rosenberg,

I.

_{G., Centralizing}

monoids on a three‐element set

relatedto

_{binary idempotent functions, Proceedings 46th}

International

_Symposium

on