Namespaces
Variants
Actions

Difference between revisions of "Pseudo-Boolean algebra"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A [[Lattice|lattice]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756101.png" /> containing a least element 0 and such that for any two elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756102.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756103.png" /> there exists a largest element, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756104.png" />, in the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756105.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756106.png" /> is the greatest lower bound of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756107.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756108.png" />. The element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p0756109.png" /> is called the pseudo-complement of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561010.png" /> relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561011.png" />, or the implication from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561012.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561013.png" />. Every pseudo-Boolean algebra is a [[Distributive lattice|distributive lattice]] with largest element 1 (every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561014.png" /> is such).
+
<!--
 +
p0756101.png
 +
$#A+1 = 86 n = 0
 +
$#C+1 = 86 : ~/encyclopedia/old_files/data/P075/P.0705610 Pseudo\AAhBoolean algebra
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
A [[Lattice|lattice]]  $  \mathbf L = ( L , \leq  ) $
 +
containing a least element 0 and such that for any two elements $  a , b $
 +
of $  L $
 +
there exists a largest element, denoted by $  a \supset b $,  
 +
in the set $  \{ {x \in L } : {a \wedge x \leq  b } \} $,  
 +
where $  a \wedge x $
 +
is the greatest lower bound of $  a $
 +
and $  x $.  
 +
The element $  a \supset b $
 +
is called the pseudo-complement of $  a $
 +
relative to $  b $,  
 +
or the implication from $  a $
 +
to $  b $.  
 +
Every pseudo-Boolean algebra is a [[Distributive lattice|distributive lattice]] with largest element 1 (every element $  a \supset a $
 +
is such).
  
 
Pseudo-Boolean algebras serve as algebraic models of Heyting's [[Intuitionistic propositional calculus|intuitionistic propositional calculus]] and characterize it in the same way that Boolean algebras characterize classical propositional calculus (cf. [[Boolean algebra|Boolean algebra]]).
 
Pseudo-Boolean algebras serve as algebraic models of Heyting's [[Intuitionistic propositional calculus|intuitionistic propositional calculus]] and characterize it in the same way that Boolean algebras characterize classical propositional calculus (cf. [[Boolean algebra|Boolean algebra]]).
Line 5: Line 31:
 
Pseudo-Boolean algebras are also called Heyting algebras.
 
Pseudo-Boolean algebras are also called Heyting algebras.
  
Relatively pseudo-complemented lattices were considered already in 1919 by T. Skolem [[#References|[1]]], but without relation to logic. The first such relation involved in the study of lattices dual to pseudo-Boolean algebras (i.e. lattices obtained from pseudo-Boolean algebras by reversing the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561015.png" />; cf. [[#References|[2]]]). Such lattices were called Brouwer algebras (see [[Brouwer lattice|Brouwer lattice]]). Later, the term  "Brouwer algebra"  was also used for pseudo-Boolean algebras.
+
Relatively pseudo-complemented lattices were considered already in 1919 by T. Skolem [[#References|[1]]], but without relation to logic. The first such relation involved in the study of lattices dual to pseudo-Boolean algebras (i.e. lattices obtained from pseudo-Boolean algebras by reversing the relation $  \leq  $;  
 +
cf. [[#References|[2]]]). Such lattices were called Brouwer algebras (see [[Brouwer lattice|Brouwer lattice]]). Later, the term  "Brouwer algebra"  was also used for pseudo-Boolean algebras.
  
The class of pseudo-Boolean algebras, regarded as universal algebras <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561016.png" /> with a constant 0 and binary operators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561017.png" />, can be specified by a certain system of identities.
+
The class of pseudo-Boolean algebras, regarded as universal algebras $  ( L ;  0 , \wedge , \lor , \supset ) $
 +
with a constant 0 and binary operators $  \wedge , \lor , \supset $,  
 +
can be specified by a certain system of identities.
  
A congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561018.png" /> of a pseudo-Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561019.png" /> (cf. [[Congruence (in algebra)|Congruence (in algebra)]]) is completely determined by the equivalence class containing 1, i.e. by the set
+
A congruence $  R \subseteq L \times L $
 +
of a pseudo-Boolean algebra $  ( L ;  0 , \wedge , \lor , \supset ) $(
 +
cf. [[Congruence (in algebra)|Congruence (in algebra)]]) is completely determined by the equivalence class containing 1, i.e. by the set
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\nabla  = \{ {x \in L } : {\langle  x , 1 \rangle \in R } \}
 +
,
 +
$$
  
 
according to the formula
 
according to the formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561021.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
\langle  x , y \rangle \in R  \iff  ( x \supset y \in \nabla  \textrm{ and }  y \supset x
 +
\in \nabla ) .
 +
$$
  
 
The set (1) is a [[Filter|filter]], i.e. it satisfies the conditions
 
The set (1) is a [[Filter|filter]], i.e. it satisfies the conditions
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561022.png" /></td> </tr></table>
+
$$
 +
( x \in \nabla  \textrm{ and }  x \leq  y )  \Rightarrow  y \in \nabla ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561023.png" /></td> </tr></table>
+
$$
 +
( x \in \nabla  \textrm{ and }  y \in \nabla )  \Rightarrow  x \wedge y \in \nabla .
 +
$$
  
Conversely, every non-empty filter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561024.png" /> of an arbitrary pseudo-Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561025.png" /> defines by (2) a congruence on the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561026.png" /> for which the equivalence class of 1 coincides with the given filter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561027.png" />.
+
Conversely, every non-empty filter $  \nabla $
 +
of an arbitrary pseudo-Boolean algebra $  L $
 +
defines by (2) a congruence on the algebra $  ( L;  0, \wedge , \lor , \supset ) $
 +
for which the equivalence class of 1 coincides with the given filter $  \nabla $.
  
In a pseudo-Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561028.png" /> there also holds the infinite distributive law
+
In a pseudo-Boolean algebra $  ( L , \leq  ) $
 +
there also holds the infinite distributive law
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561029.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
a \wedge \sup  X  = \
 +
\sup \{ {a \wedge x } : {x \in X } \}
 +
$$
  
for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561030.png" /> and any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561031.png" /> having a least upper bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561032.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561033.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561034.png" /> is a complete lattice, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561035.png" /> exists for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561036.png" />, then, conversely, the truth of (3) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561037.png" /> implies that it is a pseudo-Boolean algebra. The operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561038.png" /> is then defined by
+
for any $  a \in L $
 +
and any set $  X \subseteq L $
 +
having a least upper bound $  \sup  X $
 +
in $  L $.  
 +
If $  ( L , \leq  ) $
 +
is a complete lattice, i.e. $  \sup X $
 +
exists for any $  X \subseteq L $,  
 +
then, conversely, the truth of (3) in $  L $
 +
implies that it is a pseudo-Boolean algebra. The operation $  \supset $
 +
is then defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561039.png" /></td> </tr></table>
+
$$
 +
a \supset b  = \sup \{ {x \in L } : {a \wedge x \leq  b } \}
 +
.
 +
$$
  
Complete pseudo-Boolean algebras (i.e. complete lattices satisfying (3)) may be considered as algebras <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561040.png" /> with a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561041.png" />, a binary operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561042.png" /> and an  "infinitary"  operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561043.png" />. By this approach one defines for complete pseudo-Boolean algebras concepts such as a homomorphism, a congruence and a subalgebra. Thus, a congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561044.png" /> must satisfy the condition: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561046.png" /> are two subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561047.png" /> such that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561048.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561049.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561050.png" />. The class of complete pseudo-Boolean algebras, regarded as algebras <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561051.png" />, can be specified by a system of identities, involving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561052.png" />. Therefore it is closed under taking subalgebras, quotient algebras and direct products of families of algebras. There exist free algebras with an arbitrary set of generators in the class of complete algebras.
+
Complete pseudo-Boolean algebras (i.e. complete lattices satisfying (3)) may be considered as algebras $  ( L ;  1 , \wedge , \sup ) $
 +
with a constant $  1 $,  
 +
a binary operation $  \wedge : L \times L \rightarrow L $
 +
and an  "infinitary"  operation $  \sup :  \{ {X } : {X \subseteq L } \} \rightarrow L $.  
 +
By this approach one defines for complete pseudo-Boolean algebras concepts such as a homomorphism, a congruence and a subalgebra. Thus, a congruence $  R \subseteq L \times L $
 +
must satisfy the condition: If $  X = \{ {x } : {i \in I } \} $
 +
and $  Y = \{ {y } : {i \in I } \} $
 +
are two subsets of $  L $
 +
such that for each $  i \in I $
 +
one has $  \langle  x _ {i} , y _ {i} \rangle \in R $,  
 +
then $  \langle  \sup  X , \sup  Y \rangle \in R $.  
 +
The class of complete pseudo-Boolean algebras, regarded as algebras $  \langle  L ;  1 , \wedge , \sup \rangle $,  
 +
can be specified by a system of identities, involving $  1 , \wedge , \sup $.  
 +
Therefore it is closed under taking subalgebras, quotient algebras and direct products of families of algebras. There exist free algebras with an arbitrary set of generators in the class of complete algebras.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561053.png" /> is a multiplicative closure operator on a complete pseudo-Boolean algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561054.png" />, i.e. a function such that
+
If $  J : L \rightarrow L $
 +
is a multiplicative closure operator on a complete pseudo-Boolean algebra $  \mathbf L = ( L , \leq  ) $,  
 +
i.e. a function such that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561055.png" /></td> </tr></table>
+
$$
 +
x  \leq  J ( x)  = J ( J ( x) ) \ \
 +
\textrm{ and } \ \
 +
J ( x \wedge y )  = J ( x) \wedge J ( y) ,
 +
$$
  
 
then the relation
 
then the relation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561056.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
R _ {J}  = \
 +
\{ {\langle  x , y \rangle \in L \times L } : {J( x) = J ( y) } \}
 +
$$
  
is a congruence on the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561057.png" />, and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561058.png" /> with the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561059.png" /> induced from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561060.png" /> is a complete pseudo-Boolean algebra which is isomorphic to the quotient algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561061.png" />. Conversely, an arbitrary congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561062.png" /> determines, by the formula
+
is a congruence on the algebra $  \mathbf A = ( L ;  1 , \wedge , \sup ) $,  
 +
and the set $  J L = \{ {x \in L } : {J ( x) = x } \} $
 +
with the order $  \leq  \mid  _ {JL} $
 +
induced from $  \mathbf L $
 +
is a complete pseudo-Boolean algebra which is isomorphic to the quotient algebra $  \mathbf A / R _ {J} $.  
 +
Conversely, an arbitrary congruence $  \mathbf R $
 +
determines, by the formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561063.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{5 }
 +
J _ {R} ( x) =  \sup \{ {y \in L } : {\langle  y , x \rangle \in R } \}
 +
,
 +
$$
  
a multiplicative closure operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561064.png" />. The mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561065.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561066.png" /> defined by (4) and (5) are mutually inverse.
+
a multiplicative closure operator $  J _ {R} : L \rightarrow L $.  
 +
The mappings $  J \mapsto R _ {J} $
 +
and $  R \mapsto J _ {R} $
 +
defined by (4) and (5) are mutually inverse.
  
 
===Examples of pseudo-Boolean algebras.===
 
===Examples of pseudo-Boolean algebras.===
  
 +
1) For any set  $  U $,
 +
the set  $  \{ {X } : {X \subseteq U } \} $,
 +
ordered by inclusion  $  \subseteq $,
 +
is a complete pseudo-Boolean algebra. Its subalgebras are exactly the topologies on  $  U $.
  
1) For any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561067.png" />, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561068.png" />, ordered by inclusion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561069.png" />, is a complete pseudo-Boolean algebra. Its subalgebras are exactly the topologies on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561070.png" />.
+
2) If a function  $  I : L \rightarrow L $
 +
on a complete pseudo-Boolean algebra satisfies the conditions
  
2) If a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561071.png" /> on a complete pseudo-Boolean algebra satisfies the conditions
+
$$ \tag{6 }
 +
I ( I ( x) = I ( x)  \leq  x ,\ \
 +
I ( x \wedge y )  = I ( x) \wedge I ( y) ,\ \
 +
I( 1)  = 1,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561072.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
then the set  $  I L = \{ {X \in L } : {I x = x } \} $,
 +
with the induced order relation, is a subalgebra of the algebra  $  ( L ; 1 , \wedge , \sup ) $.  
 +
Every subalgebra  $  A \subseteq L $
 +
can be obtained in this way from a unique function  $  I $
 +
satisfying (6), namely
  
then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561073.png" />, with the induced order relation, is a subalgebra of the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561074.png" />. Every subalgebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561075.png" /> can be obtained in this way from a unique function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561076.png" /> satisfying (6), namely
+
$$
 +
I ( x)  = \sup \{ {a \in A } : {a \leq  x } \}
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561077.png" /></td> </tr></table>
+
Functions  $  I $
 +
satisfying (6) are called interior operators.
  
Functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561078.png" /> satisfying (6) are called interior operators.
+
3) If one defines on the set $  \Phi $
 
+
of all formulas of the language of intuitionistic propositional calculus the relation $  x \leq  y $
3) If one defines on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561079.png" /> of all formulas of the language of intuitionistic propositional calculus the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561080.png" /> by: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561081.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561082.png" /> is derivable in this calculus, and forms the quotient by the equivalence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561083.png" />, then one obtains a free pseudo-Boolean algebra.
+
by: $  A \leq  B $
 +
if and only if $  A \supset B $
 +
is derivable in this calculus, and forms the quotient by the equivalence relation $  x \leq  y \& y \leq  x $,  
 +
then one obtains a free pseudo-Boolean algebra.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  T. Skolem,  "Untersuchungen über die Axiome des Klassenkalküls und über Produktations- und Summationsprobleme, welche gewisse Klassen von Aussagen betreffen" , ''Selected works in logic'' , Universitetsforlaget Oslo  (1970)  pp. 67–101</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J.C.C. McKinsey,  A. Tarski,  "On closed elements in closure algebras"  ''Ann. of Math.'' , '''47'''  (1946)  pp. 122–162</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  E. Rasiowa,  R. Sikorski,  "The mathematics of metamathematics" , Polska Akad. Nauk  (1963)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.G. Dragalin,  "Mathematical intuitionism: an introduction to proof theory" , Amer. Math. Soc.  (1988)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  M.P. Fourman,  D.S. Scott,  "Sheaves and logic"  M.P. Fourman (ed.)  C.J. Mulvey (ed.)  D.S. Scott (ed.) , ''Applications of sheaves'' , ''Lect. notes in math.'' , '''753''' , Springer  (1979)  pp. 302–401</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  T. Skolem,  "Untersuchungen über die Axiome des Klassenkalküls und über Produktations- und Summationsprobleme, welche gewisse Klassen von Aussagen betreffen" , ''Selected works in logic'' , Universitetsforlaget Oslo  (1970)  pp. 67–101</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J.C.C. McKinsey,  A. Tarski,  "On closed elements in closure algebras"  ''Ann. of Math.'' , '''47'''  (1946)  pp. 122–162</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  E. Rasiowa,  R. Sikorski,  "The mathematics of metamathematics" , Polska Akad. Nauk  (1963)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.G. Dragalin,  "Mathematical intuitionism: an introduction to proof theory" , Amer. Math. Soc.  (1988)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  M.P. Fourman,  D.S. Scott,  "Sheaves and logic"  M.P. Fourman (ed.)  C.J. Mulvey (ed.)  D.S. Scott (ed.) , ''Applications of sheaves'' , ''Lect. notes in math.'' , '''753''' , Springer  (1979)  pp. 302–401</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
In the modern English literature, pseudo-Boolean algebras are most commonly called Heyting algebras (and the binary operation denoted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561084.png" /> above is usually written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561085.png" />). The  "complete pseudo-Boolean algebras"  referred to above are called frames or locales (see [[Locale|Locale]]). Note that the binary operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075610/p07561086.png" /> is not taken as a primitive operation in the algebraic theory of frames; thus subframes and frame congruences are not, in general, Heyting subalgebras or Heyting algebra congruences (nor are the free frames mentioned above free as Heyting algebras). For free Heyting algebras, see [[#References|[a5]]].
+
In the modern English literature, pseudo-Boolean algebras are most commonly called Heyting algebras (and the binary operation denoted $  \supset $
 +
above is usually written as $  \Rightarrow $).  
 +
The  "complete pseudo-Boolean algebras"  referred to above are called frames or locales (see [[Locale|Locale]]). Note that the binary operation $  \supset $
 +
is not taken as a primitive operation in the algebraic theory of frames; thus subframes and frame congruences are not, in general, Heyting subalgebras or Heyting algebra congruences (nor are the free frames mentioned above free as Heyting algebras). For free Heyting algebras, see [[#References|[a5]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Balbes,  P. Dwinger,  "Distributive lattices" , Univ. Missouri Press  (1974)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.J. Freyd,  "Aspects of topoi"  ''Bull. Austral. Math. Soc.'' , '''7'''  (1972)  pp. 1–76</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P.T. Johnstone,  "Stone spaces" , Cambridge Univ. Press  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Rasiowa,  "An algebraic approach to non-classical logics" , North-Holland  (1974)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Urquhart,  "Free Heyting algebras"  ''Algebra Universalis'' , '''3'''  (1973)  pp. 94–97</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  S. Vickers,  "Topology via logic" , Cambridge Univ. Press  (1989)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Balbes,  P. Dwinger,  "Distributive lattices" , Univ. Missouri Press  (1974)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.J. Freyd,  "Aspects of topoi"  ''Bull. Austral. Math. Soc.'' , '''7'''  (1972)  pp. 1–76</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P.T. Johnstone,  "Stone spaces" , Cambridge Univ. Press  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Rasiowa,  "An algebraic approach to non-classical logics" , North-Holland  (1974)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Urquhart,  "Free Heyting algebras"  ''Algebra Universalis'' , '''3'''  (1973)  pp. 94–97</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  S. Vickers,  "Topology via logic" , Cambridge Univ. Press  (1989)</TD></TR></table>

Latest revision as of 08:08, 6 June 2020


A lattice $ \mathbf L = ( L , \leq ) $ containing a least element 0 and such that for any two elements $ a , b $ of $ L $ there exists a largest element, denoted by $ a \supset b $, in the set $ \{ {x \in L } : {a \wedge x \leq b } \} $, where $ a \wedge x $ is the greatest lower bound of $ a $ and $ x $. The element $ a \supset b $ is called the pseudo-complement of $ a $ relative to $ b $, or the implication from $ a $ to $ b $. Every pseudo-Boolean algebra is a distributive lattice with largest element 1 (every element $ a \supset a $ is such).

Pseudo-Boolean algebras serve as algebraic models of Heyting's intuitionistic propositional calculus and characterize it in the same way that Boolean algebras characterize classical propositional calculus (cf. Boolean algebra).

Pseudo-Boolean algebras are also called Heyting algebras.

Relatively pseudo-complemented lattices were considered already in 1919 by T. Skolem [1], but without relation to logic. The first such relation involved in the study of lattices dual to pseudo-Boolean algebras (i.e. lattices obtained from pseudo-Boolean algebras by reversing the relation $ \leq $; cf. [2]). Such lattices were called Brouwer algebras (see Brouwer lattice). Later, the term "Brouwer algebra" was also used for pseudo-Boolean algebras.

The class of pseudo-Boolean algebras, regarded as universal algebras $ ( L ; 0 , \wedge , \lor , \supset ) $ with a constant 0 and binary operators $ \wedge , \lor , \supset $, can be specified by a certain system of identities.

A congruence $ R \subseteq L \times L $ of a pseudo-Boolean algebra $ ( L ; 0 , \wedge , \lor , \supset ) $( cf. Congruence (in algebra)) is completely determined by the equivalence class containing 1, i.e. by the set

$$ \tag{1 } \nabla = \{ {x \in L } : {\langle x , 1 \rangle \in R } \} , $$

according to the formula

$$ \tag{2 } \langle x , y \rangle \in R \iff ( x \supset y \in \nabla \textrm{ and } y \supset x \in \nabla ) . $$

The set (1) is a filter, i.e. it satisfies the conditions

$$ ( x \in \nabla \textrm{ and } x \leq y ) \Rightarrow y \in \nabla , $$

$$ ( x \in \nabla \textrm{ and } y \in \nabla ) \Rightarrow x \wedge y \in \nabla . $$

Conversely, every non-empty filter $ \nabla $ of an arbitrary pseudo-Boolean algebra $ L $ defines by (2) a congruence on the algebra $ ( L; 0, \wedge , \lor , \supset ) $ for which the equivalence class of 1 coincides with the given filter $ \nabla $.

In a pseudo-Boolean algebra $ ( L , \leq ) $ there also holds the infinite distributive law

$$ \tag{3 } a \wedge \sup X = \ \sup \{ {a \wedge x } : {x \in X } \} $$

for any $ a \in L $ and any set $ X \subseteq L $ having a least upper bound $ \sup X $ in $ L $. If $ ( L , \leq ) $ is a complete lattice, i.e. $ \sup X $ exists for any $ X \subseteq L $, then, conversely, the truth of (3) in $ L $ implies that it is a pseudo-Boolean algebra. The operation $ \supset $ is then defined by

$$ a \supset b = \sup \{ {x \in L } : {a \wedge x \leq b } \} . $$

Complete pseudo-Boolean algebras (i.e. complete lattices satisfying (3)) may be considered as algebras $ ( L ; 1 , \wedge , \sup ) $ with a constant $ 1 $, a binary operation $ \wedge : L \times L \rightarrow L $ and an "infinitary" operation $ \sup : \{ {X } : {X \subseteq L } \} \rightarrow L $. By this approach one defines for complete pseudo-Boolean algebras concepts such as a homomorphism, a congruence and a subalgebra. Thus, a congruence $ R \subseteq L \times L $ must satisfy the condition: If $ X = \{ {x } : {i \in I } \} $ and $ Y = \{ {y } : {i \in I } \} $ are two subsets of $ L $ such that for each $ i \in I $ one has $ \langle x _ {i} , y _ {i} \rangle \in R $, then $ \langle \sup X , \sup Y \rangle \in R $. The class of complete pseudo-Boolean algebras, regarded as algebras $ \langle L ; 1 , \wedge , \sup \rangle $, can be specified by a system of identities, involving $ 1 , \wedge , \sup $. Therefore it is closed under taking subalgebras, quotient algebras and direct products of families of algebras. There exist free algebras with an arbitrary set of generators in the class of complete algebras.

If $ J : L \rightarrow L $ is a multiplicative closure operator on a complete pseudo-Boolean algebra $ \mathbf L = ( L , \leq ) $, i.e. a function such that

$$ x \leq J ( x) = J ( J ( x) ) \ \ \textrm{ and } \ \ J ( x \wedge y ) = J ( x) \wedge J ( y) , $$

then the relation

$$ \tag{4 } R _ {J} = \ \{ {\langle x , y \rangle \in L \times L } : {J( x) = J ( y) } \} $$

is a congruence on the algebra $ \mathbf A = ( L ; 1 , \wedge , \sup ) $, and the set $ J L = \{ {x \in L } : {J ( x) = x } \} $ with the order $ \leq \mid _ {JL} $ induced from $ \mathbf L $ is a complete pseudo-Boolean algebra which is isomorphic to the quotient algebra $ \mathbf A / R _ {J} $. Conversely, an arbitrary congruence $ \mathbf R $ determines, by the formula

$$ \tag{5 } J _ {R} ( x) = \sup \{ {y \in L } : {\langle y , x \rangle \in R } \} , $$

a multiplicative closure operator $ J _ {R} : L \rightarrow L $. The mappings $ J \mapsto R _ {J} $ and $ R \mapsto J _ {R} $ defined by (4) and (5) are mutually inverse.

Examples of pseudo-Boolean algebras.

1) For any set $ U $, the set $ \{ {X } : {X \subseteq U } \} $, ordered by inclusion $ \subseteq $, is a complete pseudo-Boolean algebra. Its subalgebras are exactly the topologies on $ U $.

2) If a function $ I : L \rightarrow L $ on a complete pseudo-Boolean algebra satisfies the conditions

$$ \tag{6 } I ( I ( x) ) = I ( x) \leq x ,\ \ I ( x \wedge y ) = I ( x) \wedge I ( y) ,\ \ I( 1) = 1, $$

then the set $ I L = \{ {X \in L } : {I x = x } \} $, with the induced order relation, is a subalgebra of the algebra $ ( L ; 1 , \wedge , \sup ) $. Every subalgebra $ A \subseteq L $ can be obtained in this way from a unique function $ I $ satisfying (6), namely

$$ I ( x) = \sup \{ {a \in A } : {a \leq x } \} . $$

Functions $ I $ satisfying (6) are called interior operators.

3) If one defines on the set $ \Phi $ of all formulas of the language of intuitionistic propositional calculus the relation $ x \leq y $ by: $ A \leq B $ if and only if $ A \supset B $ is derivable in this calculus, and forms the quotient by the equivalence relation $ x \leq y \& y \leq x $, then one obtains a free pseudo-Boolean algebra.

References

[1] T. Skolem, "Untersuchungen über die Axiome des Klassenkalküls und über Produktations- und Summationsprobleme, welche gewisse Klassen von Aussagen betreffen" , Selected works in logic , Universitetsforlaget Oslo (1970) pp. 67–101
[2] J.C.C. McKinsey, A. Tarski, "On closed elements in closure algebras" Ann. of Math. , 47 (1946) pp. 122–162
[3] E. Rasiowa, R. Sikorski, "The mathematics of metamathematics" , Polska Akad. Nauk (1963)
[4] A.G. Dragalin, "Mathematical intuitionism: an introduction to proof theory" , Amer. Math. Soc. (1988) (Translated from Russian)
[5] M.P. Fourman, D.S. Scott, "Sheaves and logic" M.P. Fourman (ed.) C.J. Mulvey (ed.) D.S. Scott (ed.) , Applications of sheaves , Lect. notes in math. , 753 , Springer (1979) pp. 302–401

Comments

In the modern English literature, pseudo-Boolean algebras are most commonly called Heyting algebras (and the binary operation denoted $ \supset $ above is usually written as $ \Rightarrow $). The "complete pseudo-Boolean algebras" referred to above are called frames or locales (see Locale). Note that the binary operation $ \supset $ is not taken as a primitive operation in the algebraic theory of frames; thus subframes and frame congruences are not, in general, Heyting subalgebras or Heyting algebra congruences (nor are the free frames mentioned above free as Heyting algebras). For free Heyting algebras, see [a5].

References

[a1] R. Balbes, P. Dwinger, "Distributive lattices" , Univ. Missouri Press (1974)
[a2] P.J. Freyd, "Aspects of topoi" Bull. Austral. Math. Soc. , 7 (1972) pp. 1–76
[a3] P.T. Johnstone, "Stone spaces" , Cambridge Univ. Press (1982)
[a4] H. Rasiowa, "An algebraic approach to non-classical logics" , North-Holland (1974)
[a5] A. Urquhart, "Free Heyting algebras" Algebra Universalis , 3 (1973) pp. 94–97
[a6] S. Vickers, "Topology via logic" , Cambridge Univ. Press (1989)
How to Cite This Entry:
Pseudo-Boolean algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pseudo-Boolean_algebra&oldid=14887
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article