Boolean Algebra
Partially ordered set $(X, \le)$ is a relational system, but a special type of it can be studied as a universal algebra called lattice $(X, (\wedge, \vee))$. Most applications of lattice theory are associated with Boolean algebras.
Lattice
Lattice $(X, (\wedge, \vee))$ is an algebra derived from a partially ordered set $(X, \le)$ in which infimum and supremum exist for all two-element subsets, such that operations meet $\wedge$ and join $\vee$ are defined as $a \wedge b := \inf \{a, b\}$ and $a \vee b := \sup \{a, b\}$. Every non-empty finite subset of a lattice has a supremum and infimum. Complete lattice $(X, (\wedge_\alpha, \vee_\alpha))$ is a lattice corresponding to a partially ordered set in which infimum and supremum exist for all subsets; equivalently, a lattice on which any isotone transformation has a fixed point.
The two lattice operations meet $\wedge$ and join $\vee$ satisfy: (1) idempotence, $x ∗ x = x$; (2) commutativity, $x ∗ y = y ∗ x$; (3) associativity, $(x ∗ y) ∗ z = x ∗ (y ∗ z)$; (4) the absorption law, $(x ∗ y) \star x = x$. Here $∗$ represents either operation and $\star$ represents the other operation. Without grouping, meet $\wedge$ takes precedence over join $\vee$. Distributive lattice is a lattice that also satisfies the distributive law: $x ∗ (y \star z) = (x ∗ y) \star (x ∗ z)$; the two instances of this law are equivalent. Completely distributive lattice is a complete lattice that also satisfies the complete distributive law (arbitrary joins distribute over arbitrary meets): for all subsets $A \subset X$, for all doubly index $\{J_i\}_{i \in I}$ on the subset $A = \{x_{i,j} : i \in I, j \in J_i\}$, the following identity holds $\wedge_{i \in I} \vee_{j \in J_i} x_{i,j} = \vee_{f \in \prod_i J_i} \wedge_{i \in I} x_{i,f_i}$; equivalently, a complete lattice imbeddable in a power set by a mapping that preserves arbitrary supremum and infimum.
For example, the power set $\mathcal{P}(X)$ of a set $X$ is a partially ordered set $(\mathcal{P}(X), \subset)$ via the subset relation $\subset$, and any subset $\mathcal{A} \subset \mathcal{P}(X)$ of the power set has infimum $\cap \mathcal{A}$ and supremum $\cup \mathcal{A}$, so it is a complete lattice $(\mathcal{P}(X), (\cap, \cup))$ via the operations intersection $\cap$ and union $\cup$. Moreover, set operations $\cap$ and $\cup$ satisfy the complete distributive law, so the power set lattice $(\mathcal{P}(X), (\cap, \cup))$ is a completely distributive lattice.
Theorem (@Stone1937; @Priestley1970; representation for distributive lattices): Any distributive lattice is isomorphic to a sublattice of a power set lattice.
As a corollary, any distributive lattice has the least element $\bot$ (or $0$, the identity of $\wedge$) and the largest element $\top$ (or $1$, the identity of $\vee$).
Boolean algebra
Boolean algebra, Boolean lattice, or complemented distributive lattice $(X, (\wedge, \vee, \complement), \{\top, \bot\})$ is a distributive lattice $(X, (\wedge, \vee), \{\top, \bot\})$ endowed with a unary operation called complement $\complement$ such that $x \vee \complement x = \top$ and $x \wedge \complement x = \bot$. Alternatively, [@Huntington1933] axiomatizes Boolean algebra $(X, (\lor, \lnot))$ to be a set $X$ with a binary operator $\lor$ and a unary operator $\lnot$ that satisfies: (1) commutativity: $x \lor y = y \lor x$; (2) associativity: $x \lor (y \lor z) = (x \lor y) \lor z$; (3) Huntington axiom: $\lnot (\lnot x \lor y) \lor \lnot (\lnot x \lor \lnot y) = x$. In this case, the two special elements top and bottom can be defined as $\top := x \lor \lnot x$ and $\bot := \lnot \top$. The operator meet can be defined as $x \land y := \lnot (\lnot x \lor \lnot y)$. Boolean laws refers to the common properties of Boolean algebra: idempotence, commutativity, associativity, absorption, distributivity, complementation, identity element, and duality: all these laws still hold if simultaneously exchange $\land$ and $\bot$ with $\lor$ and $\top$.
Figure: Hasse diagrams for Boolean algebras of orders n = 2, 3, 4, and 5.
Boolean algebra is an algebraic system that captures the essence of Mathematical Logic and Axiomatic Set Theory. Boolean algebra abstract the algebra of sets.
Table: Analogous concepts in Boolean algebra, set theory, and mathematical logic.
| algebra | set | logic |
|---|---|---|
| meet $\wedge$ | intersection $\cap$ | conjunction $\land$ |
| join $\vee$ | union $\cup$ | disjunction $\lor$ |
| (complement) | complement $\complement$ | negation $\lnot$ |
| top $\top$ | universe | tautology $1$ |
| bottom $\bot$ | empty set $\emptyset$ | contradiction $0$ |
Theorem (@Stone1936; duality for Boolean algebras): Every Boolean algebra is isomorphic to the algebra of clopen subsets of its Stone space. Every Boolean algebra is isomorphic to a certain field of sets.
A power set lattice $(\mathcal{P}(X), (\cap, \cup), \{\top, \bot\})$ together with the set complement operation $\complement$ is a Boolean algebra. A Boolean algebra is completely distributive iff it is isomorphic to a power set. Every finite Boolean algebra has a power of two $2^n$ number of elements. Boolean function $f: 2^n \mapsto 2$ is an operation on the Boolean domain $2 = \{0, 1\}$. There are $2^{2^n}$ Boolean functions in a Boolean algebra of order $n$.