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
Previous Page Next Page