Boolean, Relation-Induced, and Other Operations
for Dealing with First-Order Definability
The notion of first-order definability in a relational structure deals with re-
lations that often are of different finite rank and whose members therefore are
sequences of corresponding different finite length. When investigating the use of al-
gebraic methods for dealing with this notion, it therefore seems a natural and mild
restriction to consider only operations F which, when applied to sets XQ, ..., Xn-\
of finite sequences yield as value a set F(Xo,... , X
_i) that, like each Xm, also
consists of finite sequences.
Several sets of operations of this kind will be considered below. They agree
with respect to those operations F in them for which the following holds: For
some binary relation R between finite sequences, F is the unary operation R* that
maps each set X of finite sequences into the direct image R*(X) {y : (#, y) G
R for some x G X} of X under R. We shall say that R induces F. Any F that is
induced by some R shall be relation-induced.
Besides these relation-induced operations, each of the sets to be considered
will contain at least one Boolean operation. Some of the sets also will contain an
operation of a third kind, namely, the 0-ary operation H{$y whose constant value is
the set {0}, i.e., the set whose only element is the null-sequence, i.e. is the sequence
of length 0. This 0-ary operation is not relation-induced. Nor is the closely related
unary operation F relation-induced that satisfies F(X) = {0} for every X, since
every operation G that is relation-induced satisfies G(0) = 0.
(Let Hf be the unary operation such that H'(Q) = 0 and H'(X) = {0} for any
1 ^ 1 Then, as the referee noted, H' is closely related to #{0} and, moreover, is
induced by the binary relation S$ such that S$ is single-valued and for any finite
sequence x as argument yields as value the empty sequence 0. In contrast to the
relations considered in Chapter II, functions such as S$ that are constant or almost
constant are not uniform.)
Previous Page Next Page