Pseudo-Boolean algebra

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.[edit]

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[edit]

Comments[edit]

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[edit]