Pseudo-Boolean algebra

A lattice containing a least element 0 and such that for any two elements of there exists a largest element, denoted by , in the set , where is the greatest lower bound of and . The element is called the pseudo-complement of relative to , or the implication from to . Every pseudo-Boolean algebra is a distributive lattice with largest element 1 (every element 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 ; 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 with a constant 0 and binary operators , can be specified by a certain system of identities.

A congruence of a pseudo-Boolean algebra (cf. Congruence (in algebra)) is completely determined by the equivalence class containing 1, i.e. by the set

(1)

according to the formula

(2)

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

Conversely, every non-empty filter of an arbitrary pseudo-Boolean algebra defines by (2) a congruence on the algebra for which the equivalence class of 1 coincides with the given filter .

In a pseudo-Boolean algebra there also holds the infinite distributive law

(3)

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

Complete pseudo-Boolean algebras (i.e. complete lattices satisfying (3)) may be considered as algebras with a constant , a binary operation and an "infinitary" operation . By this approach one defines for complete pseudo-Boolean algebras concepts such as a homomorphism, a congruence and a subalgebra. Thus, a congruence must satisfy the condition: If and are two subsets of such that for each one has , then . The class of complete pseudo-Boolean algebras, regarded as algebras , can be specified by a system of identities, involving . 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 is a multiplicative closure operator on a complete pseudo-Boolean algebra , i.e. a function such that

then the relation

(4)

is a congruence on the algebra , and the set with the order induced from is a complete pseudo-Boolean algebra which is isomorphic to the quotient algebra . Conversely, an arbitrary congruence determines, by the formula

(5)

a multiplicative closure operator . The mappings and defined by (4) and (5) are mutually inverse.

Examples of pseudo-Boolean algebras.

1) For any set , the set , ordered by inclusion , is a complete pseudo-Boolean algebra. Its subalgebras are exactly the topologies on .

2) If a function on a complete pseudo-Boolean algebra satisfies the conditions

(6)

then the set , with the induced order relation, is a subalgebra of the algebra . Every subalgebra can be obtained in this way from a unique function satisfying (6), namely

Functions satisfying (6) are called interior operators.

3) If one defines on the set of all formulas of the language of intuitionistic propositional calculus the relation by: if and only if is derivable in this calculus, and forms the quotient by the equivalence relation , 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 above is usually written as ). The "complete pseudo-Boolean algebras" referred to above are called frames or locales (see Locale). Note that the binary operation 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)