🔳Lattice Theory Unit 7 – Complemented Lattices and Boolean Algebras

Key Concepts and Definitions

• Lattice defined as a partially ordered set in which every pair of elements has a least upper bound (join) and a greatest lower bound (meet)
• Bounded lattice contains a top element $\top$ and a bottom element $\bot$
• Complemented lattice defined as a bounded lattice where each element $a$ has a complement $a'$ such that $a \vee a' = \top$ and $a \wedge a' = \bot$
  • Complements in a complemented lattice are not necessarily unique
• Boolean algebra defined as a complemented distributive lattice
  • In a Boolean algebra, complements are unique
• Atoms are the minimal non-zero elements in a lattice
• Duality principle states that for every theorem in lattice theory, there is a dual theorem obtained by interchanging joins and meets, and $\top$ and $\bot$
• Isomorphism between lattices preserves the lattice structure and operations

Lattice Structures and Properties

• Lattices can be represented using Hasse diagrams, where elements are nodes and lines represent the partial order
• A sublattice is a subset of a lattice that is closed under joins and meets
• A lattice is distributive if the following identities hold for all elements $a$, $b$, and $c$:
  • $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
  • $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
• A lattice is modular if it satisfies the modular law: if $a \leq c$, then $a \vee (b \wedge c) = (a \vee b) \wedge c$
• A lattice is complete if every subset has a join and a meet
• A lattice is atomic if every element is the join of atoms
• A lattice is algebraic if every element is the join of compact elements, where an element $a$ is compact if $a \leq \bigvee S$ implies $a \leq \bigvee T$ for some finite subset $T \subseteq S$

Complemented Lattices: Fundamentals

• In a complemented lattice, every element has at least one complement
• The complement of $\top$ is $\bot$, and the complement of $\bot$ is $\top$
• If $a \leq b$, then $b' \leq a'$ for any complements $a'$ and $b'$ of $a$ and $b$, respectively
• The meet of an element and its complement is always $\bot$, and their join is always $\top$
• In a finite complemented lattice, the number of elements is always a power of 2
• A complemented lattice is distributive if and only if complements are unique
• A complemented modular lattice is called an orthomodular lattice
  • Orthomodular lattices have applications in quantum logic

Boolean Algebras: Introduction

• Boolean algebras are complemented distributive lattices
• In a Boolean algebra, complements are unique, and the complement of an element $a$ is denoted as $a'$ or $\bar{a}$
• Boolean algebras satisfy the following additional identities for all elements $a$ and $b$:
  • $a \wedge a' = \bot$ and $a \vee a' = \top$ (complement laws)
  • $a \wedge \top = a$ and $a \vee \bot = a$ (identity laws)
  • $a \wedge a = a$ and $a \vee a = a$ (idempotent laws)
  • $a \wedge b = b \wedge a$ and $a \vee b = b \vee a$ (commutative laws)
  • $(a \wedge b) \wedge c = a \wedge (b \wedge c)$ and $(a \vee b) \vee c = a \vee (b \vee c)$ (associative laws)
  • $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$ and $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$ (distributive laws)
  • $(a')' = a$ (double complement law)
• De Morgan's laws hold in Boolean algebras: $(a \wedge b)' = a' \vee b'$ and $(a \vee b)' = a' \wedge b'$
• Every finite Boolean algebra is isomorphic to the power set of a finite set with set-theoretic operations

Relationship Between Complemented Lattices and Boolean Algebras

• Every Boolean algebra is a complemented distributive lattice
• A complemented lattice is a Boolean algebra if and only if it is distributive
• Stone's representation theorem states that every Boolean algebra is isomorphic to a field of sets (a set algebra)
• In a Boolean algebra, the complement of an element is unique, while in a complemented lattice, an element may have multiple complements
• A complemented lattice can be embedded into a Boolean algebra using the MacNeille completion
• The Dedekind-MacNeille completion of a complemented lattice is the smallest complete lattice containing it
• The center of a complemented lattice consists of all elements with a unique complement, forming a Boolean sublattice

Theorems and Proofs

• Theorem: A lattice is distributive if and only if it does not contain a sublattice isomorphic to $M_3$ or $N_5$
  • Proof involves showing that the existence of $M_3$ or $N_5$ sublattices leads to a contradiction with distributivity
• Theorem: A complemented lattice is a Boolean algebra if and only if it is distributive
  • Proof relies on showing that distributivity implies uniqueness of complements and vice versa
• Theorem: Every finite Boolean algebra has $2^n$ elements for some non-negative integer $n$
  • Proof uses induction on the number of atoms and the fact that each element is the join of a unique set of atoms
• Theorem: A lattice is a Boolean algebra if and only if it is isomorphic to a sublattice of the power set of some set
  • Proof involves constructing an isomorphism between the Boolean algebra and a set algebra
• Theorem: The axioms for Boolean algebras are independent
  • Proof requires demonstrating that removing any one axiom results in a structure that is not a Boolean algebra

Applications and Examples

• Power set lattices: The power set of a set $X$, denoted $\mathcal{P}(X)$, forms a Boolean algebra under set inclusion, union, and intersection
  • Example: For $X = \{1, 2, 3\}$, $\mathcal{P}(X)$ is a Boolean algebra with 8 elements
• Propositional logic: The set of propositional formulas forms a Boolean algebra under logical equivalence, disjunction, and conjunction
  • Example: $p \wedge (q \vee r)$ is equivalent to $(p \wedge q) \vee (p \wedge r)$ in propositional logic
• Switching circuits: Boolean algebras are used to model and optimize switching circuits in digital electronics
  • Example: A simple circuit with two switches in series is modeled by the Boolean expression $x \wedge y$
• Lindenbaum-Tarski algebras: The set of sentences in a formal language modulo logical equivalence forms a Boolean algebra
  • Example: In first-order logic, the Lindenbaum-Tarski algebra is used to prove the completeness theorem
• Quantum logic: Orthomodular lattices, which are a generalization of Boolean algebras, are used to model quantum-mechanical systems
  • Example: The lattice of closed subspaces of a Hilbert space is an orthomodular lattice

Practice Problems and Exercises

1. Prove that in a distributive lattice, if $a \wedge b = a \wedge c$ and $a \vee b = a \vee c$, then $b = c$.
2. Show that in a Boolean algebra, $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$ for all elements $a$, $b$, and $c$.
3. Prove that a finite lattice is complemented if and only if it is isomorphic to a sublattice of a finite power set lattice.
4. Let $L$ be a complemented lattice. Prove that the following statements are equivalent:
   • $L$ is a Boolean algebra
   • $L$ is distributive
   • Every element of $L$ has a unique complement
5. Prove that a lattice is a Boolean algebra if and only if it satisfies the following identities for all elements $a$ and $b$:
   • $a \wedge (a \vee b) = a$
   • $a \vee (a \wedge b) = a$
6. Show that the center of a complemented lattice forms a Boolean sublattice.
7. Construct the Hasse diagram of the Boolean algebra formed by the power set of $\{1, 2, 3, 4\}$.
8. Prove that every finite Boolean algebra is atomic.