Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Home > Heyting algebra
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.1 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
.
This element is called the relative pseudo-complement of a with respect to b, and is denoted (or ).
An equivalent definition can be given by considering the mappings
defined by , for some fixed a in H. A bounded lattice H is a Heyting algebra iff all mappings are the lower adjoint of a monotone Galois connection. In this case the respective upper adjoints are given by , 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 of some element x by setting , where 0 is the least element of the Heyting algebra.
An element x of a Heyting algebra is called regular if
.
An element x is regular if and only if for some element y of the Heyting algebra.
2 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:
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:
- H satisfies both De Morgan laws.
- , for all x, y in H.
- , for all x in H.
- , for all x, y in H.
The pseudo-complement of an element x of H is the supremum of the set
and it belongs to this set (i.e.
holds).
Boolean algebras are exactly those Heyting algebras in which
for all x, or, equivalently, in which
for all x. In this case, the element
is equal to .
In any Heyting algebra, the least and greatest elements 0 and 1 are regular.
The regular elements of any Heyting algebra constitute a Boolean algebra.
Unless all elements of the Heyting algebra are regular, this Boolean algebra will not be a sublattice of the Heyting algebra, because its join operation will be different.
3 Examples
- Every totally ordered set that is a bounded lattice is also a Heyting algebra, where and for all a other than 0.
- Every topologyTopology is the study or science of places. It derives its name from the Greek words τοπος meaning place and λογος meaning study, talk. See also earth science, geography, human geography, g provides a complete Heyting algebra in the form of its open setIn topology and related fields of mathematics, a set U is called open if, intuitively speaking, you can "wiggle" or "change" any point x in U by a small amount in any direction and still be inside U. In other words, if x is surrounded only by elements of lattice. In this case, the element is the interiorIn topology, the interior of a set is the union of all open sets contained in it, and contains all interior points. It is the largest open set contained in the original set. The interior of a set S is denoted by int S Int S or, S''o. A set S is an open se of the union of and B, where denotes the complement of the open set A. Not all complete Heyting algebras are of this form. These issues are studied in pointless topology, where complete Heyting algebras are also called frames or locales.
- The Lindenbaum algebra of propositional intuitionistic logic is a Heyting algebra. It is defined to be the set of all propositional logic formulae, ordered via logical entailment: for any two formulae F and G we have iff . At this stage is merely a preorderThis article is about the mathematics concept. For preorder traversal of a tree data structure, see tree traversal. In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered s that induces a partial order which is the desired Heyting algebra.
Read more »