2.1 Lattice definition and axioms

Lattices are special structures in math that organize elements with a specific order. They're built on partially ordered sets, where any two elements have a least upper bound and greatest lower bound.

In lattices, we use join and meet operations to find these bounds. These operations follow rules like associativity and commutativity, which help us understand how elements relate to each other in the lattice.

Lattice Definition

Partially Ordered Sets and Lattices

Top images from around the web for Partially Ordered Sets and Lattices

• 

  Lattice (order) - Wikipedia View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

• 

  File:Set partitions 4; join and meet.svg - Wikimedia Commons View original

  Is this image relevant?

• 

  Lattice (order) - Wikipedia View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Partially Ordered Sets and Lattices

• 

  Lattice (order) - Wikipedia View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

• 

  File:Set partitions 4; join and meet.svg - Wikimedia Commons View original

  Is this image relevant?

• 

  Lattice (order) - Wikipedia View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

1 of 3

• A partially ordered set (poset) consists of a set $P$ together with a binary relation $\leq$ that satisfies reflexivity ($a \leq a$), antisymmetry ($a \leq b$ and $b \leq a$ imply $a = b$), and transitivity ($a \leq b$ and $b \leq c$ imply $a \leq c$)
• A lattice $(L, \leq)$ is a partially ordered set in which any two elements $a, b \in L$ have a least upper bound (join) denoted by $a \vee b$ and a greatest lower bound (meet) denoted by $a \wedge b$
• The binary operations $\vee$ (join) and $\wedge$ (meet) on a lattice satisfy the following properties for all $a, b, c \in L$:
  • Associativity: $(a \vee b) \vee c = a \vee (b \vee c)$ and $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
  • Commutativity: $a \vee b = b \vee a$ and $a \wedge b = b \wedge a$
  • Absorption: $a \vee (a \wedge b) = a$ and $a \wedge (a \vee b) = a$

Bounds in Lattices

• An upper bound of a subset $S$ of a partially ordered set $(P, \leq)$ is an element $u \in P$ such that $s \leq u$ for all $s \in S$
  • The set of all upper bounds of $S$ is denoted by $U(S)$
• A lower bound of a subset $S$ of a partially ordered set $(P, \leq)$ is an element $l \in P$ such that $l \leq s$ for all $s \in S$
  • The set of all lower bounds of $S$ is denoted by $L(S)$
• The least upper bound (join) of a subset $S$ of a lattice $(L, \leq)$ is the unique element $\bigvee S \in L$ such that:
  • $\bigvee S$ is an upper bound of $S$
  • For any other upper bound $u$ of $S$, we have $\bigvee S \leq u$
• The greatest lower bound (meet) of a subset $S$ of a lattice $(L, \leq)$ is the unique element $\bigwedge S \in L$ such that:
  • $\bigwedge S$ is a lower bound of $S$
  • For any other lower bound $l$ of $S$, we have $l \leq \bigwedge S$

Lattice Properties

Completeness

• A lattice $(L, \leq)$ is complete if every subset $S \subseteq L$ has a least upper bound $\bigvee S$ and a greatest lower bound $\bigwedge S$ in $L$
  • In a complete lattice, the empty set $\emptyset$ has a least upper bound $\bigvee \emptyset$, which is the bottom element $\bot$, and a greatest lower bound $\bigwedge \emptyset$, which is the top element $\top$
• Examples of complete lattices include:
  • The power set of a set ordered by inclusion $(\mathcal{P}(X), \subseteq)$
  • The set of all divisors of a positive integer ordered by divisibility $(\text{Div}(n), |)$

Algebraic Properties of Lattices

• Associativity: For all $a, b, c \in L$, $(a \vee b) \vee c = a \vee (b \vee c)$ and $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
  • This property allows for the unambiguous notation of $\bigvee_{i=1}^n a_i$ and $\bigwedge_{i=1}^n a_i$ for finite joins and meets
• Commutativity: For all $a, b \in L$, $a \vee b = b \vee a$ and $a \wedge b = b \wedge a$
  • The order of elements in a join or meet operation does not affect the result
• Idempotence: For all $a \in L$, $a \vee a = a$ and $a \wedge a = a$
  • Joining or meeting an element with itself yields the same element
• Absorption: For all $a, b \in L$, $a \vee (a \wedge b) = a$ and $a \wedge (a \vee b) = a$
  • This property relates the join and meet operations, showing that an element "absorbs" the result of joining or meeting it with another element