Tarski showed that first-order logic, as well as other sufficiently expressive lan-
guages, involves operations on sets of sequences (see [Ta], VI, VIII). He also showed
that not all operations involved are Boolean. Jonsson and Tarski, in their joint pa-
per [JT] on Boolean algebras with operators called attention to operations that
arise from a certain correspondence. To be more precise, let V be any set and let
0 n UJ. Then to any n + 1-ary relation R on V there corresponds the n-ary
operation R* on the power set {X : X C V} of V that, when n = 1 satisfies the
following condition and, when n ^ 1, satisfies a similar condition:
For any set XCV, R*(X) is the direct image
{y.xRy for some xG X} of X under R.
When this condition holds, then i?* shall be induced by R. Also, any operation
that is induced by some R shall be relation-induced. While these notions apply
to any set V, in connection with first-order logic V is, for some set U ^ 0 serving
as universe or base set (or "alphabet"), the set VJJ of sequences ("words") that are
formed from elements of U.
Relation-induced operations play a major role in classical as well as non-
classical first-order logic. For studying these logics it has been useful to study,
by themselves, the Boolean operations involved or, respectively, their non-classical
counterparts. This suggests that it may be good strategy to also study, by them-
selves, the pertinent relation-induced operations.
One of the relation-induced operations used in the theory of relation algebras,
which deals with a fragment of first-order logic, is 2-ary, namely the operation
of forming the relative product of two relations. In contrast, the survey given in
Chapter 5 of [HMT] suggests that in most, and perhaps in all, algebraic theories of
full first-order logic, every relation-induced operation serving as primitive is either Cl-
ary or 1-ary and hence every inducing relation is either 1-ary or 2-ary. For example,
in the theory of cylindric set algebras as described in Section 1.1 of [HMT], every
Previous Page Next Page