Properties of Lattices

Definition

A lattice is a poset $(L, \le)$ such that for every pair of elements $a, b \in L$:

• the greatest lower bound exists, called the meet and written $a \wedge b$
• the least upper bound exists, called the join and written $a \vee b$

So, a lattice is a set with an order relation where every two elements can be combined in two ways:

meet

• : the largest element below both

join

• : the smallest element above both

Basic notation

For elements $a$ and $b$ in a lattice:

• $a \wedge b$: meet
• $a \vee b$: join

Example: In the set of all subsets of $S = \{1,2,3\}$, ordered by inclusion:

• $A \wedge B = A \cap B$
• $A \vee B = A \cup B$

Main Content

1. Fundamental Algebraic Properties

Commutative law

• :
• $a \wedge b = b \wedge a$
• $a \vee b = b \vee a$
• This means the order of elements does not matter.
• Example: $A \cap B = B \cap A$, $A \cup B = B \cup A$

Associative law

• :
• $(a \wedge b) \wedge c = a \wedge (b \wedge c)$
• $(a \vee b) \vee c = a \vee (b \vee c)$
• This allows us to group elements in any way.
• Example: $(A \cap B) \cap C = A \cap (B \cap C)$

These laws make lattice operations behave much like familiar operations in arithmetic and set theory.

2. Absorption and Idempotent Properties

Idempotent law

• :
• $a \wedge a = a$
• $a \vee a = a$
• Combining an element with itself gives the same element.
• Example: $A \cup A = A$, $A \cap A = A$

Absorption law

• :
• $a \wedge (a \vee b) = a$
• $a \vee (a \wedge b) = a$
• This expresses that one operation “absorbs” the other.
• Example:
  • $A \cap (A \cup B) = A$
  • $A \cup (A \cap B) = A$

These properties are central because they connect the meet and join operations in a lattice.

3. Order-Theoretic and Structural Properties

Partial order compatibility

• :
• The lattice order is determined by meet and join:
  • $a \le b$ if and only if $a \wedge b = a$
  • $a \le b$ if and only if $a \vee b = b$
• This helps translate order problems into algebraic ones.

Bounded lattice properties

• :
• If a lattice has a least element $0$ and greatest element $1$, it is called a bounded lattice.
• Then:
  • $a \wedge 0 = 0$
  • $a \vee 1 = 1$
• Example: In power set lattices, $0 = \varnothing$ and $1 = S$

Duality principle

• :
• Many lattice statements remain true if we swap:
  • $\wedge$ with $\vee$
  • $\le$ with $\ge$
  • $0$ with $1$
• This is called dual reasoning.
• Example:
  • If $a \wedge b = a$, then dually $a \vee b = b$

This structural viewpoint is extremely useful in proving lattice theorems efficiently.

Working / Process

1. Identify the set and order relation

• Determine the elements and how they are ordered.
• Example: subsets ordered by $\subseteq$, numbers ordered by $\le$, or divisors ordered by divisibility.

2. Find meet and join for each pair

• Compute the greatest lower bound and least upper bound.
• For sets: meet = intersection, join = union.
• For divisors of a number: meet = gcd, join = lcm.

3. Verify lattice properties

• Check commutativity, associativity, idempotence, and absorption.
• Determine whether the lattice is bounded, distributive, complemented, modular, or complete if needed.

Example for subsets of $\{1,2,3\}$:

        {1,2,3}
       /   |   \
   {1,2} {1,3} {2,3}
     | \    |    / |
     |  \   |   /  |
    {1}  {2} {3}
       \   |   /
           ∅

Here:

• bottom element is $\varnothing$
• top element is $\{1,2,3\}$
• meet of $\{1,2\}$ and $\{1,3\}$ is $\{1\}$
• join of them is $\{1,2,3\}$

Advantages / Applications

Helps simplify ordered structures

• Lattices provide a unified way to study order, bounds, and combining elements.
• This makes complex posets easier to analyze.

Widely used in set theory and algebra

• Power sets, divisor lattices, Boolean algebras, and subspace lattices are all important examples.
• In each case, meet and join have natural meanings.

Important in logic and computer science

• Lattices are used in propositional logic, digital circuits, formal concept analysis, compiler design, and data flow analysis.
• They help model information flow, dependencies, and state systems.

Supports advanced mathematical properties

• Many special classes of lattices are studied through these properties:
  • distributive lattices
  • modular lattices
  • complemented lattices
  • complete lattices

Useful for combinatorics

• Lattice structures appear in counting problems, ordering of partitions, and combinatorial proofs.
• Hasse diagrams make these structures easier to visualize and compare.

Summary

• A lattice is a poset where every pair of elements has a meet and join.
• Its main properties include commutativity, associativity, idempotence, absorption, and order compatibility.
• Lattices can be bounded, distributive, modular, complemented, or complete depending on additional structure.
• Important terms to remember: poset, meet, join, greatest lower bound, least upper bound, bounded lattice, distributive lattice, modular lattice, complemented lattice, duality