Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

Completeness of uniformly delayed op erations 123

for all j ≥ 0. From ∆

∩ ρ

⊆ ω

we get ρ

= ∅ and (ii) yields ρ

⊇ ω

. From this it follows

that τ

is a reﬂexive binary relation on k.Moreover,τ

is distinct from k

because ∆

⊆ ρ

Thus τ := (τ

,τ

,...) is a proper binary polyrelation. Letting a

=  for all m ∈ B

i

and

 =1, 2, γ = {(a

,...,a

)} and g((a

,...,a

)) = {0} we obtain from Lemma 3.11 that the

polyrelation τ belongs to [ρ] in contradiction to (i). This proves the claim. 2

Set F := Pold ρ and F

= {f | (f,i) ∈ F } for all i ∈ N.

Claim 2: F

⊆ C for i =1,...,p−1.

Proof: Suppose to the contrary that there exist 0 <i<p, n ≥ 1andf ∈ F

(n)

\ C.Then

fx = fy for some x =(x

,...,x

) ∈ k

and y =(y

,...,y

) ∈ k

.Forj =1,...,h and

l =1,...,n set z

:= x

if j ∈ B

and z

:= y

if j ∈ B

. Clearly each column of the h × n

matrix Z =[z

] belongs to ∆

⊆ ρ

and from f ∈ Pol(ρ

,ρ

)thevaluesoff in the rows

of Z form b ∈ ρ

. Clearly b ∈ ∆

, and thus by Claim 1 we have z ∈ ∆

∩ ρ

⊆ ω

.This

contradiction shows that F

\ C = ∅; i.e., F

⊆ C and the claim is proved. 2

Claim 3: C ⊆ F

Proof: From the assumption (ii) we get C ⊆ Pol ρ

for all 0 ≤ j<pand thus C ⊆



j∈N

Pol ρ

= F

, proving the claim. 2

Now clearly e ∈ F

.Asρ ∈ Ξ

,thesetF =Poldρ is incomplete. Now Proposition 2.6

(for δ = 0) yields that F

is not primal. By Claim 3 also C ⊆ F

. It is implicit in [Ro70]

that there exists a reﬂexive relation σ on k such that F

⊆ Pol σ and Pol σ is maximal in O.

Together with F

⊆ C ⊆ F

⊆ Pol σ (i =1,...,p− 1) we get F ⊆ Pol σ

∗

in contradiction to

ρ ∈ Ξ

. 2

Recall that for a clutter E in E

the relation ∆



∈E

∆



was deﬁned in 3.6.

4.11 Lemma Let ρ satisfy the assumptions of Lemma 4.10 and let E be a clutter in E

such

that (i) each θ ∈ E has exactly two blocks and (ii)



E is the least equivalence relation. Then

∆

⊆ ρ

implies ρ

= k

Proof Put T := {t ∈ p | ∆

⊆ ρ

}. Suppose to the contrary that ρ

⊂ k

for some u ∈ T .

For δ ≥ 0 put λ



t∈T

δ+t

. Clearly ∆

⊆ λ

⊆ ρ

⊂ k

. Suppose that ∆

⊆ ∆

for

some θ ∈ E

.Then



E ⊇ θ and from (ii) we obtain that θ is the least equivalence relation

on {1,...,h} and ∆

= k

. This shows that λ

is nontrivial and therefore λ := (λ

,λ

,...)

is proper and λ ∈ [ρ] by Lemma 3.11.

Denote by s the least positive integer such that t

+ s ∈ T for all t ∈ T (where, as in the

proof of Theorem 4.2, t

+ s denotes the least integer 0 ≤ z<psuch that z ≡ t + s (mod p)).

Clearly s ≤ p and s divides p.Thusλ has period s and in view of ρ ∈ Ξ

,wegetλ ∈ Ξ

.Now

λ also satisﬁes the assumptions of Lemma 4.10 and therefore ∆

⊆ λ

for some 0 <i<s,

proving t

+ i ∈ T for all t ∈ T in contradiction to the minimality of s.Thusρ

= k

for all

u ∈ T . 2

4.12 Proposition There is no minimal quaternary polyrelation.

Proof Suppose to the contrary that ρ =(ρ

,ρ

,...) is a minimal quaternary polyrelation of

period p and let E consist of the three equivalence relations on {1,...,4} with two 2-element

blocks each. Applying Lemmas 4.9 and 4.11 we obtain the contradiction that every ρ

either primitive or trivial. 2

124 T.HikitaandI.G.Rosenberg

We consider ternary polyrelations. Recall that

∆

= {aab | a, b ∈ k}, ∆

= {aba | a, b ∈ k}, ∆

= {abb | a, b ∈ k},

= {aaa | a ∈ k},andν

= ρ

∩ι

for all i ≥ 0.

4.13 Lemma Let ρ ∈ Ξ

be ternary with period p and such that (i) [ρ] contains no proper

binary polyrelation and (ii) ρ

= ∅ or ρ

⊇ ω

for all 0 ≤ j<p. Then for all j ∈ p

∈ I = {∅,ω

, ∆

Proof Suppose to the contrary that some ν

is nontrivial. By Lemma 4.6 we have ν

∩ ι

=∆

for a clutter E in E

with |E|≥2. Then each ε ∈ E has exactly two blocks

and the relation



E is the least equivalence relation on {1, 2, 3}. Applying Lemma 4.11 we

get ρ

= k

, a contradiction. Thus ν

is trivial and ν

∈ I. 2

4.14 Lemma If ρ =(ρ

,ρ

,...) is a minimal ternary polyrelation then each nontrivial ρ

has ν

= ω

Proof Suppose to the contrary that there is a nontrivial ρ

with ν

= ω

. By Lemma 4.6

for all 0 ≤ j<peither ρ

= ∅ or ρ

⊇ ω

. By Lemma 4.13 then ν

∈{∆

, ∆

}.By

an appropriate exchange of coordinates we can get ν

=∆

(i.e., we apply Lemma 3.11 to

 = p = h =3,Γ=(γ, g)withγ = {(a, b, c)}, g((a, b, c)) = {0} where {a, b, c} = {1, 2, 3} is

suitably chosen). By Lemma 4.7 we have Pr

= k

; i.e., for arbitrary x, y ∈ k there exists

w so that xyw ∈ ρ

.Forl =0,...,p−1andn =3,...,k put

= {x

...x

| x

uv ∈ ρ

(i =1,...,n)forsomeu, v ∈ k}.

Clearly the n-ary polyrelation τ

=(τ

,τ

,...) thus deﬁned belongs to [ρ] (indeed, in

Lemma 3.11 set τ

=Γ→

ρ where  = n +2, p = n, h =3,Γ=(γ,g)withγ =

{i(n +1)(n +2)| i =1,...,n} and g(a)={0} for each a ∈ γ). By induction on n =3,...,k

we prove that τ

= k

. First we prove that τ

⊇ ι

.Letx, y ∈ k be arbitrary. Then xyw ∈ ρ

for some w.Usingxyw ∈ ρ

and yyw ∈ ∆

⊆ ρ

we get xxy ∈ τ

. Similarly xyx ∈ τ

and

xxy ∈ τ

proving τ

⊇ ι

.Nowτ

is not totally reﬂexive by Theorem 4.2 and therefore

= k

for all i ≥ 0.

Suppose that 3 ≤ n<kand τ

= k

.Letx

,...,x

∈ k be arbitrary. By the inductive

assumption x

uv ∈ ρ

(j =1,...,n)forsomeu,v ∈ k. Thus for all 1 ≤ j<l≤ n we have

...x

l−1

l+1

...x

∈ τ

n+1

proving that ι

n+1

⊆ τ

n+1

. Again by Theorem 4.2 we have

n+1

= k

n+1

completing the induction step. Now, τ

= k

means that there are u, v ∈ k

such that xuv ∈ ρ

for all x ∈ k.Inparticular,vuv ∈ ρ

shows u = v. However xuu ∈ ρ

holds only for x = u. This contradiction proves the lemma. 2

4.15 We need the following result from [Ro70]. Recall that for a prime number q an elemen-

tary abelian q-group is an abelian group G;+, −, 0 such that qx =0(whereqx = x + ···+x

with q summands) for all x ∈ G. Such a ﬁnite group is isomorphic to the additive struc-

ture of a vector space over the Galois ﬁeld GF (q). More explicitly, G q

; ⊕ where for

x =(x

,...,x

) ∈ q

and y =(y

,...,y

) ∈ q

, x ⊕ y := (x

+ y

,...,x

+ y

) (the mod q

addition a

+ b is the remainder of the division of a + b by q). Put m

◦

:= {xyz(x − y + z) |

x, y, z ∈ k}.

Completeness of uniformly delayed op erations 125

4.16 Lemma Let λ = µ

∪ ω

be a ternary relation on k where ∅ = µ

⊆ σ

. Suppose that

(i) Pol λ ⊆ Pol τ for no binary nontrivial relation τ , (ii) Pol λ ⊆ Pol τ for no nontrivial at

most k-ary totally reﬂexive relation τ and (iii) Pol λ ⊆ Pol τ for no ternary relation τ of the

form µ ∪ ∆

or µ ∪ ∆

∪ ∆

with ∅ = µ ⊆ σ

. Then there exists an elementary abelian

q-group G on k such that Pol λ ⊆ Pol m

◦

Now we can prove:

4.17 Proposition There is no minimal ternary polyrelation.

Proof Suppose to the contrary that there exists a minimal ternary polyrelation ρ.Letρ

nontrivial. By Lemma 4.14 then ν

= ω

. Now by minimality, ρ

satisﬁes the assumption (i)

of Lemma 4.16. The assumption (ii) is true due to Theorem 4.2. Next (iii) holds on account

of Lemma 4.14. From Lemma 4.16 it follows that there is a prime q, an elementary abelian

q-group G on k and a quaternary polyrelation τ ∈ [ρ] such that τ

= m

◦

(the construction

from [Ro70] yielding m

◦

gives τ when applied to the polyrelation ρ). It is easy to verify that

⊇ ω

whenever τ

is nonempty (due to ρ

⊇ ω

whenever ρ

= ∅).

It follows that ρ

⊆ Pol τ

. Finally m

◦

⊇ ∆

12−34

∪ ∆

14−23

because x − x + y ≈ y and

x − y + y ≈ x). Since E = {{{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}} is such that



E is the least

equivalence relation on {1, 2, 3, 4}, we have a contradiction to Lemma 4.11. 2

Summing up:

4.18 Theorem The set Ξ

of proper periodic unary and binary polyrelations is B-generic.

5 Unary Polyrelations

5.1 In this section we study the set V of proper periodic unary polyrelations on k.Call

ρ ∈ V with period p optimal if

(1) p =min{p

| τ ∈ V ∩[ρ]} and

(2) |ρ

| + ···+ |ρ

p−1

|≤|λ

| + ···+ |λ

p−1

| whenever λ ∈ V ∩ [ρ]andp

= p.

Thus for optimality our primary concern is to have the shortest possible period p among

the proper unary polyrelations from [ρ] while our secondary concern is to have the least

possible sum of the sizes of the relations ρ

,...,ρ

p−1

(amongst those with the shortest period

p in [ρ]). In 5.2–5.8, ρ is an optimal unary polyrelation with period p. We need the following

technical lemma.

5.2 Lemma If τ ∈ V ∩ [ρ] satisﬁes τ

⊆ ρ

for all i ≥ 0 and p

≤ p

then τ = ρ.

Proof From optimality we get p

= p

= p.Fromτ

⊆ ρ

(i =0,...,p− 1) we have

|τ

| + ···+ |τ

p−1

|≤|ρ

| + ···+ |ρ

p−1

|. (5.1)

By optimality also |ρ

|+ ···+ |ρ

p−1

|≤|τ

|+ ···+ |τ

p−1

|, so (5.1) holds with equality. In view

of τ

⊆ ρ

we get τ

= ρ

for i =0,...,p−1andτ = ρ. 2

Now we have:

126 T.HikitaandI.G.Rosenberg

5.3 Lemma The sets ρ

,...,ρ

p−1

are pairwise disjoint.

Proof Suppose to the contrary that ρ

∩ ρ

= ∅ for some 0 ≤ i<j<p.Putr := j − i

and τ

:= ρ

∩ ρ

n+r

for n =0,...,p− 1. Now τ

= ρ

∩ ρ

= ∅ shows τ to be proper. It

can be checked directly that τ =Γ→

ρ where  = p = h =1andΓ=(γ,g)hasγ = {(1)}

and g((1)) = {0,r}. AccordingtoLemma3.11wehaveτ ∈ [ρ] and thus τ ∈ V ∩ [ρ].

Moreover, p

≤ p and τ

⊆ ρ

for all x ≥ 0. Applying Lemma 5.2 we get τ = ρ.Thus

∩ρ

i+r

= τ

= ρ

for all i =0,...,p−1andsoρ

⊆ ρ

i+r

.Thusforevery0≤ i<pwe have

⊆ ρ

i+r

⊆···⊆ρ

i+pr

= ρ

proving ρ

= ρ

i+r

= ···= ρ

i+(p−1)r

.Denotebys the greatest

common divisor gcd(p, r)ofp and r. It is easy to check that for all i =1,...,s− 1wehave

that ρ

= ρ

i+s

= ···= ρ

i+p−s

and therefore ρ is periodic with period s. The minimality of p

shows p = s =gcd(p, r), a contradiction to 0 <r<p. This proves the lemma. 2

We need the following simple observation.

5.4 Lemma Let ρ =(ρ

,ρ

,...) be an h-ary periodic polyrelation on k of period p.Then



=(ρ

,ρ

,...) is periodic of period p and

Pold ρ =Poldρ



Proof Let  = p = h and for i =1,...,p− 1setΓ

=(γ,g

)whereγ = {(1,...,h)} and

((1,...,h)) = {i}. Then by Lemma 3.11 clearly ρ

(i)

=Γ

→

ρ satisﬁes Pold ρ ⊆ Pold ρ

(i)

In particular, ρ



= ρ

(1)

and (ρ



)

p−1

= ρ show

Pold ρ ⊆ Pold ρ



⊆ Pold(ρ



)

(p−1)

=Poldρ.

Thus we can turn around the cycle of ρ at will without eﬀecting the corresponding uniform

clone. Set I := {i ∈ p | ρ

= ∅}. According to Lemma 5.4 henceforward we assume 0 ∈ I.

We have:

5.5 Lemma I = {0,r,...,p− r} for some divisor r of p.

Proof If I = {0} then clearly r = p. Thus suppose that |I| > 1. Denote by r the least

positive integer such that i

+ r ∈ I for some i ∈ I (where again i

+ r is the remainder

of division of i + r by p); in other words, r is the least distance between two consecutive

members of I on the cycle. For x ≥ 0 put



if x

+ r ∈ I,

∅ otherwise.

(5.2)

Observe that the polyrelation τ is constructed in the way described in Deﬁnition 3.9. Indeed,

set  =2,p = h =1,andΓ=(γ,g)whereγ = {(1), (2)} and g((1)) = {0}, g((2)) = {r}.

The corresponding σ =Γ→

ρ has

= {ϕ(1) | ϕ : {1, 2}→k,ϕ(1) ∈ ρ

,ϕ(2) ∈ ρ

x+r

}

for all x ≥ 0 which is (5.2). In view of i, i

+ r ∈ I,wehaveτ

= ρ

= ∅ and so τ ∈ V ∩ [ρ].

Clearly p

≤ p and τ

⊆ ρ

for all x ≥ 0. Applying Lemma 5.2 we obtain τ = ρ. According

Completeness of uniformly delayed op erations 127

to (5.2) we have i ∈ I ⇒ i

+ r ∈ I. In particular, from 0 ∈ I we get that I consists of all

j ∈ p such that j ≡ rx (mod p) for some integer x.Nowr is a divisor of p on account of the

minimality of r.ThusI ⊇{0,r,...,p− r} and again by the minimality of r we obtain the

required I = {0,r,...,p− r}. 2

The following lemma relates r and n := p/r. For later use it is given in a more general

form.

5.6 Lemma Let ρ be an at most binary periodic polyrelation with period p and such that p

p for no proper σ ∈ [ρ].Letr be a divisor of p such that p/r = p

...p

for l ≥ 1, p

,...,p

distinct primes and positive integers a

,...,a

. Suppose that for I := {0,r,2r,...,p−r} and

J := p \ I we have either

(1) (a) ∅ = ρ

⊂ k for all i ∈ I while ρ

= ∅ for all j ∈ J,or

(b) ρ

= ∅ is an areﬂexive binary relation for all i ∈ I while ρ

= ∅ for all j ∈ J,

(2) ι

⊂ ρ

⊂ k

for all i ∈ I while ρ

= ι

for all j ∈ J.

Then r = p

···p

for some b

,...,b

≥ 0.

Proof Put n := p/r. Suppose to the contrary that there exists a prime divisor d of r not

dividing n.Setr



:= r/d.Fori ≥ 0deﬁneapolyrelationσ

as follows. (i) If r



does not

divide i put σ

=(∅, ∅,...) in the case (1) and σ

=(ι

,ι

,...) in the case (2) (whereby σ

unary if ρ is unary and binary otherwise). (ii) Let i = r



x for some x ≥ 0. Denote by z the

unique solution in n of the congruence dz ≡ x (mod n). This solution exists as d is a prime

and d does not divide n.Nowforallj ≥ 0set

:= ρ

rz+j

. (5.3)

We prove:

Claim 1:

⊆ σ

i+j

for all i, j ≥ 0. (5.4)

Proof: Suppose to the contrary that (5.4) does not hold for some i, j ≥ 0. Then clearly

j>0, σ

is nonvoid and, moreover, in the case (2) also σ

⊃ ι

(since all the relations

are then reﬂexive). Now r



divides i since otherwise in the case (1) we get σ

= ∅ and in

the case (2) we get σ

= ι

.Thusi = r



x for some x ≥ 0anddz ≡ x (mod n)fora

unique z ∈ n and σ

= ρ

rz+j

. According to (1) and (2) here rz + j ≡  (mod p)where

 ∈ I = {0,r,...,p− r}.Asr divides p, we obtain that r divides j; i.e., j = ry for some

y ≥ 0. Note that from r = r



i + j = r



(x + dy). (5.5)

Denote by z



the element of n satisfying z



≡ z + y (mod n). Now dz



≡ dz + dy ≡ x + dy

(mod n). Next z



= z + y + mn for some integer m.Usingthisandj = ry we get



= r(z + y)+mrn = rz + j + mp ≡ rz + j (mod p). (5.6)

Now on account of (5.5), (5.4) and (5.6) we have σ

i+j

= ρ



= ρ



= ρ

rz+j

= σ

proving

the claim. 2

128 T.HikitaandI.G.Rosenberg

Claim 2: σ

∈ [ρ] for all i ≥ 0.

Proof: First consider the case where r



does not divide i.Thenσ

is either (∅, ∅,...)or

(ι

,ι

,...); hence Pold σ

= U (= the set of all uniformly delayed operations on k)and

clearly σ

∈ [ρ]. Thus let i = r



x for some x ≥ 0andletz ∈ n satisfy dz ≡ x (mod n). Then

for s := rz clearly σ

=(ρ

,ρ

s+1

,...),henceinviewofLemma5.4wehavePoldρ =Poldσ

and so σ

∈ [ρ]. 2

Claim 3: σ

i+r



= σ

for all i ≥ 0.

Proof: If r



does not divide i then r



does not divide i + r



n either and so σ

i+r



= ∅ = σ

the case (1) while σ

i+r



= ι

= σ

in the case (2). Thus let i = r



x for some x ≥ 0. Denote

by z the unique solution in n of dz ≡ x (mod n). Then dz ≡ x ≡ x + n (mod n)andsoby

(5.3)

i+r



= σ



(x+n)

= ρ

= σ



= σ

The upper superposition of σ

,σ

,... is σ := (σ

,σ

,...). In view of Claims 1 and 2,

according to [Mi84] we have σ ∈ [ρ].

Note that for i =0wehave0=r0andd0 ≡ 0(modn)andsoσ

= ρ

by (5.3).

Since by assumption ρ

is nontrivial, according to Corollary 3.8 the polyrelation σ ∈ [ρ]is

proper. Finally p

≤ r



n by Claim 3. By the deﬁnitions r



n =(r/d)(p/r)=p/d < p and so

<pin contradiction to the hypothesis. Thus every divisor of r divides n and r has the

required form. 2

Applying Lemma 5.6 to optimal unary polyrelations and reformulating the divisibility

condition we obtain:

5.7 Proposition Let ρ be an optimal unary polyrelation with nontrivial ρ

and period p =

···p





where  ≥ 1, p

,...,p



are pairwise distinct primes and d

,...,d



positive integers.

Then there exists r = p

···p





such that

(1) the integers c

satisfy 0 ≤ c

for all i =1,...,,and

(2) ρ

,ρ

,...,ρ

p−r

are pairwise disjoint and nonempty subsets of k while ρ

= ∅ for all j

not divisible by r.

5.8 Remarks

(1) An example of p and r in Proposition 5.7 are p =12andr =2. Thenρ

,ρ

,...,ρ

are pairwise distinct nonempty subsets of k and ρ

,ρ

,...,ρ

= ∅.Noticethatk ≥ 6.

(2) Suppose the number p/r of sets ρ

,ρ

,...,ρ

p−r

is a prime power q

.Thenp = q

n+m

for some n ≥ 1.

(3) Let k = 2. There are two candidate subsets of 2 for the ρ

,namely{0} and {1},and

so p/r =2andp =2

m+1

and r =2

. Thus we may suppose that ρ

= {0}, ρ

= {1}

and ρ

= ∅ for all 0 <i<2

m+1

, i =2

. For every m ≥ 0 the uniform clone Pold ρ is

one of the ℵ

precomplete uniform clones on 2 from [Ku62].

Completeness of uniformly delayed op erations 129

(4) Let k =3. Ifp/r = 2 we basically have the situation described in (3) above. Thus let

p/r =3. Thenp =3

m+1

and r =3

and we may assume that ρ

= {0}, ρ

= {a},

2·3

= {b} (where {a, b} = {1, 2})andρ

= ∅ for 0 <i<3

m+1

, i ∈{3

, 2 · 3

}.This

yields the ℵ

precomplete uniform clones on 3 from [Hi78].

6 Binary Areﬂexive Polyrelations

In this section we consider the set Ξ

of minimal binary polyrelations from Ξ

. Recall that

:= {aa | a ∈ k},andsetσ

:= k

\ι

. A binary relation τ is reﬂexive (areﬂexive)ifτ ⊇ ι

(τ ⊆ σ

). Let ρ be a binary polyrelation from Ξ

with period p.

6.1 Lemma If ρ is a minimal binary polyrelation then every ρ

is either reﬂexive or areﬂex-

ive.

Proof For every i ≥ 0setτ

:= {x | xx ∈ ρ

}. As in Lemma 4.5 the unary polyrelation

τ =(τ

,τ

,...) satisﬁes Pold ρ ⊆ Pold τ. Since by minimality τ =(τ

,τ

,...) is not proper,

we have τ

∈{∅, k} i.e. every ρ

is either areﬂexive or reﬂexive. 2

The relational (or de Morgan) product of binary relations λ and µ on k is

λ ◦ µ := {xy | xu ∈ λ, uy ∈ µ for some u}.

The converse (or inverse) of λ is

λ := {yx | xy ∈ λ}.

Denote by R and A the sets of ρ ∈ Ξ

such that each ρ

is reﬂexive and areﬂexive,

respectively. We show that the binary polyrelations may be reduced to those from R ∪ A.

6.2 Lemma Every minimal binary polyrelation on k is dominated by a binary polyrelation

from R ∪ A.

Proof Let ρ be a proper binary periodic polyrelation on k. There is nothing to prove if

ρ ∈ A.Thusletι

⊂ ρ

⊂ k

for some i ≥ 0. Taking a suitable shift of ρ, by Lemma 5.4 we

may assume that ι

⊂ ρ

⊂ k

.PutB := {b ∈ p | ρ

⊇ ι

} and C := p \ B.Putρ



:= ρ

for

b ∈ B and ρ



:= k

for c ∈ C.Noticethat0∈ B.

Claim: ρ



dominates ρ.

Proof: For b ∈ B put σ

:= ρ

b+i

for all i ≥ 0 while for c ∈ C put σ

:= k

and σ

:= ι

for

all i>0. This deﬁnes σ

=(σ

,σ

,...) for all j ≥ 0. For b ∈ B the polyrelation σ

is just a

shift of ρ and so σ

∈ [ρ]. For c ∈ C the polyrelation σ

is improper and thus σ

∈ [ρ]. We

show that σ

⊆ σ

i+j

for all i, j ≥ 0. If i + j ∈ C then σ

i+j

= k

⊇ σ

.Thusleti + j ∈ B.

Then σ

i+j

= ρ

i+j+0

= ρ

i+j

.Ifalsoj ∈ B then σ

= ρ

i+j

= σ

i+j

and we are done. Thus

let j ∈ C.Thenj>0andσ

= ι

⊆ ρ

i+j

because i + j ∈ B and so ρ

i+j

is reﬂexive. Thus

⊆ σ

i+j

for all i, j ≥ 0. The upper superposition of (σ

,σ

,...)isρ



and so ρ



∈ [ρ]. This

proves the claim. 2

Clearly ρ



= ρ

is proper and so ρ



∈ R. 2

Denote by A

and R

the set of all ρ ∈ A and ρ ∈ R with ρ

= k

for all i ∈ p.Weshow

that we can consider only polyrelations from A

∪ R

6.3 Lemma Every ρ ∈ A ∪ R is dominated by some σ ∈ A

∪ R

130 T.HikitaandI.G.Rosenberg

Proof We may assume ρ

to be nontrivial. Put p := p

and D

:= {i ∈ p | ρ

= k

}.There

is nothing to prove if D

= ∅,thusletD

= ∅ and denote by d the least element of D

.Put

:= ρ

i−d

∩ ρ

for all i ∈ p. Clearly τ

= ρ

∩ ρ

= ρ

∩ k

= ρ

and so τ is proper. Also

τ ∈ [ρ]andD

:= {i ∈ p

| τ

= k

} satisﬁes |D

| < |D

| due to τ

⊆ ρ

for all i ∈ p and

d ∈ D

\ D

.Notethatτ ∈ R ∪ A. Repeating this we ﬁnally arrive at σ with D

= ∅. 2

6.4 In the remainder of this section we study areﬂexive binary polyrelations. For ρ ∈ A

with period p put I

:= {i ∈ p | ρ

= ∅}, J

:= p \ I

and j

:= |J

For a map ϕ from a subset D of k into k put ϕ

◦

:= {xϕ(x) | x ∈ D}.LetS denote

the set of all permutations of k. Finally denote by A

the set of all ρ ∈ A

such that

∈ S

◦

= {s

◦

| s ∈ S} for all i ∈ I

.Wehave:

6.5 Lemma Every ρ ∈ A

\ A

is dominated by some σ ∈ R

Proof Let ρ ∈ A

\ A

. Suppose to the contrary that ρ is not dominated by any σ ∈ R

Put p := p

and I := I

.Furtherforalli ∈ p put λ

:= pr

= {x ∈ k | xu ∈ ρ

for some u}.

AccordingtoLemma4.7wehaveλ

= k for all i ∈ I.Putτ

:= ρ

◦ ˘ρ

= {xy | xu, yu ∈ ρ

for some u} for all i ≥ 0. Since τ

is clearly reﬂexive for all i ∈ I and τ

= ∅ otherwise, and

also τ ∈ [ρ] clearly the polyrelation τ is improper. Thus suppose τ

∈{ι

, k

} for all i ∈ I.

Let τ

= k

for some j ∈ I.Forn =3,...,k and i =0,...,p− 1form

(n)

:= {x

...x

| x

u ∈ ρ

(l =1,...,n)forsomeu}.

It is easy to see that λ

(3)

is totally reﬂexive. Thus λ

(3)

= k

by Theorem 4.2. An easy

induction shows that λ

(n)

= k

for n =3,...,k.Thus(0,...,k − 1) ∈ λ

(k)

, i.e., there is

a u such that xu ∈ ρ

for all x ∈ k. This is impossible because uu does not belong to

the areﬂexive relation ρ

.Thusρ

◦ ˘ρ

= ι

for all i ∈ I. The same argument applied to

:= ˘ρ

◦ρ

= {xy | ux, uy ∈ ρ

for some u} yields ˘ρ

◦ρ

= ι

for all i ∈ I. Now it is easy to

see that ρ

= s

◦

for some permutation s

of k.Thusρ ∈ A

contrary to our assumption. 2

Our next strategy is the following. In the ﬁrst place we try to reduce the period. Among

the polyrelations with minimal period we try to increase the number of empty relations.

6.6 Deﬁnition More formally, a polyrelation ρ ∈ A

is strict if each λ ∈ A

∩ [ρ]satisﬁes

(i) p

≥ p

and (ii) j

≤ j

whenever p

= p

(where J

= {i ∈ p

| ρ

= ∅} and j

= |J

|).

Denote by V

the set of unary polyrelations satisfying the conditions of Proposition 5.7.

Denote by A

the set of all strict polyrelations.

The following is almost immediate.

6.7 Lemma The system V

∪ R

∪ A

is B-generic.

Proof According to Proposition 5.7, Lemmas 6.2, 6.3 and 6.5 the system V

∪ R

∪ A

B-generic and so it suﬃces to show that each ρ ∈ A

is dominated by some σ ∈ A

.Put

p := p

.ThesetL

of all proper λ ∈ [ρ]withp

≤ p is ﬁnite (as it has less than 2

elements). Put

∗

:= min{p

| λ ∈ L

},L

:= {λ ∈ L

| p

= p

∗

Completeness of uniformly delayed op erations 131

Next let

∗

:= max{j

| λ ∈ L

},L

:= {λ ∈ L

| j

= j

∗

For λ

,λ

∈ L

put λ

≤ λ

if Pold λ

⊆ Pold λ

.Therelation≤ is a ﬁnite quasiorder (a

reﬂexive and transitive relation) on L

. Letting λ

∼ λ

if λ

≤ λ

we get an equivalence

relation ∼ on L

whose blocks B

,...,B

may be ordered by B

if λ



<λ



for some



∈ B

and λ



∈ B

. This ﬁnite order has a maximal element B

.Nowanyσ ∈ B

is strict,

and dominates ρ. 2

In the following lemmas we ﬁnd the shape of polyrelations from A

. Recall that (i) I

{i ∈ p

| ρ

= ∅}, (ii) The converse of a binary relation α is ˘α := {ab | ba ∈ α}, and (iii) A

permutation s ∈ S is of order m if s

(x)=x for all x ∈ k and m is the least integer with

this property.

6.8 Lemma If σ ∈ A

then a shift ρ of σ satisﬁes either

(1) I

= {0,r,2r,...,p−r} for some proper divisor r of p

and ρ

=˘ρ

,or

(2) I

= {0,i} where 0 <i<p

and ρ

=˘ρ

= ρ

Proof Put p := p

, I := I

and J := J

. We have two cases: (i) Suppose there are i ∈ I and

q ∈ p \{0} such that i

+ q ∈ I and the relational product ρ

◦ρ

i+q

= ι

(see Lemma 6.1). Fix

q to be the least possible element of p \{0} with this property. Without loss of generality

we may assume that the corresponding i equals 0 (see Lemma 5.4). Put τ

:= ρ

◦ ρ

n+q

for

all n ≥ 0. Since τ

= ρ

◦ρ

= ι

,wegetτ

= s

◦

for a nonidentity permutation s of k.Thus

is nontrivial; hence τ is proper and so τ ∈ A

∩ [ρ]. Clearly p

≤ p and, ρ being strict,

also p

= p. It is easy to see that J

⊇ J; hence j

≥ j and so j

= j by the strictness of ρ,

proving J

= J.Considerl ∈ J.Thenρ

= ∅ and consequently τ

= ρ

◦ ρ

l+q

= ∅,proving

+ l ∈ J.

For a subset A of p and b ∈ p put b

+ A := {b

+ a | a ∈ A} (where

+isthesummod

p in p). With this notation we have q

+ J ⊆ J. We need the following easy fact.

Fact: The following are equivalent for A ⊆ p, b ∈ p and c := gcd(b, p)(the greatest common

divisor of b and p):

(1) b

+ A ⊆ A,

(2) b

+ A = A,

(3) b

+(p \ A)=p \A,and

(4) c

+ A = A.

Put r :=

gcd(q, p). Applying the fact, we have r

+ J = J and r

+ I = I.Set

Q := {0 <i<q| ρ

= ∅} = I ∩{1,...,q−1}.

We need:

Claim 1: (i) ρ

=˘ρ

for all l ∈ Q, (ii) |Q|≤1.

Proof: (i) Let l ∈ Q. By the minimality of q and in view of ρ

,ρ

∈ S

◦

we have ρ

◦ ρ

= ι

Thus ρ

=˘ρ

as required.

132 T.HikitaandI.G.Rosenberg

(ii) Suppose there are m, n ∈ Q with m<n.From(i)wehaveρ

= ρ

=˘ρ

.Takinginto

account 0 <n−m<qand the minimality of q we have ˘ρ

◦˘ρ

= ρ

◦ρ

= ρ

◦ρ

m+(n−m)

= ι

and therefore the nontrivial relation ρ

equals s

◦

for some s ∈ S of order 2. Thus ρ

=˘ρ

= s

◦

Now ρ

◦ ρ

m+(q−m)

= ρ

◦ ρ

= ρ

◦ ρ

= ι

where 0 <q− m<qand this contradicts our

choice of q. 2

Claim 2: Q = ∅.

Proof: By Claim 1 (ii) we have |Q|≤1. Suppose to the contrary that |Q| =1. From0∈ I

and r

+ I = I we get {0,r,...,p−r}⊆I. It follows that Q = {r} and q =2r. By Claim 1 (i)

we have ρ

=˘ρ

. Again by the minimality of q we have ˘ρ

◦ ρ

= ρ

◦ ρ

r+(q−r)

= ι

proving

= ρ

. The same argument yields ρ

2lr

= ρ

, ρ

(2l+1)r

=˘ρ

for all l ≥ 0. From ρ

= ρ

get p even and so q =2r divides p.Moreoverρ has period q proving q = p. However, this

contradicts the deﬁnition of q.ThusQ = ∅. 2

Now Q = ∅ means that q = r divides p and we have the case (i).

(ii) Thus suppose that for all i, j ∈ I, i = j we have ρ

◦ ρ

= ι

.Inparticular,ρ

=˘ρ

for all l ∈ I \{0}.If|I| =2and ˘ρ

= ρ

we have case (ii). We show that in all the other

cases we have ρ

= ρ

for all i ∈ I.Choosei, j ∈ I,0<i<j.Then˘ρ

◦ ˘ρ

= ρ

◦ ρ

= ι

and therefore ρ

=˘ρ

= ρ

for all i ∈ I. Now put σ

:= ρ for all n ≥ 0. Clearly σ

∈{∅,ρ

}

and consequently σ

⊆ ρ

= σ

m+n

. The upper superposition of σ

,σ

,... is (ρ

,ρ

,...).

However, ρ ∈ A

is not dominated by a proper polyrelation of this type. This contradiction

settles the remaining cases. 2

For a divisor q of k denote by S

the set of all s ∈ S with k/q cycles of length q (note

that each s ∈ S

is a ﬁxedpoint-free permutation of order q). We have:

6.9 Lemma Let ρ ∈ A

.Then

(1) For every i ∈ I

we have ρ

∈ S

◦

for some divisor m

of k,and

(2) ρ

= ρ

⇒ ρ

∩ ρ

= ∅ for all 0 ≤ l<m<p

Proof Write p and I instead of p

and I

.(1)Consideri ∈ I.Thenρ

= s

◦

for some s

∈ S.

Denote by m

the minimum length of cycles of s

. Recall that for a binary relation σ the

power σ

is deﬁned recursively by setting σ

= ι

and σ

n+1

:= σ

◦ σ for n =0, 1,....Put

:= {x | xx ∈ ρ

} for all n ≥ 0. By minimality (see 4.4) the unary polyrelation ν ∈ [ρ]is

trivial. From ν

= ∅ we obtain ν

= k, i.e. ρ

= s

◦

for some s

∈ S

(2) By way of contraposition suppose ρ

∩ρ

= ∅ for some 0 ≤ l<m<p.Puts := m−l

and µ

:= pr

(ρ

∩ρ

n+s

) for all n ∈ p. Clearly µ

= ∅. Again by minimality we have µ

= k.

Since ρ

, ρ

∈ S

◦

,wehavetherequiredρ

= ρ

. 2

6.10 Lemma If ρ ∈ A

then ρ

= ι

for no i ∈ p.

Proof We may suppose that ρ is of the form given in Lemma 6.8. If it satisﬁes (2) then

= ι

(due to ˘ρ

= ρ

)andρ

= ι

(due to ρ

=˘ρ

). Thus let (1) hold. Put I := I

and

p := p

. Suppose to the contrary that L := {l ∈ I | ρ

= ι

} is nonempty. Now ρ being

proper, we have L ⊂ I and so we may assume 0 ∈ L.Denotebyl and g the least and greatest

element of L.Putσ

:= (ρ

n+r

◦ ρ

) ∩ ρ

for all n ≥ 0. First σ

l−r

=(ρ

◦ ρ

l−r

) ∩ ρ

l−r

(ι

◦ ρ

l−r

) ∩ ρ

l−r

= ρ

l−r

∩ ρ

l−r

= ρ

l−r

.Herel − r ∈ L, hence ρ

l−r

∈ S

◦

\{ι

} and therefore