Boolean algebra with operators

An operator on a Boolean algebra $ \mathbf B $ is a finitary operation on the Boolean algebra that is additive, meaning that in each of its arguments it preserves the sum/join operation of $ \mathbf B $. An operator is normal if each argument preserves the least element of $ \mathbf B $. Major examples of normal operators are as follows.

Relation algebras: the algebra of binary relations on a set $ X $( i.e. the set of subsets of $ X ^ {2} $) has the binary operator $ R \circ S $ of composition of relations and the unary inverse operator $ R ^ {- 1 } $. The axiomatic study of these operators quickly leads to deep questions about representability of equationally defined abstract algebras as concrete algebras of relations (cf. [a8], [a9]).

Cylindric algebras: on the algebra of subsets of a Cartesian product set $ X ^ {m} $, let $ c _ {k} $ be the operator assigning to each $ A \subseteq X ^ {m} $ the cylinder generated by translating $ A $ parallel to the $ k $- th coordinate axis. If $ A $ is defined by a formula $ \varphi $ having variables $ v _ {1} \dots v _ {m} $, then the cylinder $ c _ {k} ( A ) $ is defined by the existentially quantified formula $ \exists v _ {k} \varphi $. This observation leads to a comprehensive algebraic theory with many applications to quantificational logic [a6]. A related theory of polyadic algebras, due to P.R. Halmos [a5], emphasizes operators corresponding to the logical operation of substitution of terms for variables.

Complex algebras: a binary relation $ R \subseteq X ^ {2} $ defines an operator $ f _ {R} $ on the power set $ 2 ^ {X} $, in which $ f _ {R} ( A ) = \{ y : {\exists x \in A ( xRy ) } \} $ is the $ R $- image of the subset $ A $ of $ X $. This generalizes: each $ ( n + 1 ) $- ary relation on $ X $ gives rises to an $ n $- ary operation on $ 2 ^ {X} $. Thus, any relational structure $ \mathbf X $, comprising a collection of finitary relations on a set $ X $, determines a Boolean algebra with operators $ \mathbf B ( X ) $ based on $ 2 ^ {X} $, known as the complex algebra of $ \mathbf X $( the terminology originates with G. Frobenius in the 1880s, referring to a collection of elements of a group as a "complex" ).

The case of binary relations ( $ n = 1 $) is intimately connected with the study of modal logic [a2]. Another connection is with the algebra of topology [a11]: when $ ( X,R ) $ is a partial ordering, the operator $ f _ {R} $ obeys the Kuratowski axioms for the closure operator on subsets of a topological space. The general theory of Boolean algebras with operators (BAOs) was introduced by B. Jónsson and A. Tarski [a7], who extended the Stone representation theory that embeds a Boolean algebra $ \mathbf B $ into a certain complete and atomic Boolean algebra $ \mathbf B ^ \sigma $, known as the perfect or canonical extension of $ \mathbf B $( cf. also Boolean algebra). They showed that any additive operator on $ \mathbf B $ lifts to a completely additive operator on $ \mathbf B ^ \sigma $ preserving normality, and also that any normal complete and atomic Boolean algebra with operators is isomorphic to the complex algebra of some relational structure. Consequently, each normal Boolean algebra with operators $ \mathbf B $ is isomorphically embeddable into the complex algebra of some structure $ \mathbf X _ {\mathbf B} $.

This representation extends to the level of morphisms: an algebraic homomorphism $ \mathbf B _ {1} \rightarrow \mathbf B _ {2} $ induces a certain type of structure-preserving mapping $ \mathbf X _ {\mathbf B _ {2} } \rightarrow \mathbf X _ {\mathbf B _ {1} } $, called a bounded morphism. This gives rise to a categorical duality between Boolean algebras with operators and (topological) relational structures that is developed and applied in [a1], [a3]. A survey of the theory of Boolean algebras with operators is given in [a10].

Work in algebraic logic has identified a number of structural properties of varieties (equational classes, cf. Algebraic systems, variety of) of Boolean algebras with operators that are related to natural properties of logical systems. This is surveyed in [a4]. A variety $ {\mathcal V} $ is:

i) elementary if generated by the complex algebras of some first-order definable class of relational structures;

ii) complex if each of its members is isomorphically embeddable into some complex algebra that belongs to $ {\mathcal V} $;

iii) canonical if closed under canonical extensions. Every elementary variety is canonical, and every canonical variety is complex. All three notions coincide if the class $ \{ \mathbf X : {\mathbf B ( X ) \in {\mathcal V} } \} $ of all structures whose complex algebra belongs to $ {\mathcal V} $ is closed under ultrapowers.

The variety generated by the complex algebra $ \mathbf B ( \mathbf R, <, > ) $( where $ \mathbf R $ denotes the set of real numbers) is complex but not canonical. In general, complexity of $ {\mathcal V} $ corresponds to the property of strong completeness of a logical system associated with $ {\mathcal V} $. The deepest unresolved question in this area is whether every canonical variety must be elementary: if $ {\mathcal V} $ is closed under canonical extensions, does it follow that there is a first-order definable class of structures whose complex algebras generate $ {\mathcal V} $? An answer either way would enhance the understanding of the relationship between the equational properties of Boolean algebras with operators and the first-order-definable properties of relational structures.

References[edit]