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

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

Completeness of uniformly delayed op erations 113

reality.

As pointed out in 2.1 the input delayed gate is already a considerable simpliﬁcation.

The delays in circuits should be taken into consideration since to ignore them is tantamount

to neglecting such well known phenomena as races or hazards, and therefore input delayed

devices constitute the ﬁrst step in the right direction. The restriction to uniformly delayed

devices is all pervasive through the literature but it is not altogether clear whether it is

motivated by mere convenience or rather a hard fact about today’s commercially available

gates. In practice, often several functions have to be represented simultaneously which could

be used as an argument for uniform delays. The completeness concept is open to the obvious

criticism: what is the purpose of constructing an F with an enormous delay? We chose our

concept because it is the simplest and weakest completeness concept, and since it makes a

nice mathematical theory.

2.4 We conclude with two minor points. Suppose we have constructed (f, δ) and it happens

that f is constant and hence time-independent. Of course, there is no observable delay and

we can assume that we have all (f,δ



)withδ



∈ N. This is rather academic because usually

sources of constant signal are easy to get and so cheap that they can be taken for granted.

However this fact is not accounted for in our model.

Finally, we stress that we are interested in sets of gates with the potential to represent

any f ∈O(with some delay and assuming an unlimited supply of each type of gate) but we

ignore completely the inherent optimality issue: if f can be represented, what is the cheapest

way of representing it? There is a good reason for this limitation; it is because the problem is

notoriously hard, depends on present technology and labor costs and thus, to be meaningful,

should be closely tailored to a very speciﬁc situation which could become obsolete within a

very short time.

2.5 We conclude this section with a completeness criterion. First call P ⊆Oprimal if every

f ∈Ois a composition of operations from P ∪J (we reserve this term for operations without

delays). Put e := e

(i.e. e(x) ≈ x)andforV ⊆U, n>0, and δ ≥ 0, set

(n)

:= V ∩U

(n)

:= {f | (f,δ) ∈ V },

(δ)

∞



m=0

{f ∈O|(f,mδ) ∈ V for some m ≥ 0}.

We have ([Ku62, Theorem 4] for k = 2 and [PK79, 7.3.5]; see also [MRR78, Theorem 10] for

k>2):

2.6 Proposition A closed subset V of U is complete if and only if e ∈ V

and V

(δ)

is primal

for some δ ≥ 0.

2.7 Corollary Let V be a closed uniform set. If V is incomplete, then F := (J ×{0}) ∪ V

is a uniform incomplete clone.

Proof Clearly F is a uniform clone. Suppose to the contrary that F is complete. Then in

Proposition 2.6 we have δ = 0 because otherwise V would be complete. Thus F

is primal.

Then V

is primal [Ro70, 3.1.3] and since V is a closed uniform set, V

= O also. This

contradiction proves the statement. 2

114 T.HikitaandI.G.Rosenberg

Needless to say, Proposition 2.6 hardly solves the completeness problem and thus we

search for a better criterion. This will be based on sequences of relations introduced and

elaborated in the next section.

2.8 A short notational remark. The symbol ⊂ stands for strict inclusion, while ⊆ means

inclusion or equality. Whenever possible an n-tuple is written x

...x

instead of the more

conventional (x

,...,x

). The same applies to arguments of maps, functions and operations,

e.g. we write fx or fx

...x

instead of f(x)orf (x

,...,x

). Sometimes we do not distin-

guish notationally an element a and the singleton {a} writing e.g. A \a and a ×A for A \{a}

and {a}×A.

3 Polyrelations

3.1 Asubsetρ of k

(i.e. a set of h-tuples over k)isanh-ary relation on k.Letρ and σ

be h-ary relations on k and f ∈O

(n)

.Wesaythatf carries ρ in σ if for every h ×n matrix

A =[a

]overk, whose column vectors all belong to ρ,thevaluesoff on the rows of A form

an h-tuple from σ;insymbols

,...,a

) ∈ ρ (j =1,...,n)=⇒ (f(a

,...,a

),...,f(a

,...,a

)) ∈ σ.

Denote by Pol(ρ, σ)thesetofallf ∈Ocarrying ρ into σ.WesetPolρ =Pol(ρ, ρ)and

say that f preserves ρ if f ∈ Pol ρ (many other names are used in the literature; e.g., f

is compatible, substitutive, homeomorphic and ρ is invariant or stable for f ). In universal

algebra terms “f preserves ρ”meansthatρ is a subuniverse of k; f

. We recall some basic

results on clones. An h-ary relation ρ on k has no systematically repeated coordinate if for all

1 ≤ i<j≤ h there exists (a

,...,a

) ∈ ρ with a

= a

.AcloneC on k is rational if it is of

the form Pol ρ for some relation ρ on k. Here without loss of generality we can assume that

ρ has no systematically repeated coordinate.

We recall a relational construction. Let h ≥ 1and ≥ p ≥ 1 be integers and let Γ and ρ

be h-ary relations on L = {1,...,} and k, respectively. Set

Γ →

ρ = {(ϕ(1),...,ϕ(p)) | ϕ ∈ Hom(Γ,ρ)}

where Hom(Γ,ρ) denotes the set of relational homomorphisms from Γ into ρ, i.e. maps ϕ :

L → k such that ϕ(a)=(ϕ(a

),...,ϕ(a

)) ∈ ρ whenever a =(a

,...,a

) ∈ Γ. An easy

consequence of the results of [BKKR69] is: Let ρ and σ be h-ary and p-ary relations on k and

let σ be without systematically repeated coordinates. Then Pol ρ ⊆ Pol σ if and only if there

exists  ≥ p and h-ary relation Γ on {1,...,} such that σ =Γ→

ρ.Anotherresultfrom

[BKKR69] is also basic. To every irrational clone (i.e., nonrational) C there exist relations

,ρ

,... on k such that Pol ρ

⊇ Pol ρ

⊇···⊇C =



∞

i=1

Pol ρ

. We extend this to uniform

clones.

3.2 A countably inﬁnite sequence ρ := (ρ

,ρ

,...)ofh-ary relations on k is an h-ary

polyrelation on k.Thesetofh-ary polyrelations on k is denoted by R

and R :=



∞

h=1

We say that (f,δ) ∈Upreserves an h-ary polyrelation ρ =(ρ

,ρ

,...)if

f ∈ Pol

ρ :=



i∈N

Pol(ρ

,ρ

i+δ

Completeness of uniformly delayed op erations 115

We set

Pold ρ :=

∞



δ=0

(Pol

ρ × δ).

3.3 Example Let ≤ be an order (a reﬂexive, transitive and antisymmetric binary relation)

on k.ThenM := Pol ≤ is the set of ≤-monotone (also called isotone or order preserving)op-

erations on k (i.e. f ∈O

(n)

such that fx

···x

≤ fy

···y

whenever x

≤ y

,...,x

≤ y

Similarly f ∈O

(n)

is ≤-antimonotone if fx

···x

≥ fy

···y

whenever x

≤ y

,...,x

≤

.LetA be the set of ≤-antimonotone operations and let ρ =(≤, ≥, ≤, ≥,...). Then

Pol

ρ = M and Pol

2n+1

ρ = A for all n ≥ 0.

We have [Ku62]:

3.4 Lemma Let ρ =(ρ

,ρ

,...) be a polyrelation. Then Pol

ρ =



i≥0

Pol ρ

and Pold ρ is

a uniform clone.

Proof By deﬁnition,

Pol

ρ =



i∈N

Pol ρ

and therefore J ×0 ⊆ Pold ρ. It remains to prove that Pold ρ is a closed set. Let f ∈ Pol

ρ be

n-ary, let g

∈ Pol



ρ (j =1,...,n)andleth := f ⊗(g

,...,g

) (as deﬁned in 2.2). For i ∈ N

we have g

[ρ

] ⊆ ρ

i+δ



(j =1,...,n). Using f[ρ

i+δ



] ⊆ ρ

i+δ+δ



we obtain h[ρ

] ⊆ ρ

i+δ+δ



. 2

3.5 We recall a basic result from [Mi84]. The relation “(f,δ) preserves a polyrelation”

gives rise to a Galois connection between the sets U (of uniformly delayed operations on

k)andR (of polyrelations on k). The Galois closed subsets of U are the sets of the form

Pold X =



ρ∈X

Pold ρ with X ⊆R. It is shown in [Mi84] that they are exactly the uniformly

closed clones; more precisely each uniform clone is either of the form Pold ρ from some ρ ∈R

or the intersection of a countable descending chain Pold ρ

⊃ Pold ρ

⊃ ··· with ρ

∈R

for all i ≥ 0. It is therefore of interest to characterize the Galois-closed subsets of R.By

deﬁnition they are the sets

Inv Y := {ρ ∈R|every (f,δ) ∈ Y preserves ρ}

with Y ⊆U. To describe them internally we need the following notions. Let σ be an h-ary

relation on k.Ifh>1set

ζ(σ):={(a

,...,a

) | (a

,...,a

) ∈ σ},

τ(σ):={(a

,...,a

) | (a

,...,a

) ∈ σ},

pr(σ):={(a

,...,a

h−1

) | (a

,...,a

) ∈ σ},

while for h =1setζ(σ)=τ(σ)=pr(σ)=σ.Furtherset

∇(σ)={(a

,...,a

h+1

) | (a

,...,a

) ∈ σ}.

Extend ζ, τ,pr,∇ to polyrelations by applying them termwise. For ρ =(ρ

,ρ

,...)andα ∈

{ζ,τ,pr, ∇} set α(ρ)=(α(ρ

),α(ρ

),...). Further set sh(ρ)=(ρ

,ρ

,...). For polyrelations

116 T.HikitaandI.G.Rosenberg

ρ =(ρ

,ρ

,...)andσ =(σ

,σ

,...)setρ ∩ σ =(ρ

∩ σ

,ρ

∩ σ

,...) (notice that ρ ∩ σ =

(∅, ∅,...)ifρ and σ have diﬀerent arities).

We also need a partial inﬁnitary operation on R called upper superposition. For ρ

(ρ

,ρ

,...) ∈R

(i =0, 1,...) the upper superposition of (ρ

,ρ

,...) is deﬁned wherever,

for all i ≥ 0,

⊇ ρ

i−1

∪ρ

i−2

∪···∪ρ

If this condition is met the upper superposition is the polyrelation (ρ

,ρ

,...). In other

words, consider in the inﬁnite table

···

whose rows are the given polyrelations. We take the polyrelation in the ﬁrst column provided

each of its entries contains all relations on the south-west to north-east diagonal starting at

it.

It is shown in [Mi84] (in a slightly diﬀerent formulation) that a subset X of R is Galois

closed if and only if X is closed under ζ, τ,pr,∇,sh,∩, upper superposition and contains

the constant polyrelation ω =(ι

,ι

,...)(whereι

= {(x, x) | x ∈ k}).

3.6 For a positive integer h denote by E

the set of equivalence relations on {1,...,h}.For

ε ∈ E

put

∆

= {a

···a

∈ k

| (i, j) ∈ ε ⇒ a

= a

};

i.e. ∆

consists of all h-tuples over k constant on each block of ε.

If ε has a unique nonsingleton block {i

,...,i

} we denote ∆

by ∆

···i

; e.g., ∆

stands

for ∆

where ε = {12, 21}∪ι

. Similarly ∆

···i

−j

···j

denotes ∆

with ε having exactly two

nonsingleton blocks {i

,...,i

} and {j

,...,j

}.Therelations∆

are termed diagonal.The

diagonal relations and the empty relation ∅ are called trivial. A nonempty subset E of E

is a clutter (also antichain or Sperner subset)ifθ ⊂ τ for no θ,τ ∈ E. For a clutter E put

∆



ε∈E

∆

It is well known [Ro70, 2.8.7] that Pol σ = O if and only if σ is trivial. We say that a

polyrelation ρ is proper if Pold ρ is incomplete. We characterize improper polyrelations.

3.7 Proposition A polyrelation ρ =(ρ

,ρ

,...) is improper if and only if

(1) all ρ

are trivial, or

(2) there are δ>0, m>0 and trivial relations α

,...,α

δ−1

such that

⊆ ρ

i+δ

⊆···⊆ρ

i+mδ

= ρ

i+(m+1)δ

= ···= α

for all i =0,...,δ− 1.

Completeness of uniformly delayed op erations 117

Proof Necessity. For δ ≥ 0 put F

:= Pol

ρ. First consider the case F

= O. By Lemma 3.4

then Pol ρ

= O for all i ∈ N, i.e., all ρ

are trivial proving (1). Thus assume F

⊂O.By

Proposition 2.6 there is δ>0 such that e ∈ F

and G :=



n≥0

nδ

is primal (i.e., G generates

O). From e ∈ F

it follows that ρ

⊆ ρ

i+δ

for all i ∈ N. Since there are only 2

h-ary relations

on k, for each ﬁxed 0 ≤ i<δthe non-decreasing chain ρ

⊆ ρ

i+δ

⊆ ρ

i+2δ

⊆··· is stationary,

i.e. there is j

∈ N such that ρ

i+lδ

= ρ

i+j

for all l ≥ j

.Putm := max{j

,...,j

δ−1

and set α

:= ρ

mδ+i

(i =0,...,δ − 1). For a ﬁxed 0 ≤ i<δ,allf ∈ F

nδ

we have

f[α

]=f[ρ

mδ+i

] ⊆ ρ

(m+1)δ+i

= ρ

mδ+i

= α

proving f ∈ Pol α

, F

nδ

⊆ Pol α

and ﬁnally

G ⊆ Pol α

.OwingtoG primal we have α

trivial and (2) holds.

Suﬃciency. If (1) holds then by Lemma 3.4 we have Pol

ρ = O and Pold ρ is complete

by Proposition 2.6. Thus suppose that (2) holds. Then e ∈ Pol

ρ. In view of Proposition 2.6

it suﬃces to show that Pol

mδ

ρ = O for all m ≥ 0. Let 0 ≤ i<δ.Ifα

= ∅,thenρ

lδ+i

= ∅

for all l ∈ N and

f[ρ

lδ+i

]=f[∅]=∅ = ρ

(+m)δ+i

for every f ∈O. Thus assume that α

=∆

for some equivalence relation ε on {1,...,h}.

Then for every f ∈Oand l ∈ N we have the required

f[ρ

lδ+i

] ⊆ f[α

] ⊆ α

= ρ

(l+m)δ+i

We say that ρ =(ρ

,ρ

,...)isperiodic if there is δ>0 such that ρ

i+δ

= ρ

for all i ≥ 0.

For a p erio dic ρ the least δ>0 with this property is the period of ρ and it will be denoted

by p

3.8 Corollary Let ρ be a periodic polyrelation with period p.Thenρ is proper if and only

if at least one ρ

is nontrivial.

3.9 Deﬁnition It will be convenient to say that a polyrelation τ on k dominates apolyre-

lation ρ on k if Pold ρ ⊆ Pold τ. For a given polyrelation ρ on k denote by [ρ]thesetofall

polyrelations on k dominating ρ.Noticethat[ρ] is the least Galois-closed subset of R (i.e.,

the least set containing ρ and ω and closed under ζ, τ,pr,∇,sh,∩ and upper superpositions,

see 3.5).

We describe a construction of τ ∈ [ρ]. Let h>0and ≥ p>0 be integers and let

Γ=(γ,g)whereγ is an h-ary relation on L = {1,...,} and g is a map from γ into the ﬁnite

nonvoid subsets of N.Letρ =(ρ

,ρ

,...)beanh-ary polyrelation on k.Foreachi ∈ N set

= {(ϕ(1),...,ϕ(p)) | ϕ : L → k,ϕ(a) ∈ ρ

i+j

for all a ∈ γ and j ∈ g(a)},

where for a =(a

,...,a

) ∈ γ we write ϕ(a)=(ϕ(a

),...,ϕ(a

)). This deﬁnes an h-ary

polyrelation τ =(τ

,τ

,...)onk denoted by Γ →

ρ.

We illustrate this construction on a few examples.

118 T.HikitaandI.G.Rosenberg

(1) Let  = p = h, γ = {(σ(1),...,σ(h))} where σ is a permutation of {1,...,h} and

g((σ(1),...,σ(h))) = {0}.Thenτ =Γ→

ρ satisﬁes for all i ∈ N

= {a

...a

| a

σ(1)

...a

σ(h)

∈ ρ

Obviously, τ

is obtained from ρ

by a coordinate exchange independent on i; i.e., the

same coordinate switch is performed on each ρ

(2) Let h = p =2, =3,γ = {(1, 3), (3, 2)} and g((1, 3)) = {0}, g((3, 2)) = {1}.Fora

binary polyrelation ρ we get τ =Γ→

ρ =(ρ

◦ ρ

,ρ

◦ ρ

,...)where◦ denotes the

standard relational product or composition (i.e. α ◦ β := {(x, y) | (x, u) ∈ α, (u, y) ∈ β

for some u ∈ k}).

(3) Let  = p = h, γ = {(1,...,h)} and g((1,...,h)) = {1}.Thenτ =Γ→

ρ =

(ρ

,ρ

,...). Obviously τ is obtained from ρ by a one-step shift to the right.

(4) Let  = p = h, γ = {(1,...,h)} and g((1,...,h)) = {0, 1}.Thenτ =(ρ

∩ ρ

,ρ

∩

,...).

The Deﬁnition 3.9 is justiﬁed by the following lemma which is essentially in [Mi84] and

can be proved directly.

3.11 Lemma If ρ and τ are as in Deﬁnition 3.9,thenτ ∈ [ρ]; i.e., Pold ρ ⊆ Pold τ.

3.12 A uniform incomplete clone C on k is precomplete if every uniform clone on k properly

containing C is complete; in other words, if C is a maximal element of the set of uniform

incomplete clones on k ordered by containment. A clone M of ordinary (i.e. non-delayed)

operations on k is maximal if M ⊂Oand M ⊂ M



⊂Ofor no clone M



The maximal clones on k are completely known: [Po21] for k = 2, [Ia58] for k =3and

[Ro65, Ro70] for k>3. They are of the form Pol σ where the relation σ on k runs through

6 families. For further use we quote a few of them: (i) proper unary relations (i.e. subsets of k

distinct from ∅ and k); (ii) binary relations {xs(x) | x ∈ k} where s is a ﬁxed permutation of

k with k/p cycles of prime length p; (iii) bounded partial orders on k (i.e., transitive, reﬂexive

and antisymmetric binary relations on k with a least and a greatest element); (iv) proper

equivalence relations on k (i.e., distinct from {(x, x) | x ∈ k} and k

), and (v) binary central

relations on k (i.e., reﬂexive and symmetric relations distinct from k

andsuchthatc×k ⊆ σ

for some c ∈ k).

A set Ξ of proper polyrelations is termed generic if each incomplete uniform clone C

extends to Pold ξ for some ξ ∈ Ξ. Our task is to ﬁnd a small generic set. The optimal generic

set Ξ would have Pold ξ precomplete for each ξ ∈ Ξ. Such a system would provide the best

general completeness criterion in the sense that for a given F we have only to test whether

F ⊆ Pold ξ for all ξ ∈ Ξ. The essential step is Hikita and Nozaki’s generic system Ξ

[HN77].

For a relation σ put σ

∗

=(σ,σ,...). We say that σ

∗

is of type A if Pol σ is maximal. Proper

periodic polyrelations ξ of arity at most k such that Pold ξ is contained in no Pold σ

∗

type A are said to be of type B. For the last type C we need the following special binary

relations. An equivalence relation on a proper subset P of k distinct from {pp | p ∈ P } is

called a proper partial equivalence on k.Letι

:= {aa | a ∈ k}.

3.10 Examples

Completeness of uniformly delayed op erations 119

3.13 Deﬁnition A binary polyrelation (ρ

,ι

,...)isoftype C if

(1) ρ

= c × k for some c ∈ k,or

(2) ρ

is a proper partial equivalence relation on k,or

(3) ρ

= {ps(p) | p ∈ P } where ∅ = P ⊆ k and either

(a) s is a permutation of P of prime order or

(b) s is an injective map from P into k such that

(i) s(P) = P and

(ii) s(p) ∈ P ⇐⇒ s(p)=p.

Denote by Ξ

the set of all polyrelations of type A, B and C. The following is a major step,

and probably the most important one towards the general uniform completeness criterion.

3.14 Theorem [HN77, Hi81b] The set Ξ

is generic. The uniform clones Pold ξ of type A

and C are precomplete.

The general uniform completeness criterion based on the full list of ℵ

uniform precomplete

clones, was found for k = 2 in [Ku62] and for k = 3 in [Hi78].

3.15 Deﬁnition A set Ξ of polyrelations on k of type B (i.e., periodic and of arity at most k)

is called B-generic if every precomplete clone Pold σ with σ a polyrelation of type B satisﬁes

Pold σ =Poldτ for some τ ∈ Ξ.

4 Minimal Polyrelations

4.1 In view of Theorem 3.14 it suﬃces to study the B-generic sets B of polyrelations.

Denote by Ξ

the set of all polyrelations of type B, i.e., ρ proper, periodic, of arity at most

k andsuchthatPoldρ ⊆ Pold σ

∗

for no σ

∗

of type A. Clearly Ξ

is B-generic. For a given

ρ =(ρ

,ρ

,...) ∈ B denote by h

and p

(or brieﬂy h and p)itsarityandperiod.

For h>2set

:= {(x

,...,x

) ∈ k

| x

= x

for some 1 ≤ i<j≤ h}

(i.e. ι

consists of all h-tuples over k whose coordinates are not all pairwise distinct). An

h-ary relation σ on k is totally reﬂexive if ι

⊆ σ.For2<h≤ k an h-ary polyrelation

λ =(λ

,λ

,...)istotally reﬂexive if at least one λ

is totally reﬂexive but distinct from k

The following theorem is basic for our study.

4.2 Theorem If ρ ∈ Ξ

then [ρ] contains no totally reﬂexive periodic polyrelation.

Proof Suppose τ =(τ

,τ

,...) ∈ [ρ] is a totally reﬂexive h-ary polyrelation of period

p.ThesetT := {i ∈ p | τ

⊇ ι

} is then nonempty. For δ ≥ 0 put λ



t∈T

t+δ

First observe that ι

⊆ λ

⊆ τ

for all t ∈ T . Taking into account that for at least one

t ∈ T we have τ

⊂ k

we obtain ι

⊆ λ

⊂ k

,henceλ =(λ

,λ

,...)isproperby

Corollary 3.8. Next λ =(λ

,λ

,...) ∈ [τ] by Lemma 3.11. Indeed choose  = p = h,

120 T.HikitaandI.G.Rosenberg

γ = {(1,...,h)} and g((1,...,h)) = T .ThenforΓ=(γ,g) the corresponding polyrelation

σ =Γ→

τ =(σ

,σ

,...)satisﬁesσ



t∈T

t+δ

= λ

for all δ ≥ 0 (see Examples 3.10(4)).

For integers x and y denote by x

+ y the integer z such that z ≡ x + y (mod p)and

0 ≤ z<p. Further denote by s the least positive integer such that t

+ s ∈ T for all

t ∈ T . Clearly 0 <s≤ p and it is almost immediate that s divides p.Nextλ

δ+s

= λ

for all δ ≥ 0. This shows that the period p

of λ divides s. We show that ι

 λ

for

i =1,...,s − 1. Indeed, by the minimality of s there exists t



∈ T such that t



+ i ∈ T

whereby λ



t∈T

i+t

⊆ τ

i+t



= τ

+ t



and ι

⊆ λ

would imply ι

⊆ τ

+ t



and i

+ t



∈ T .

This contradiction shows ι

 λ

for all i =1,...,s− 1. From this it follows that actually

= s.Inviewofλ being proper and ρ being B-generic we get s>1. Set F := Pold λ.

Denote by V the set of all operations on k taking less than k values. Further for all

i =0,...,s− 1set

:= Pol

λ =

s−1



j=0

Pol(λ

,λ

j+i

)

(see 3.1). We prove that F

⊆ V for i =1,...,s− 1. Suppose to the contrary that imf = k

for some n-ary f ∈ F

. Then there exist x

,...,x

k−1

in k

such that f(x

)=j for all j ∈ k.

As ι

 λ

there exists (j

,...,j

) ∈ ι

\ λ

.DenotebyX the h × n matrix with rows

,...,x

. Clearly all columns of X belong to ι

and hence to λ

.Asf ∈ F

⊆ Pol(λ

,λ

)

clearly (y

,...,y

) ∈ λ

. This contradiction proves f ∈ V and F

⊆ V .

It is known [Ro70] that for the nontrivial totally reﬂexive relation λ

there exists an at

least h-ary totally reﬂexive relation ζ such that Pol λ

⊆ Pol ζ where Pol ζ is maximal in

O.WehaveF

⊆ Pol λ

⊆ Pol ζ and, in view of total reﬂexivity, also F

⊆ V ⊆ Pol ζ for

i =1,...,s− 1. Thus F ⊆ Pold ζ

∗

in contradiction to ρ ∈ Ξ

. 2

A nontrivial relation is primitive if it is the union of diagonal relations, and a polyrelation

λ is primitive if all λ

are trivial or primitive and at least one λ

is primitive.

4.3 Lemma If ρ ∈ Ξ

then [ρ] contains no primitive periodic polyrelation.

Proof Suppose to the contrary that τ ∈ [ρ] is a primitive periodic polyrelation and set

F := Pold τ. It is known [Ro70] that O

(1)

⊆ Pol σ if and only if σ is trivial or primitive. Thus



i≥0

Pol τ

⊇O

(1)

.WeprovethatF

⊆ Pol ι

(recall ι

:= {(a

,...,a

) ∈ k

| a

= a

for some 1 ≤ i<j≤ k}) for all δ ∈ N. Suppose to the contrary that there exist δ ≥ 0and

f ∈ F

\ Pol ι

.Letf be n-ary. By Slupecki’s criterion [Sl39], see [PK79, 5.3], the operation

f depends essentially on at least two variables and takes all values from k.Thusthereexist

,...,a

k−1

∈ k

such that fa

= i for all i ∈ k and hence f (h

(x),...,h

(x)) ≈ x for

some h

,...,h

∈O

(1)

.AsO

(1)

⊆ F

and f ∈ F

, clearly (e, δ) ∈ F and e ∈ F

(where

e = e

=id

). Let g ∈Obe arbitrary. Again by Slupecki’s criterion the operation g is a

composition of operations from {f}∪O

(1)

.UsingthefactthatO

(1)

⊆ F

and e, f ∈ F

can convert this composition into a uniform one (see 2.2). It follows that g ∈ F

mδ

for some

m ≥ 0. By Proposition 2.6 the closed set F is complete. As τ is primitive, at least one τ

nontrivial and so by Corollary 3.8 the polyrelation τ is proper. This contradicts F =Poldτ

incomplete and so F

⊆ Pold ι

for all δ ≥ 0; consequently, F ⊆ Pold ι

∗

where ι

∗

is of type A,

in contradiction to ρ ∈ Ξ

. 2

Completeness of uniformly delayed op erations 121

4.4 Our goal is to ﬁnd the smallest possible B-generic system. The basic strategy is the

following: given a B-generic Ξ we ﬁnd Ξ



⊂ Ξ such that each ρ ∈ Ξ is dominated by some



∈ Ξ



. This reduction will be done in several steps. In the ﬁrst step we basically reduce

the arities. For ease of presentation a proper periodic h-ary polyrelation (with h ≤ k) ρ is

minimal if either h =1orρ is dominated by no proper periodic polyrelation of arity less than

h.DenotebyΞ

the set consisting of minimal polyrelations. It is almost immediate that Ξ

is B-generic. First we show that Ξ

consists of unary and binary relations. In the remainder

of the section the polyrelation ρ =(ρ

,ρ

,...) denotes a ﬁxed minimal polyrelation of arity

h and period p.Put

:= {x

...x

∈ k

| x

= x

for all 1 ≤ i<j≤ h}

and recall that ι

:= k

\ σ

.Putω

:= {x...x ∈ k

| x ∈ k}. We use throughout the

notation ρ

:= µ

∪ν

where µ

:= ρ

∩σ

and ν

:= ρ

∩ ι

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

We start out with the following technical lemmas. For an h-ary relation τ and 1 ≤ i

···<i

≤ h put

...i

τ := {x

...x

| x

...x

∈ τ }, Pr

...i

τ := pr

...j

h−l

where 1 ≤ j

< ··· <j

h−l

≤ h and {i

,...,i

,...,j

h−l

} = {1,...,h}.DenotebyE

the set of equivalence relations on {1,...,h} and put ξ

:= {11, 22,...,hh}. Finally for

1 ≤ i<j≤ h denote by ∆

the diagonal relation {a

...a

∈ k

| a

= a

}.Wehave:

4.5 Lemma If h>2, m ≥ 0 and ρ

is nonvoid, then ρ

∩ ∆

is diagonal for all 1 ≤ i<

j ≤ h.

Proof For notational simplicity let i =1andj = h.Setτ

:= Pr

(ρ

∩ ∆

) for all

n ≥ 0. The (h −1)-ary polyrelation τ thus deﬁned dominates ρ since in Lemma 3.11 we can

choose  = h, p = h − 1, γ = {(1, 2,...,h− 1, 1)} and g((1, 2,...,h− 1, 1)) = {0}.Bythe

minimality of ρ the polyrelation τ is improper and hence every τ

is trivial by Corollary 3.8.

Suppose to the contrary that τ

= ∅.Setξ

:= pr

for all n ≥ 0. Clearly ξ

= ∅ due to

the assumption ρ

= ∅. We claim that the binary relation ξ

is areﬂexive (i.e. if xy ∈ ξ

then x = y). Indeed, were aa ∈ ξ

for some a ∈ k then (a

,...,a

h−1

,a) ∈ ρ

for some

,...,a

h−1

∈ k and (a, a

,...,a

h−1

) ∈ τ

= ∅. Thus the binary polyrelation ξ dominates ρ

and is proper because ξ

is nontrivial; however, this contradicts the minimality of ρ.Thus

is diagonal, and τ

=∆

for some equivalence relation θ on {1,...,h − 1}.Itiseasy

to see that ρ

∩ ∆

=∆



where θ



is the equivalence relation on {1,...,h} obtained by

adjoining h to the block of θ



containing 1. 2

An h-ary relation τ is reﬂexive if τ ∩ ι

is primitive or diagonal.

4.6 Lemma If h>2 then every ρ

is empty or reﬂexive.

Proof Let ρ

= ∅.Then

= ρ

∩ ι



1≤j<l≤h

(ρ

∩ ∆

)

where by Lemma 4.5 all ρ

∩ ∆

are diagonal. 2

122 T.HikitaandI.G.Rosenberg

4.7 Lemma If µ

= ρ

∩ σ

= ∅ then Pr

= k

h−1

for all l =1,...,h.

Proof The relation Pr

is a trivial relation which contains a repetition-free (h − 1)-tuple

proving Pr

= k

h−1

. 2

4.8 Lemma No minimal polyrelation has arity greater than 4.

Proof Suppose to the contrary that ρ is a minimal polyrelation of arity h>4. By Lemma 4.3

the polyrelation ρ is nonprimitive, i.e. at least one ρ

is nontrivial and nonprimitive. From

Lemma 4.6 we have ν

=∆

where E is a clutter in E

(see 3.6). In view of Lemma 4.5

the relation ρ

∩∆

= ν

∩∆

is diagonal; i.e., ν

∩∆

=∆

for some equivalence relation

θ ∈ E

. Suppose to the contrary that ∆

=∆

; i.e. θ is not the equivalence relation on

{1,...,h} whose unique nonsingleton block is {1, 2}. Then there are 1 ≤ m<n≤ h such

that (m, n) ∈ θ and {m, n} = {1, 2}.Inviewofh>4wecanchooset so that 2 <t≤ h and

m = t = n. By Lemma 4.7 we have Pr

= k

h−1

; therefore

⊇ ∆



:= {x

...x

h−1

∈ k

h−1

| x

= x

and due to t>2also∆



⊆ Pr

(ρ

∩ ∆

)=Pr

∆

. However, this is impossible because

each a

...a

h−1

∈ Pr

∆

has equal coordinates at places corresponding to m and n (e.g. if

t>nwe have a

= a

). Thus ∆

=∆

and ∆

⊆ ρ

. By symmetry ∆

⊆ ρ

for all

1 ≤ l<j≤ h proving ι

⊆ ρ

and ρ

totally reﬂexive. But this contradicts Theorem 4.2. 2

Next we consider the quaternary (i.e. 4-ary) minimal relations. For {a, b, c, d} = {1,...,4}

denote by ab-cd the equivalence relation on {1,...,4} with two blocks {a, b} and {c, d} and

set χ := ∆

12−34

∪∆

13−24

∪∆

14−23

4.9 Lemma If h =4then each nonprimitive and nontrivial ρ

contains χ.

Proof By Lemma 4.5 the relation ρ

∩ ∆

is diagonal i.e. equals ∆

for some θ ∈ E

such

that (1, 2) ∈ θ. Applying Lemma 4.7 we get Pr

=Pr

= k

and therefore neither 3 nor

4 can be in the block of θ containing 1 and 2. Thus ∆

⊇ ∆

12−34

. By symmetry the same

result holds for every pair 1 ≤ i<j≤ 4provingρ

⊇ χ. 2

To settle the case of quaternary polyrelations we need the following technical lemmas.

Denote by C the set of constant operations on k and by ω

the h-ary relation {a...a| a ∈ k}.

4.10 Lemma Let ρ =(ρ

,ρ

,...) ∈ Ξ

have arity h>2,periodp and satisfy (i) [ρ] contains

no proper binary polyrelation and (ii) ρ

= ∅ or ρ

⊇ ω

for all j ∈ p. Then there is 0 <i<p

such that ∆

⊆ ρ

whenever θ ∈ E

has exactly two blocks and satisﬁes ∆

⊆ ρ

Proof Suppose to the contrary that for every 0 <i<pthere is θ

∈ E

with exactly two

blocks B

and B

such that ∆

⊆ ρ

\ ρ

.Weshow:

Claim 1: ∆

∩ ρ

⊆ ω

for all 0 <i<p.

Proof: Suppose to the contrary that ∆

∩ ρ

⊆ ω

for some 0 <i<p.Chooseb

∈ B

(l =1, 2) and set

:= pr

(∆

∩ ρ

)={x

| x

...x

∈ ∆

∩ ρ

}