Absorption law

From Wikipedia, the free encyclopedia

In algebra, the absorption law is an identity linking a pair of binary operations.

Any two binary operations, say $ and %, are subject to the absorption law if:

a $ (a % b) = a % (a $ b) = a.

The operations $ and % are said to form a dual pair.

Let there be some set closed under two binary operations. If those operations are commutative, associative, and satisfy the absorption law, the resulting abstract algebra is a lattice, in which case the two operations are sometimes called meet, join; other possibilities include and,or. Since commutativity and associativity are often properties of other algebraic structures (for example, addition and multiplication of real numbers), absorption is the defining property of a lattice. Since Boolean algebras and Heyting algebras are lattices, they too obey the absorption law.

Since classical logic is a model of Boolean algebra, and the same is true of intuitionistic logic and Heyting algebras, the absorption law holds for operations and , denoting OR and AND, respectively. Hence:

where = is understood to be logical equivalence over formulae.

The absorption law does not hold for relevance logics, linear logics, and substructural logics. In the last case, there is no one-to-one correspondence between the free variables of the defining pair of identities.