1.7 Duality principle

Definition of Duality Principle

The duality principle says that if a statement is true for all partially ordered sets, then the "dual" of that statement is also true for all partially ordered sets. The dual is obtained by reversing every order relation in the statement. This single idea lets you get two theorems for the price of one.

Dual Statements

A dual statement is formed by systematically swapping order-theoretic terms throughout a statement:

• Replace $\leq$ with $\geq$ (and vice versa)
• Replace supremum (least upper bound) with infimum (greatest lower bound)
• Replace join ($\vee$) with meet ($\wedge$)
• Replace greatest element with least element

The key point: if the original statement is true in every poset, its dual is automatically true in every poset too. You don't need a separate proof.

For example, the statement "every finite nonempty poset has at least one maximal element" dualizes to "every finite nonempty poset has at least one minimal element." Both are true, and proving one immediately gives you the other.

Why It Matters

• It cuts proof work in half. Once you prove a theorem, you get its dual for free.
• It exposes symmetries in ordered structures that aren't always obvious at first glance.
• It provides a second perspective on any order-theoretic property, which often deepens understanding.

Dual Posets

Given a poset $(P, \leq)$, the dual poset (also called the opposite poset) is $(P, \geq)$. You keep the same set of elements but flip every comparison.

Constructing the Dual

1. Start with a poset $(P, \leq)$.
2. Define a new relation $\leq^{op}$ on $P$ by: $a \leq^{op} b$ if and only if $b \leq a$.
3. The result $(P, \leq^{op})$ is again a valid partial order (reflexivity, antisymmetry, and transitivity all carry over).

If you have a Hasse diagram, the dual corresponds to flipping the diagram upside down.

Properties of Dual Posets

Certain features swap roles in the dual, while others are preserved outright:

• Maximal elements in $(P, \leq)$ become minimal elements in $(P, \geq)$, and vice versa.
• The greatest element (if it exists) becomes the least element.
• A supremum of a subset in the original becomes an infimum of that subset in the dual.
• Chains (totally ordered subsets) remain chains, and antichains remain antichains.
• The cardinality and the covering relations are preserved (though each cover $a \lessdot b$ becomes $b \lessdot a$).

The dual of the dual gives you back the original poset: $(P, \leq^{op})^{op} = (P, \leq)$.

Dual Lattices

A lattice is a poset where every pair of elements has both a join (least upper bound) and a meet (greatest lower bound). Because lattices are posets, the duality principle applies, but it also has algebraic consequences.

Meet and Join Swap

In the dual of a lattice $(L, \leq)$:

• The meet ($\wedge$) in the original becomes the join ($\vee$) in the dual.
• The join ($\vee$) in the original becomes the meet ($\wedge$) in the dual.

So any lattice identity involving $\wedge$ and $\vee$ has a dual identity with the two operations swapped. For instance, the absorption law $a \vee (a \wedge b) = a$ dualizes to $a \wedge (a \vee b) = a$. Both hold in every lattice.

Properties like distributivity and modularity are self-dual: if a lattice is distributive, its dual is also distributive. This is because the defining identities for these properties are mapped to equivalent identities under dualization.

Complementation in Dual Lattices

In a bounded lattice (one with a top element $1$ and a bottom element $0$), an element $a'$ is a complement of $a$ if $a \wedge a' = 0$ and $a \vee a' = 1$.

When you dualize, $0$ and $1$ swap roles, and $\wedge$ and $\vee$ swap roles. The two complementation conditions simply exchange with each other, so $a'$ remains a complement of $a$ in the dual lattice.

This is why De Morgan's laws have a natural home in duality. In a Boolean lattice (a complemented distributive lattice), De Morgan's laws state:

• $(a \vee b)' = a' \wedge b'$
• $(a \wedge b)' = a' \vee b'$

Each of these is the dual of the other.

Galois Connections

A Galois connection is a pair of order-preserving (or order-reversing) functions between two posets that are linked by a specific adjunction condition. The duality principle is baked into the very definition.

Definition and Properties

Given two posets $(P, \leq)$ and $(Q, \leq)$, a Galois connection consists of two functions $f: P \to Q$ and $g: Q \to P$ such that for all $a \in P$ and $b \in Q$:

$f(a) \leq b \iff a \leq g(b)$

From this single condition, several properties follow:

• Both $f$ and $g$ are monotone (order-preserving).
• The compositions $g \circ f$ and $f \circ g$ are closure-like: $a \leq g(f(a))$ and $f(g(b)) \leq b$.
• Applying $f$ or $g$ three times gives the same result as applying it once: $f(g(f(a))) = f(a)$.

Notice the duality: $f$ and $g$ play symmetric but reversed roles. Swapping the two posets (and reversing the order on both) turns $f$ into $g$ and vice versa.

Examples in Order Theory

• Closure and interior operators. On the power set of a topological space, the closure operator and the interior operator form a Galois connection (with complementation mediating between them).
• Formal concept analysis. Given a relation between objects and attributes, the maps sending a set of objects to their shared attributes (and vice versa) form a Galois connection. The resulting fixed points are the concept lattice.
• Classical Galois theory. The maps between subgroups of the Galois group and intermediate field extensions form a Galois connection. This is the historical origin of the name.
• Topology. The relationship between open sets and closed sets (via complementation) can be framed as a Galois connection.