View source for Pseudo-Boolean algebra

<!--
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 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  $  \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  $  ( 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)|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|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====
<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====
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====
<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>