Namespaces
Variants
Actions

Difference between revisions of "Boolean algebra with operators"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (correction)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
An operator on a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107501.png" /> is a finitary operation on the [[Boolean algebra|Boolean algebra]] that is additive, meaning that in each of its arguments it preserves the sum/join operation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107502.png" />. An operator is normal if each argument preserves the least element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107503.png" />. Major examples of normal operators are as follows.
+
<!--
 +
b1107501.png
 +
$#A+1 = 55 n = 0
 +
$#C+1 = 55 : ~/encyclopedia/old_files/data/B110/B.1100750 Boolean algebra with operators
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
Relation algebras: the algebra of binary relations on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107504.png" /> (i.e. the set of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107505.png" />) has the binary operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107506.png" /> of composition of relations and the unary inverse operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107507.png" />. The axiomatic study of these operators quickly leads to deep questions about representability of equationally defined abstract algebras as concrete algebras of relations (cf. [[#References|[a8]]], [[#References|[a9]]]).
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Cylindric algebras: on the algebra of subsets of a Cartesian product set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107508.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b1107509.png" /> be the operator assigning to each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075010.png" /> the cylinder generated by translating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075011.png" /> parallel to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075012.png" />-th coordinate axis. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075013.png" /> is defined by a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075014.png" /> having variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075015.png" />, then the cylinder <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075016.png" /> is defined by the existentially quantified formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075017.png" />. This observation leads to a comprehensive algebraic theory with many applications to quantificational logic [[#References|[a6]]]. A related theory of polyadic algebras, due to P.R. Halmos [[#References|[a5]]], emphasizes operators corresponding to the logical operation of substitution of terms for variables.
+
An operator on a Boolean algebra $  \mathbf B $
 +
is a finitary operation on the [[Boolean algebra|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.
  
Complex algebras: a binary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075018.png" /> defines an an operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075019.png" /> on the power set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075020.png" />, in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075021.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075022.png" />-image of the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075023.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075024.png" />. This generalizes: each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075025.png" />-ary relation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075026.png" /> gives rises to an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075027.png" />-ary operation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075028.png" />. Thus, any relational structure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075029.png" />, comprising a collection of finitary relations on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075030.png" />, determines a Boolean algebra with operators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075031.png" /> based on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075032.png" />, known as the complex algebra of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075033.png" /> (the terminology originates with G. Frobenius in the 1880s, referring to a collection of elements of a group as a  "complex" ).
+
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. [[#References|[a8]]], [[#References|[a9]]]).
  
The case of binary relations (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075034.png" />) is intimately connected with the study of [[Modal logic|modal logic]] [[#References|[a2]]]. Another connection is with the algebra of topology [[#References|[a11]]]: when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075035.png" /> is a partial ordering, the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075036.png" /> obeys the Kuratowski axioms for the closure operator on subsets of a [[Topological space|topological space]]. The general theory of Boolean algebras with operators (BAOs) was introduced by B. Jónsson and A. Tarski [[#References|[a7]]], who extended the Stone representation theory that embeds a Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075037.png" /> into a certain complete and atomic Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075038.png" />, known as the perfect or canonical extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075039.png" /> (cf. also [[Boolean algebra|Boolean algebra]]). They showed that any additive operator on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075040.png" /> lifts to a completely additive operator on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075041.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075042.png" /> is isomorphically embeddable into the complex algebra of some structure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075043.png" />.
+
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 [[#References|[a6]]]. A related theory of polyadic algebras, due to P.R. Halmos [[#References|[a5]]], emphasizes operators corresponding to the logical operation of substitution of terms for variables.
  
This representation extends to the level of morphisms: an algebraic homomorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075044.png" /> induces a certain type of structure-preserving mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075045.png" />, 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 [[#References|[a1]]], [[#References|[a3]]]. A survey of the theory of Boolean algebras with operators is given in [[#References|[a10]]].
+
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" ).
  
Work in algebraic logic has identified a number of structural properties of varieties (equational classes, cf. [[Algebraic systems, variety of|Algebraic systems, variety of]]) of Boolean algebras with operators that are related to natural properties of logical systems. This is surveyed in [[#References|[a4]]]. A variety <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075046.png" /> is:
+
The case of binary relations ( $  n = 1 $)
 +
is intimately connected with the study of [[Modal logic|modal logic]] [[#References|[a2]]]. Another connection is with the algebra of topology [[#References|[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|topological space]]. The general theory of Boolean algebras with operators (BAOs) was introduced by B. Jónsson and A. Tarski [[#References|[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|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 [[#References|[a1]]], [[#References|[a3]]]. A survey of the theory of Boolean algebras with operators is given in [[#References|[a10]]].
 +
 
 +
Work in algebraic logic has identified a number of structural properties of varieties (equational classes, cf. [[Algebraic systems, variety of|Algebraic systems, variety of]]) of Boolean algebras with operators that are related to natural properties of logical systems. This is surveyed in [[#References|[a4]]]. A variety $  {\mathcal V} $
 +
is:
  
 
i) elementary if generated by the complex algebras of some first-order definable class of relational structures;
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075047.png" />;
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075048.png" /> of all structures whose complex algebra belongs to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075049.png" /> is closed under ultrapowers.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075050.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075051.png" /> denotes the set of real numbers) is complex but not canonical. In general, complexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075052.png" /> corresponds to the property of strong completeness of a logical system associated with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075053.png" />. The deepest unresolved question in this area is whether every canonical variety must be elementary: if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075054.png" /> is closed under canonical extensions, does it follow that there is a first-order definable class of structures whose complex algebras generate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110750/b11075055.png" />? 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.
+
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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Goldblatt,  "Varieties of complex algebras"  ''Ann. Pure and Applied Logic'' , '''44'''  (1989)  pp. 173–242</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Goldblatt,  "Mathematics of modality" , ''Lecture Notes'' , '''43''' , Center for the Study of Language and Information, Stanford Univ.  (1993)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R. Goldblatt,  "Elementary generation and canonicity for varieties of Boolean algebras with operators"  ''Algebra Universalis'' , '''34'''  (1995)  pp. 551–607</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Goldblatt,  "Algebraic polymodal logic"  H. Andréka (ed.)  etAAsal. (ed.) , ''Handbook of Algebraic Logic'' , Kluwer Acad. Publ.  (to appear)  (Res. Rep. 96–175, Math. Dept. Victoria Univ. of Wellington, Jan. 1996)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P.R. Halmos,  "Algebraic logic" , Chelsea, reprint  (1962)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  L. Henkin,  J.D. Monk,  A. Tarski,  "Cylindric algebras I–II}" , North-Holland  (1971–1985)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  B. Jónsson,  A. Tarski,  "Boolean algebras with operators, I"  ''Amer. J. Math.'' , '''73'''  (1951)  pp. 891–939</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  B. Jónsson,  A. Tarski,  "Boolean algebras with operators, II"  ''Amer. J. Math.'' , '''74'''  (1952)  pp. 127–162</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  B. Jónsson,  "Varieties of relation algebras"  ''Algebra Universalis'' , '''15'''  (1982)  pp. 273–298</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  B. Jónsson,  "A survey of Boolean algebras with operators" , ''Algebras and Order (Montreal, PQ, 1991)'' , ''NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci.'' , '''389''' , Kluwer Acad. Publ.  (1993)  pp. 239–286</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  J.C.C. Mckinsey,  A. Tarski,  "The algebra of topology"  ''Ann. of Math.'' , '''45'''  (1944)  pp. 141–191</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Goldblatt,  "Varieties of complex algebras"  ''Ann. Pure and Applied Logic'' , '''44'''  (1989)  pp. 173–242</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Goldblatt,  "Mathematics of modality" , ''Lecture Notes'' , '''43''' , Center for the Study of Language and Information, Stanford Univ.  (1993)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R. Goldblatt,  "Elementary generation and canonicity for varieties of Boolean algebras with operators"  ''Algebra Universalis'' , '''34'''  (1995)  pp. 551–607</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Goldblatt,  "Algebraic polymodal logic"  H. Andréka (ed.)  etAAsal. (ed.) , ''Handbook of Algebraic Logic'' , Kluwer Acad. Publ.  (to appear)  (Res. Rep. 96–175, Math. Dept. Victoria Univ. of Wellington, Jan. 1996)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P.R. Halmos,  "Algebraic logic" , Chelsea, reprint  (1962)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  L. Henkin,  J.D. Monk,  A. Tarski,  "Cylindric algebras I–II}" , North-Holland  (1971–1985)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  B. Jónsson,  A. Tarski,  "Boolean algebras with operators, I"  ''Amer. J. Math.'' , '''73'''  (1951)  pp. 891–939</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  B. Jónsson,  A. Tarski,  "Boolean algebras with operators, II"  ''Amer. J. Math.'' , '''74'''  (1952)  pp. 127–162</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  B. Jónsson,  "Varieties of relation algebras"  ''Algebra Universalis'' , '''15'''  (1982)  pp. 273–298</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  B. Jónsson,  "A survey of Boolean algebras with operators" , ''Algebras and Order (Montreal, PQ, 1991)'' , ''NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci.'' , '''389''' , Kluwer Acad. Publ.  (1993)  pp. 239–286</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  J.C.C. Mckinsey,  A. Tarski,  "The algebra of topology"  ''Ann. of Math.'' , '''45'''  (1944)  pp. 141–191</TD></TR></table>

Latest revision as of 19:12, 11 December 2020


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

[a1] R. Goldblatt, "Varieties of complex algebras" Ann. Pure and Applied Logic , 44 (1989) pp. 173–242
[a2] R. Goldblatt, "Mathematics of modality" , Lecture Notes , 43 , Center for the Study of Language and Information, Stanford Univ. (1993)
[a3] R. Goldblatt, "Elementary generation and canonicity for varieties of Boolean algebras with operators" Algebra Universalis , 34 (1995) pp. 551–607
[a4] R. Goldblatt, "Algebraic polymodal logic" H. Andréka (ed.) etAAsal. (ed.) , Handbook of Algebraic Logic , Kluwer Acad. Publ. (to appear) (Res. Rep. 96–175, Math. Dept. Victoria Univ. of Wellington, Jan. 1996)
[a5] P.R. Halmos, "Algebraic logic" , Chelsea, reprint (1962)
[a6] L. Henkin, J.D. Monk, A. Tarski, "Cylindric algebras I–II}" , North-Holland (1971–1985)
[a7] B. Jónsson, A. Tarski, "Boolean algebras with operators, I" Amer. J. Math. , 73 (1951) pp. 891–939
[a8] B. Jónsson, A. Tarski, "Boolean algebras with operators, II" Amer. J. Math. , 74 (1952) pp. 127–162
[a9] B. Jónsson, "Varieties of relation algebras" Algebra Universalis , 15 (1982) pp. 273–298
[a10] B. Jónsson, "A survey of Boolean algebras with operators" , Algebras and Order (Montreal, PQ, 1991) , NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci. , 389 , Kluwer Acad. Publ. (1993) pp. 239–286
[a11] J.C.C. Mckinsey, A. Tarski, "The algebra of topology" Ann. of Math. , 45 (1944) pp. 141–191
How to Cite This Entry:
Boolean algebra with operators. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Boolean_algebra_with_operators&oldid=16043
This article was adapted from an original article by R. Goldblatt (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article