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

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

Completeness of uniformly delayed op erations 133

σ is proper. On the other hand σ

=(ρ

g+r

◦ ρ

) ∩ ρ

=(ρ

g+r

◦ ι

) ∩ ι

= ρ

g+r

∩ ι

.Here

+ r ∈ L by the deﬁnition and 0 ∈ L and so by Lemma 6.9 we have ρ

g+r

∈ S

◦

for some

divisor m of k, m =1. Thusσ

+ r

= ∅. Clearly σ

=(ρ

n+r

◦∅) ∩∅= ∅ if r does not divide

n.Consequently|I

| < |I|. Since clearly also p

≤ p

, this contradicts the strictness of ρ. 2

6.11 Lemma Let ρ ∈ A

. Then there exists a divisor m>1 of k such that ρ

∈ S

◦

for all

i ∈ I

Proof We know from Lemma 6.9 that for every i ∈ I := I

we have ρ

∈ S

◦

for some divisor

of k. In view of Lemma 6.10 clearly m

> 1. Suppose m

= m

for some 0 ≤ i<j<p

Put σ

:= ρ

for all n ≥ 0. Then σ

= ι

while σ

∈ S \ ι

.Thusσ is proper and so clearly

σ ∈ A

. However, this contradicts Lemma 6.10 and therefore all the m

are equal. 2

Denote by A

the set of all ρ ∈ A

for which there is a prime divisor q of k such that

∈ S

◦

for all i ∈ I

.Wehave:

6.12 Proposition The set V

∪ A

∪R

is B-generic.

Proof Let ρ ∈ A

. By Lemma 6.11 there is a divisor m>1ofk such that ρ

∈ S

◦

for

all i ∈ I

. Choose a prime divisor q of m and put m



:= m/q. For all n ≥ 0 put σ

:= ρ



It is easy to see that I

= I

, p

≤ p

and that σ

∈ S

◦

for all i ∈ I

.Moreover,σ ∈ [ρ]and

so σ ∈ A

dominates ρ. 2

The following lemma relates r and p.

6.13 Lemma Let ρ ∈ A

have period p and satisfy 0 ∈ I = I

. Then there exists a divisor

r of p such that

(1) p/r = p

···p





for some  ≥ 0, primes p

< ···<p



and positive integers d

,...,d



(2) r = p

···p





for some nonnegative integers c

,...,c



(3) I = {0,r,2r,...,p−r},

(4) ρ

,ρ

,...,ρ

p−r

∈ S

◦

for some prime divisor q of k.

Proof The condition (4) is just a part of the deﬁnition of A

. Recall that A

⊆ A

and so the

conclusion of Lemma 6.8 holds. Let ρ satisfy (1) from Lemma 6.8. Applying Proposition 5.7

we obtain (3). Thus let ρ satisfy (2) from Lemma 6.8. Then I = {0,i} for some 0 <i<p

and ρ

=˘ρ

= ρ

. We need the following:

Claim: We have p =2i.

Proof: Suppose to the contrary that 2i = p.Putτ

:= ρ

◦ (˘ρ

n+i

)

for all n ≥ 0. On one

hand in view of ρ

=˘ρ

,wehave(˘ρ

)

=(˘ρ

)

= ι

and therefore τ

= ρ

◦ ι

= ρ

.Onthe

other hand, ρ

= ∅ due to 2i = p and so τ

= ρ

◦ (

∅)

= ∅.Sinceτ

= ∅◦(˘ρ

i+j

)

= ∅ for

all j ∈ p \{0,i},wehaveI

= {0}.Sinceτ ∈ [ρ]isproperandp

= p, this contradicts the

strictness of ρ.Thisprovestheclaim. 2

Now we can apply Lemma 5.6. In our case r = i and p/r =2,sor =2

for some b ≥ 0

and consequently p =2i =2

b+1

proving (3) in this case. 2

134 T.HikitaandI.G.Rosenberg

6.14 Consider ρ ∈ A

with period p and I := I

= {0,r,...,p− r}.Thecasep =2r is

relatively simple and will be dealt with separately later. For notational simplicity we also

assume r = 1. It is easy to see that our results for r = 1 can be blown up to the case r>1.

We have ρ

= s

◦

for some s

∈ S

(i =0,...,p− 1) where q is a prime divisor of k.Westart

with the following:

6.15 Lemma Let ρ be as in 6.14.Then

(1) If i

,...,i

,...,j

∈ p and α := ρ

◦···◦ρ

, β := ρ

◦···◦ρ

are not disjoint

then for all n ≥ 0,

◦···◦ρ

= ρ

◦···◦ρ

(2) ρ

,...,ρ

p−1

are pairwise distinct.

Proof (1) Choose ab ∈ α ∩ β. For all n ≥ 0set

:= ρ

◦···◦ρ

◦ ˘ρ

◦···◦˘ρ

; σ

:= pr

{xx | xx ∈ τ

Clearly aa ∈ α ◦

β = τ

, whence a ∈ σ

. By the minimality of ρ, the unary polyrelation σ is

improper and so σ

= k proving τ

= ι

. From Lemma 6.10 we obtain that τ is improper. In

view of τ

∈ S

◦

clearly τ

= ι

for all n ≥ 0 and (1) follows from the deﬁnition of τ

(2) Suppose to the contrary that s

= s

for some 0 ≤ i<j<p. By (1) clearly ρ

+ n

for all n ≥ 0. It is easy to see that then ρ is periodic with period d =gcd(p, j −i) <p,

a contradiction. 2

6.16 Put T

:= {s

,...,s

p−1

}.Fors, t ∈ S we deﬁne the product st by setting (st)(x):=

t(s(x)).

Denote by G

the subgroup [T

]ofS generated by T

.Inotherwords,G

is the set of all

products s

···s

with m>0andi

,...,i

∈ p (this is indeed a group because s

−1

= s

q− 1

for all i ∈ p). Denote by e the identity permutation on k.Furthersets



:= s

for all

i ∈ p and deﬁne a binary relation ϕ

on G

by setting

:= {(s

···s



···s



) | u>0,i

,...,i

∈ p}.

We shall often use the following lemma.

6.17 Lemma If ρ is as in 6.14 then:

(1) T

⊆ S

for some prime divisor q of k and G

⊆{e}∪



| m>1 divides k}.

(2) ϕ

is the diagram (graph) of an automorphism f

of the permutation group G

Proof (1) The ﬁrst statement is just Lemma 6.13 (4). For the second one let g = s

···s

∈

\{e}.Putτ

:= ρ

n+i

◦···◦ρ

n+i

for all n ∈ p.Nowτ

= s

◦

◦···◦s

◦

= g

◦

= ι

and so

τ is proper. Since τ ∈ A

, from Lemma 6.9 (1) we see that τ

∈ S

◦

for some divisor m of k

proving g ∈ S

(2) First we prove:

Claim 1: The relation ϕ

is the diagram of a selfmap f

of G

Completeness of uniformly delayed op erations 135

Proof: Let s

···s

= s

···s

for some i

,...,i

,...,j

∈ p.Forn = 1 Lemma 6.15 (1)

yields s



···s



= s



···s



. 2

Claim 2: The map f

is injective.

Proof: Let s



···s



= s



···s



.Forn = p −1 Lemma 6.15 (1) yields s

···s

= s

···s

A direct veriﬁcation shows that f

is an endomorphism of G

, i.e. f

(ab)=f

(a)f

(b)for

all a, b ∈ G

. Combining this with Claims 1 and 2 we obtain (2). 2

6.18 We write H ≤ G to indicate that H is a subgroup of a group G. For a selfmap f of

G, a subgroup H is f -closed if f(H) ⊆ H.DenotebyA

the set of all ρ ∈ A

such that {e}

and G

are the only f

-closed subgroups of G

.Wehave:

6.19 Lemma Every ρ ∈ A

is dominated by some σ ∈ A

Proof Choose an inclusion-minimal member H of

{X ≤ G

| X>{e} is f

-closed}

and let s ∈ H \{e}. By Lemma 6.17 (1) we have s ∈ S

for some divisor m of k with

m>1. Choose a prime divisor n of m and set t := m/n.Ass consists of k/m cycles of

length m, clearly s

∗

:= s

has t cycles of length n and so s

∗

∈ (H \{e}) ∩ S

.Inviewof

∗

∈ (H \{e}) ⊆ G

\{e} we have that s

∗

= s

···s

for some u>0andi

,...,i

∈ p.Set

:= ρ

n+i

◦···◦ρ

n+i

for all n ≥ 0. Clearly σ

= s

∗◦

, hence σ is proper and σ ∈ [ρ] ∩ A

dominates ρ.SetT

∗

:= {f

∗

) | n ∈ p} and notice that the permutation group G

generated by T

∗

.NextG

is a subgroup of H due to s

∗

∈ H, the deﬁnition of T

∗

and the

fact that H is f

-closed. From the deﬁnition of σ it follows directly that f

is the restriction

of f

to G

.NowG

is f

-closed by Lemma 6.17 (2) and so G

is f

-closed. Finally by the

minimality of H we have G

= H and therefore σ ∈ A

. 2

6.20 Recall that for a prime q an elementary Abelian q-group G is an Abelian group

G;+, −, 0 in which every g ∈ G \{0} is of order q. It is well known that a ﬁnite ele-

mentary q-group is isomorphic to the additive group of a ﬁnite vector space over the Galois

ﬁeld GF(q) (also denoted F

). This can be described more explicitly as follows.

Let m>0. For a =(a

,...,a

) ∈ q

,b=(b

,...b

) ∈ q

put a+b := (a

⊕b

,...,a

⊕

)whereby⊕ denotes the mod q sum on q := {0,...,q−1}. Now a ﬁnite Abelian elementary

q-group G is isomorphic to some q

;+,

0 where

0:=(0,...,0); in particular |G| = q

for

some m>0.

For the following proposition we are indebted to P. Frankl and P. P. P´alfy (personal

communications 1983 and 1998).

6.21 Proposition Let ρ ∈ A

and let q be a prime divisor of k such that ρ

∈ S

◦

for all

i ≥ 0.ThenG

is an elementary Abelian q-group.

Proof

Claim: G

is Abelian.

Proof: Suppose to the contrary that G

is noncommutative. We show:

136 T.HikitaandI.G.Rosenberg

Fact: The automorphism f

is ﬁxed-point free (i.e., the identity e is the unique ﬁxed-point of

Proof: Suppose to the contrary that f

(g)=g for some g ∈ G

\{e}. Clearly f

ﬁxes the

cyclic subgroup H of G

generated by g. From Lemma 6.19 we get H = G

, a contradiction

since H is abelian. This proves the fact. 2

Applying a well-known theorem (see e.g. [Go68, Theorem 10.1.2 p. 335]) we obtain that

ﬁxes a unique Sylow q-subgroup H of G

and therefore again G

is a Sylow q-group. Now

a q-group is nilpotent (see e.g. [Go68, Theorem 2.3.3 p. 22]) and hence L =[G

]isa

proper subgroup of G

.Heref

ﬁxes L, a contradiction. Thus G

is abelian. 2

Now the generators s

,...,s

p−1

of G

belong to S

and hence they are all of order q and

so in the Abelian group G

every element is of order q.ThusG

is an elementary Abelian

q-group. 2

The remainder of this section is essentially due to P. Frankl (personal communication

1983).

6.22 By Proposition 6.21 the group G

is isomorphic to the additive group of an m-

dimensional vector space V

over GF (q) (whose universe is q

). Denote by ϕ : g → ˆg

this isomorphism from G

onto V

and for all j ∈ n set x

:= ˆs

. We need the following.

6.23 Fact Let Y be an m×m matrix over q and e

:= (1, 0,...,0) ∈ q

.IfY is nonsingular

over GF (q) then e

= e

for some h>0.

Proof The members of the sequence e

Y,e

,... belong to the ﬁnite set q

and so there

is a repetition in the sequence; i.e., e

i+h

= e

for some i ≥ 0andh>0. Now, Y being

nonsingular, we have e

= e

. 2

6.24 For ˜α =(α

,...,α

m−1

) ∈ q

denote by Y

˜α

the m × m matrix

˜α

⎡

⎢

⎣

010··· 00

001··· 00

000··· 01

··· α

m−2

m−1

⎤

⎥

⎦

As det Y

˜α

=(−1)

m−1

, clearly Y

˜α

is nonsingular if and only if α

=0. Nowwehave:

6.25 Lemma Let ρ ∈ A

have period p and let q be a prime divisor of k such that ρ

∈ S

◦

for all i ∈ p. Then either

(1) q>2 and there exists 1 <α<qsuch that

(a) p is the least positive integer solution h of α

≡ 1(modq) and

(b) x

= α

for all j ∈ p,or

(2) There exist 1 <m<pand ˜α =(α

,...,α

m−1

) ∈ q

such that

Completeness of uniformly delayed op erations 137

(a) α

=0,

(b) p is the least positive integer solution h of e

˜α

= e

,and

→ e

˜α

from {s

| j ∈ p} to V

extends to an isomorphism from G

onto V

Proof Put x

:= ˆs

for all j ∈ p. We start with the following:

Claim: x

+ ···+ x

p−1

=0.

Proof: Put τ

:= ρ

◦ ρ

n+1

◦···◦ρ

n+p−1

for all n ∈ p. On account of G

Abelian we have

= τ

for all n ∈ p.Wereτ

= ι

, the proper polyrelation (τ

,τ

,...) would dominate ρ.

This being impossible, τ

= ι

proving the claim. 2

Now there exists a least 0 <d<pfor which

+ ···+ α

+ d

=0 (6.1)

holds for some i ∈ p and α

,...,α

i+d

∈ p with α

=0= α

i+d

since by the claim the

equation (6.4) holds for i =0,d = p − 1andα

= ···= α

p−1

= 1. Taking an appropriate

shift of ρ, without loss of generality we may assume that i = 0. Also multiplying (6.1) by the

inverse of −α

in the ﬁeld GF (q)wegetα

= −1. Thus

+ ···+ α

d−1

− x

=0 (6.2)

where α

= 0. The automorphism f

transforms (6.2) into

+ ···+ α

d−1

+(d−1)

− x

+ d

=0 (6.3j)

for all j ∈ p. From (6.2)

= α

+ ···+ α

d−1

. (6.4)

Denote by H the subspace of V

generated by x

,...,x

d−1

.From(6.4)wehavex

∈ H.An

easy induction on j =0,...,p− d − 1 based in (6.3j)showsthatx

,...,x

p−1

∈ H. Clearly

is generated by x

,...,x

p−1

because G

is generated by s

,...,s

p−1

; therefore H = V

Moreover, our choice of d guarantees that the set B := {x

,...,x

d−1

} is independent

(in the vector space V

; i.e., a linear combination of x

,...,x

d−1

equals 0 if and only if all

coeﬃcients are 0) and so B is a basis of V

.Inparticular,d = m. We have two cases.

(i) Let m =1. From(6.3j)weobtainx

=(α

)

for all j ∈ p. Clearly α

=1andp is

the least integer h such that α

≡ 1(modq) (the so-called index of α

(ii) Let m>1. Put

:= (1, 0,...,0),...,e

:= (0,...,0, 1). (6.5)

As B is a basis of V

, the above isomorphism ϕ : G

→ V

canbechosensothatx

= e

i+1

for i =0,...,m− 1. The automorphism f

of G

becomes a linear transformation of V

It is easy to check that this linear transformation sends x to xY

˜α

for all x ∈ q

(with the

matrix product, and ˜α =(α

,...,α

m−1

)wherebyx is considered as a 1 ×m matrix) and Y

˜α

from 6.24. A direct check shows that indeed e

˜α

= e

j+1

for j =1,...,m−1 and that (6.3j)

holds for all j ∈ p.Moreover,x

= e

˜α

for all j ∈ p and so p is indeed the least positive

integer h satisfying e

˜α

= e

. 2

138 T.HikitaandI.G.Rosenberg

,...,x

p−1

2 1, 2, 4, 3

1, 3, 4, 2

1, 4

Table 1: m =1andq =5

6.26 Examples

(1) Let m =1andq = 5. All three sequences 1,x

,...,x

p−1

are given in Table 1.

(2) Let m =2andq =3. Wechoosex

=(1, 0) and x

=(0, 1). We have six matrices

˜α

with α

∈{1, 2} and α

∈ 3. The calculation of the powers of Y

˜α

yields the values of p

given in Table 2.

0 2α

1 =0 8

=0 6

Table 2: m =2andq =3

For example, consider the second case α

=1,α := α

=0. Takingintoaccountα

≡ 1

(mod 3) the consecutive powers of Y

˜α

are

˜α

1 α

α 2

2 α

22α

2α 1

The corresponding sequence x

,...,x

(1, 0), (0, 1), (1,α), (α, 2), (2, 0), (0, 2), (2, 2α), (α, 0).

We describe concretely the permutations s

6.27 (1) Consider case (1) of Lemma 6.25. Then s

∈ S

is arbitrary and s

= s

for all

j ∈ p.

(2) Consider case (2) of Lemma 6.25. We need:

Fact: If 0 ≤ i<j<mand C and C



are cycles of s

and s

then |C ∩ C



|≤1.

Proof: Let a, b ∈ C ∩ C



.Thens



(a)=b = s

(a)forsome, n ∈ q.Thusρ



∩ ρ

non-void and from Lemma 6.15 (1) we obtain ρ



= ρ

.Thuss



= s

and this translates

Completeness of uniformly delayed op erations 139

into e

= ne

. Recalling from the proof of Lemma 6.25 (2) that {e

,...,e

m−1

} is a

basis of the vector space V

we obtain that the set {e

} is linearly independent (over

GF (q)). Thus  = n =0andb = s

(a)=a. This proves the fact. 2

Recall that s

,...,s

m−1

permute pairwise and that each s

is ﬁxed-point free and all

its cycles are of length q. This and the fact shows that k is the disjoint union of

blocks of size q

and thus q

divides k. Setting l := kq

−m

we can identify k with

l × q

.Nowfor(u, v) ∈ l × q

and j ∈ m we put s

(u, v):=(u, v ⊕ e

j+1

)(where

⊕ denotes addition on V

, i.e., the componentwise mod q addition on q

)ande

(1, 0,...,0),...,e

m−1

:= (0,...,1, 0),e

:= e

.Sinces

,...,s

m−1

generate G

,each

s ∈ G

respects the above blocks; in particular this holds for s

,...,s

p−1

.Form ≤

j<pand e

˜α

=(c

,...,c

m−1

)wecansets

:= s

···s

m−1

7 Order polyrelations

7.1 Sections 7 and 8 treat the remaining case of reﬂexive binary polyrelations from R

.The

set R

from Lemma 6.3 consists of proper binary periodic polyrelations ρ =(ρ

,ρ

,...)such

that ρ

= k

for no i ≥ 0 and every ρ

= ∅ is reﬂexive. First we eliminate ρ

= ∅.Denoteby

the set of all proper binary periodic polyrelations ρ =(ρ

,ρ

,...)withι

⊆ ρ

⊂ k

for

all i ≥ 0. We have:

7.2 Lemma Every ρ ∈ R

is dominated by some σ ∈ R

Proof Let ρ ∈ R

.Sinceρ is proper, through an appropriate shift we can get ι

⊂ ρ

⊂ k

Put λ := (ι

,ι

,...). For j ≥ 0 put τ

:= (ρ

,ρ

j+1

,...)ifρ

= ∅ and τ

:= λ if ρ

= ∅.We

show τ

⊆ τ

i+j

for all i, j ≥ 0. Indeed, if ρ

= ∅ then τ

= ρ

j+i

= τ

i+j

while for ρ

= ∅ we

get τ

= ι

⊆ τ

i+j

because τ

i+j

= ι

if ρ

i+j

= ∅ and τ

i+j

= ρ

i+j

⊇ ι

if ρ

i+j

= ∅.Moreover,

∈ [ρ] for all j ≥ 0. Indeed, if ρ

= ∅ then Pold τ

=Poldρ while Pold τ

=Poldλ = U

if ρ

= ∅. Thus the upper superposition σ of τ

,τ

,... dominates ρ. It is easy to see that

= ρ

if ρ

= ∅ and σ

= ι

if ρ

= ∅.Thusσ belongs to R

and dominates ρ. 2

A binary relation σ is symmetric, antisymmetric or transitive if σ =˘σ, σ ∩ ˘σ = ι

and

⊆ σ, respectively. A reﬂexive, antisymmetric and transitive relation is an order. A binary

polyrelation λ =(λ

,λ

,...)issymmetric, antisymmetric,ortransitive,ifallλ

are reﬂexive

as well as symmetric, antisymmetric or transitive, respectively. Denote by M the set of all

binary, symmetric, proper and periodic polyrelations on k (i.e., proper ρ =(ρ

,ρ

,...)with

⊆ ρ

⊆ k

and ρ

=˘ρ

for all i ≥ 0; note that here we allow also ρ

= k

). Further denote

by P the set of binary antisymmetric proper polyrelations on k.Wehave:

7.3 Lemma Every ρ ∈ R

is dominated by a polyrelation from M ∪ P .

Proof Let ρ ∈ R

\ P .Thenρ

∩ ˘ρ

⊃ ι

for some i ≥ 0. Put τ

:= ρ

∩ ˘ρ

for all n ≥ 0.

Now ι

⊂ τ

⊆ ρ

⊂ k

and so τ is proper. Clearly τ is symmetric and so τ ∈ M dominates

ρ. 2

7.4 Let ξ be a binary reﬂexive and antisymmetric relation on k.Callx ∈ k a least (greatest)

element of ξ if x × k ⊆ ξ (k × x ⊆ ξ). Notice that if ξ has a least (greatest) element then it

is unique. Call ξ bounded if it has both a least and a greatest element.

140 T.HikitaandI.G.Rosenberg

Denote by P

the set of all ρ ∈ P such that every ρ

⊃ ι

is bounded. We have:

7.5 Lemma Let σ ∈ P satisfy [σ] ∩M = ∅. Then every proper binary ρ ∈ [σ] belongs to P

Proof Put p := p

and I := {i ∈ p | ρ

⊃ ι

}.Formτ

:= ρ

◦ ˘ρ

for all i ≥ 0. Now τ ∈ [σ]is

obviously reﬂexive and symmetric and ρ

⊆ τ

by reﬂexivity. If τ

⊂ k

for at least one i ∈ I

then τ is proper in contradiction to [σ] ∩ M = ∅.Thusτ

= k

for all i ∈ I.Forn ≥ 2 put

(n)

:= {x

...x

| x

u,...,x

u ∈ ρ

for some u ∈ k}.

Now λ

(2)

= τ

= k

, and by Theorem 4.2 an easy induction shows λ

(n)

= k

for n =2,...,k.

In particular, λ

(k)

= k

, i.e., for each i ∈ I the relation ρ

has a greatest element l

.Itcanbe

easily veriﬁed that for every binary polyrelation σ =(σ

,σ

,...) the converse polyrelation

˘σ =(˘σ

, ˘σ

,...) satisﬁes Pold σ =Pold˘σ. The same argument applied to ˘ρ := (˘ρ

, ˘ρ

,...)

yields that for each i ∈ I the relation ρ

has a least element o

. 2

Denote by P

the set of all ρ ∈ P

such that every ρ

⊃ ι

is a bounded order. We have:

7.6 Lemma Every ρ ∈ P is dominated by a polyrelation from M ∪P

Proof There is nothing to prove if [ρ] ∩ M = ∅. Thus assume [ρ] ∩ M = ∅.Thenρ ∈ P

Lemma 7.5. Put τ

:= ρ

(= ρ

◦···◦ρ

with k factors) for all n ≥ 0. Let i ∈ I := {j ∈ p

⊃ ι

} and denote by l

the greatest element of ρ

.Nowτ

= k

because l

x ∈ τ

holds only

for x = l

.Thusρ

⊆ τ

⊂ k

proving that τ is proper. Note that all τ

are transitive. For all

i ≥ 0 put ξ

:= τ

∩ ˘τ

.Wereι

⊂ ξ

for at least one i ∈ I we would have ξ ∈ [ρ] ∩ M.Thus

is also antisymmetric; hence τ

is a bounded order for all i ∈ I proving τ ∈ P

. 2

7.7 Next we pick an optimal polyrelation ρ ∈ P

\M (see Proposition 5.7). Formally, denote

by P

the set of all ρ ∈ P

such that

(1) [ρ] ∩ M = ∅,

(2) For every λ =(λ

,λ

,...) ∈ [ρ] ∩ P

≥ p := p

and p

= p =⇒|λ

| + ···+ |λ

p−1

|≥|ρ

| + ···+ |ρ

p−1

On account of periodicity and ﬁniteness we have the following:

7.8 Lemma Every ρ ∈ P

is dominated by some σ ∈ P

In Lemmas 7.9 and 7.10 we completely describe P

. In Lemmas 7.9 and 7.10 ρ is always

a ﬁxed polyrelation from P

with period p and

c := |ρ

| + ···+ |ρ

p−1

|,I:= {i ∈ p | ρ

⊃ ι

7.9 Lemma We have ρ

∩ρ

i+d

= ι

for all 0 <d<p.

Completeness of uniformly delayed op erations 141

Proof Suppose ρ

∩ ρ

j+d

⊃ ι

for some j ∈ p and 0 <d<p.Formτ

= ρ

∩ ρ

i+d

for all

i ≥ 0. By Lemma 7.5 and [ρ] ∩M = ∅ we have τ ∈ P

.Nowforalli ≥ 0therelationτ

is the

intersection of two orders and therefore an order. Since ι

⊂ τ

⊆ ρ

⊂ k

, the polyrelation

τ is proper and so τ ∈ P

. Clearly p

≤ p andinviewofρ ∈ P

,alsop ≤ p

.Thusp

= p

and from the deﬁnition of P

we have t := |τ

| + ···+ |τ

p−1

|≥|ρ

| + ···+ |ρ

p−1

| =: c.

Now ρ

⊇ τ

for all i ∈ p and so c ≥ t proving c = t. This together with ρ

⊇ τ

shows

= τ

for all i ∈ p. This yields ρ

⊆ ρ

i+d

for all i ∈ p.Consequentlyρ

⊆ ρ

i+d

⊆··· ⊆

i+pd

= ρ

and therefore ρ

= ρ

i+d

for all i =0,...,p− 1. However, then ρ has period d

strictly less than p. This contradiction proves the lemma. 2

7.10 Lemma We have p =2r, I = {0,r},andρ

=˘ρ

Proof We may assume that 0 ∈ I. We start with:

Claim 1: |I| > 1.

Proof: Suppose |I| =1. ThenI = {0}. For all n ≥ 0setτ

:= ρ

◦ ρ

n+1

◦···◦ρ

n+p−1

.Itis

easy to see that τ

= ρ

for all n ≥ 0andsoτ is dominated by (ρ

,ρ

,...), a contradiction.

Denote by r the least positive integer such that j

+ r ∈ I for some j ∈ I.

Claim 2: ρ

⊆ ˘ρ

n+r

for all n ∈ p.

Proof: For i ∈ I denote by o

and l

the least and greatest elements of ρ

.Letj ∈ I

satisfy j

+ r ∈ I. Notice that the ordered pairs o

j+r

and o

j+r

belong to ρ

∩ ρ

j+r

.As

∩ρ

j+r

= ι

from Lemma 7.9, we obtain o

= l

j+r

and l

= o

j+r

. Now put τ

:= ρ

∩ ˘ρ

n+r

for all n ≥ 0. Now o

= l

j+r

∈ τ

proving that τ is proper. The argument used in the

proofofLemma7.9yieldsτ

= ρ

for all n ∈ p. Finally τ

= ρ

∩ ˘ρ

n+r

= ρ

shows that

⊆ ˘ρ

n+r

. 2

In particular, we have ρ

⊆ ˘ρ

⊆ ρ

.Nowp divides 2r because otherwise by Lemma 7.9

we would have ρ

= ρ

∩ ρ

= ι

in contradiction to 0 ∈ I.Inviewof0<r<pwe have

p =2r. The minimality of r and 0 ∈ I show that I = {0,r}. Finally by Claim 2 we have

⊆ ˘ρ

⊆ ρ

proving ρ

=˘ρ

. 2

Now we have:

7.11 Theorem

(1) The set P

consists of ρ with period 2

> 1 and such that ρ

is a bounded order, ρ

m−1

its converse and ρ

= ι

otherwise.

(2) Ξ

= V

∪ A

∪ P

∪ M is B-generic.

Proof (1) By Lemma 7.10 we have p =2r and from Lemma 5.6 (2) r =2

for some

b ≥ 0. Now (1) follows from Lemma 7.10, and (2) follows from Lemma 6.7, Proposition 6.21,

Lemmas 7.2, 7.3, 7.6 and 7.8. 2

142 T.HikitaandI.G.Rosenberg

8 Reﬂexive Symmetric Polyrelations

8.1 In this section we study the set M of symmetric binary proper polyrelations. We need

the following terminology.

Let σ be a binary reﬂexive and symmetric relation on k. A subset C of k is a clique of σ

if C

⊆ σ.Thecenter C

of σ is the set {x ∈ k | x ×k ⊆ ρ}.If∅ = C

⊂ k the relation σ is

called central.

Given binary reﬂexive relations σ

and σ

deﬁne

∗ σ

:= {xy | xu, yv ∈ σ

and uy, vx ∈ σ

for some u, v ∈ k}.

It is easy to see that σ

∗ σ

is always a symmetric relation and σ

∪ σ

⊆ σ

∗ σ

and if σ

and σ

are symmetric then σ

∗ σ

= σ

∗ σ

. A binary polyrelation ρ =(ρ

,ρ

,...) ∈ M is

central if every ρ

⊂ k

is central.

As in the preceding sections we choose ρ with ﬁrstly the least possible period and secondly

the largest sum of relation sizes. Formally, polyrelation ρ =(ρ

,ρ

,...) ∈ M with period p

is rich if every λ ∈ [ρ] ∩M satisﬁes (i) p

≥ p and (ii) |λ

|+ ···+ |λ

p−1

|≤|ρ

|+ ···+ |ρ

p−1

whenever p

= p.DenotebyM

the set of rich polyrelations. A standard argument (based

on ﬁniteness) shows:

8.2 Lemma Every polyrelation from M is dominated by some polyrelation from M

The following lemma will be used several times.

8.3 Lemma Let ρ ∈ M

.Ifλ ∈ [ρ] ∩ M satisﬁes p

≤ p

and λ

⊇ ρ

for all i ∈ p then

λ = ρ.

Proof First p

= p := p

by the deﬁnition of richness. Let c := |ρ

| + ···+ |ρ

p−1

| and

d := |λ

| + ···+ |λ

p−1

|. Clearly d ≥ c on account of λ

⊇ ρ

for all i ∈ p and c ≥ d by the

richness of ρ and so c = d. Using again λ

⊇ ρ

for all i ∈ p we obtain |λ

| = |ρ

| and by the

same token we have λ

= ρ

for all i ∈ p proving λ = ρ. 2

In 8.4–8.7 ρ =(ρ

,ρ

,...) is a ﬁxed polyrelation from M

with period p,andsuchthat

⊂ ρ

⊂ k

.ForI ⊆ p put ρ



i∈I

.FurtherletJ consist of the nonempty subsets I

of p such that ρ

⊃ ι

8.4 Lemma (1) J contains all singletons {i} (i ∈ p).

(2) The set p does not belong to J,and

(3) ρ

∗ ρ

i+d

= k

for all i ∈ p and 0 <d<p.

Proof (2) Suppose to the contrary that p ∈ J.Thenρ

:= ρ

∩···∩ρ

p−1

⊃ ι

.Inview

of k

⊃ ρ

⊇ ρ

the relation ρ

is a nontrivial (reﬂexive and symmetric) binary relation.

Put τ

:= ρ

∩···∩ρ

n+p−1

for all n ≥ 0. Then ρ is dominated by the proper polyrelation

(ρ

,ρ

,...) and this contradiction proves (2).

Let 0 <d<p.Forx ≥ 0formλ

:= ρ

∗ ρ

x+d

.Thenλ ∈ [ρ]andλ is reﬂexive and

symmetric. Moreover, λ

⊇ ρ

∪ρ

x+d

and taking into account that ρ is rich, from Lemma 8.3

we obtain that either λ is improper or λ = ρ. In the latter case from ρ

= λ

⊇ ρ

∪ρ

x+d

obtain ρ

⊇ ρ

x+d

.Thusρ

⊇ ρ

x+d

⊇···⊇ρ

x+pd

= ρ

; hence ρ

= ρ

x+d

and ρ has period