Abstract

Let U be any nonempty set and let [°^U = \Jnu;

nU

be the set of sequences

(xo, • • • 5

xn-i)

such that 0 n UJ and each xm is in U. For 0 i cu, 0 j UJ

and " concatenation of sequences, let g*, p^, and e^- be the partial function on

[O,U)JJ

faafc

w n e n

the associated if-clause holds satisfies the equality given below

and that otherwise is undefined.

qi((x0,...,xn-i)) = (xo,..-,Xi-1)~{xi+1,...,xn-i), \rni.

Pi((x

0

,...,a:

n

_i)) = ( x

0

, . . . , ^ _ i ) ^ ( ^

+

i , Xi)"(xi

+ 2

.. z

n

-i) ,

if n i + 1.

e

i:/

((xo,...,x

n

_i)) = (x

0

,...,x

n

_i) , i f n 2 , n j , anc Xi = Xj.

If [/ 2, then the converse ^ of qi is not single-valued, where* pY = Pi and

e^ = e^-. With o being relative product let Sq, Spi Se be the closure under o of

{qi : i

UJ}

U { ^ : z u;}, {p* : i a;}, or {ei5 : i, j u, {ij} ^ {0}},

respectively. Also, let Spq, Spe, Spqe be the closure under o of Sp U Sqi SPU Se, or

SpUSqUSe, respectively. For several of these six inductively defined sets S of binary

relations on

[°U)U

we will give an explicit characterization. For any of these six

sets S the structure (5, o,^ , C), where C is set inclusion, is an ordered semigroup

with involution which, up to isomorphism, is the same for any U such that U 2.

For each of these structures except when S is Se we will give a presentation. We

will also give a presentation of those structures which result from these when one

changes from sequences that are finite to those of length UJ.

Let Opqe be the set of those unary operations F on the set {W : W C \.°^)jj}

such that, for some R in Spqe, given any W in the set, F(W) is the direct image

{y : (w,y) G R for some w in W} of W under R. Consider any ([/, Xs)sr] such

that each X$ is an n^-ary relation on U for some n$, 0 ns UJ, and such that at

least one X$ is nonempty. Also consider any m-ary relation Y on U, 0 m UJ.

Then Y is definable in (U, Xs)srj by a first-order formula (with equality but

ix