The Heyting algebra reference article from the English Wikipedia on 24-Apr-2004
(provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Heyting algebra

Have you considered sponsoring a child
In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. Heyting algebras arise as models of intuitionistic logic, a logic in which the law of excluded middle does not in general hold. Complete Heyting algebras are a central object of study in pointless topology.

Table of contents
1 Formal definitions
2 Properties
3 Examples
4 References

Formal definitions

A Heyting algebra H is a bounded lattice such that for all a and b in H there is a greatest element x of H such that a ^ x ≤ b. This element is called the relative pseudo-complement of a with respect to b, and is denoted a=>b (or a→b).

An equivalent definition can be given by considering the mappings fa: H→H defined by fa(x) = a ^ x, for some fixed a in H. A bounded lattice H is a Heyting algebra iff all mappings fa are the lower adjoint of a monotone Galois connection. In this case the respective upper adjoints ga are given by ga(x) = a=>x, where => is defined as above.

A complete Heyting algebra is a Heyting algebra that is a complete lattice.

In any Heyting algebra, one can define the pseudo-complement ¬x of some element x by setting ¬x=x=>0, where 0 is the least element of the Heyting algebra.

An element x of a Heyting algebra is called regular if x = ¬¬x.

Properties

Heyting algebras are always distributive. This is sometimes stated as an axiom, but in fact it follows from the existence of relative pseudo-complements. The reason is that, being the lower adjoint of a Galois connection, ^ preserves all existing suprema. Distributivity in turn is just the preservation of binary suprema by ^.

Furthermore, by a similar argument, the following infinite distributive law holds in any complete Heyting algebra:

x^ VY = V{x^y :  y in Y},

for any element x in H and any subset Y of H.

Not every Heyting algebra satisfies the two De Morgan laws. However, the following statements are equivalent for all Heyting algebras H:

  1. H satisfies both De Morgan laws.
  2. ¬(x ^ y) = ¬x v ¬y, for all x, y in H.
  3. ¬x v ¬¬x = 1, for all x in H.
  4. ¬¬(x v y) = ¬¬x v ¬¬y, for all x, y in H.

The pseudo-complement of an element x of H is the supremum of the set {y : y ^ x=0} and it belongs to this set (i.e. x ^ ¬x=0 holds).

Boolean algebras are exactly those Heyting algebras in which x = ¬¬x for all x, or, equivalently, in which x v ¬x = 1 for all x. In this case, the element a => b is equal to ¬a v b.

In any Heyting algebra, the least and greatest elements 0 and 1 are regular. In addition, the regular elements of any Heyting algebra constitute a Boolean algebra.

Examples

References