UNIT 6: Posets, Hasse Diagrams and Lattices

1. Ordered Sets and Hasse Diagrams

Definition of Partial Order

[!IMPORTANT]

A partial order on a set $P$ is a binary relation "$\preceq$" that is reflexive, antisymmetric, and transitive. The set $P$ together with "$\preceq$" forms a "partially ordered set" or "poset": $(P, \preceq)$.

Properties:

Reflexivity: For all $a \in P$, $a \preceq a$.
Antisymmetry: For all $a, b \in P$, if $a \preceq b$ and $b \preceq a$, then $a = b$.
Transitivity: For all $a, b, c \in P$, if $a \preceq b$ and $b \preceq c$, then $a \preceq c$.

[!TIP]

To show something is a poset, check all three properties above with proper cases.

Examples of Posets

$(\mathbb{N}, \leq)$: "less than or equal to" on natural numbers.
$(\mathcal{P}(S), \subseteq)$: Power set of $S$ with subset relation.
$(\mathbb{Z}, |)$: Set of integers with "divides" ($a|b$) relation.

Poset Notation and Terminology

$(P, \preceq)$: Denotes a poset.
Chain: A subset of $P$ where every two elements are comparable (i.e., $\forall a, b$, $a \preceq b$ or $b \preceq a$).
Antichain: A subset where no two different elements are comparable.
Maximal Element: $m \in P$, if there is no $x \in P$ such that $m \prec x$.
Minimal Element: $n \in P$, if there is no $x \in P$ such that $x \prec n$.
Greatest Element: $g \in P$, with $a \preceq g$ for all $a \in P$.
Least Element: $l \in P$, with $l \preceq a$ for all $a \in P$.

Hasse Diagrams

Definition and Purpose

[!IMPORTANT]

A Hasse diagram is a graphical representation of a finite poset, where elements are drawn as vertices, and edges denote the partial order, omitting reflexive and implied (by transitivity) edges.

Useful to visualize the structure and relationships within a poset.

Steps to Construct a Hasse Diagram

Write all elements as points (vertices).
Draw an edge upward from $a$ to $b$ if $a \prec b$ and no $c$ with $a \prec c \prec b$ (i.e., $b$ covers $a$).
Place smaller (with respect to order) elements lower and larger elements higher.
Do not draw edges for reflexivity or transitivity.

[!TIP]

Omit drawing loops (reflexive edges) and direct edges where there is a chain (due to transitivity).

Example: Drawing Hasse Diagram for a Simple Poset

Let $A = \{1, 2, 4\}$ with the relation "$a | b$" ("divides").

Step 1: List ordered pairs where $a | b$.
- $1|1$, $1|2$, $1|4$, $2|2$, $2|4$, $4|4$
Step 2: Remove reflexive pairs and use only "covering pairs":
- $1$ is covered by $2$ ($1|2$), $2$ is covered by $4$ ($2|4$)
Hasse Diagram:
- $1$ at the bottom.
- Connect $1 \rightarrow 2$ (edge up).
- Connect $2 \rightarrow 4$ (edge up).

Draw 3 nodes vertically labeled '1' (bottom), '2' (middle),

Above diagram shows the Hasse diagram for $(\{1,2,4\}, |)$.

Numerical Example:

Draw the Hasse diagram for $(S, \subseteq)$, where $S = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.

Pairs: $\emptyset \subseteq \{a\}, \emptyset \subseteq \{b\}, \{a\} \subseteq \{a, b\}, \{b\} \subseteq \{a, b\}$, etc.
Levels:
- Bottom: $\emptyset$
- Middle: $\{a\}$ and $\{b\}$
- Top: $\{a, b\}$
Edges: (from bottom up)
- $\emptyset \rightarrow \{a\}$
- $\emptyset \rightarrow \{b\}$
- $\{a\} \rightarrow \{a, b\}$
- $\{b\} \rightarrow \{a, b\}$

$Place four nodes. Bottom-most: $\emptyset$; above and left/r$

This Hasse diagram illustrates all subset relations in $S$ without redundant edges.

2. Isomorphic and Well-Ordered Sets

Isomorphic Ordered Sets

Definition of Order Isomorphism

[!IMPORTANT]

Two posets $(A, \leq_A)$ and $(B, \leq_B)$ are "order isomorphic" if there exists a bijection $f: A \to B$, such that for all $x, y \in A$,

$$ x \leq_A y \iff f(x) \leq_B f(y) $$

Such $f$ preserves the ordering structure.

Criteria for Isomorphism

$f$ must be bijective (one-to-one and onto).
$f$ must preserve the order: $x \leq y \implies f(x) \leq f(y)$.
$f^{-1}$ (its inverse) must also preserve order.

[!TIP]

Isomorphism means "same structure as a poset," not just same elements.

Numerical Example

Are $(\{1, 2, 3\}, \leq)$ and $(\{a, b, c\}, \leq_{lex})$ with $a < b < c$ isomorphic?

Possible bijection: $1 \to a$, $2 \to b$, $3 \to c$.
$1 < 2$ maps to $a < b$, $2 < 3$ maps to $b < c$.
All comparisons preserved.

Conclusion: The two ordered sets are isomorphic under this mapping.

Well-Ordered Sets

Definition

[!IMPORTANT]

A totally ordered set $(A, \leq)$ is "well-ordered" if every non-empty subset of $A$ has a least element.

Examples

$(\mathbb{N}, \leq)$ is well-ordered.
Every finite totally ordered set is well-ordered.
$(\mathbb{Z}, \leq)$ is not well-ordered.

Properties of Well-Ordered Sets

Every chain in a well-ordered set is finite or countably infinite.
There are no infinite strictly descending sequences.
Every subset has a unique minimal (least) element.

[!TIP]

Beware: "Totally ordered" does not always mean "well-ordered"!

3. Properties of Lattices, Bounded and Complemented Lattices

Lattices

Definition of Lattice

[!IMPORTANT]

A poset $(L, \leq)$ is a lattice if every pair of elements $a, b \in L$ has both a least upper bound (join, $a \vee b$) and a greatest lower bound (meet, $a \wedge b$) in $L$.

Meet and Join Operations

Meet ($a \wedge b$): Greatest element $\leq a$ and $\leq b$.
Join ($a \vee b$): Least element $\geq a$ and $\geq b$.

Formally:

$$ a~\wedge~b = \textrm{Greatest lower bound (GLB)~of~} \{a, b\} $$

$$ a~\vee~b = \textrm{Least upper bound (LUB)~of~} \{a, b\} $$

Lattice as Algebraic Structure

$(L, \wedge, \vee)$ forms an algebraic structure called a "lattice."
The operations satisfy:
- Commutativity: $a \wedge b = b \wedge a$, $a \vee b = b \vee a$
- Associativity: $a \wedge (b \wedge c) = (a \wedge b) \wedge c$, etc.
- Absorption: $a \wedge (a \vee b) = a$, $a \vee (a \wedge b) = a$
- Idempotency: $a \wedge a = a$, $a \vee a = a$

Examples: Smallest Lattice Structures

Divisors of $6$: $L = \{1, 2, 3, 6\}$, "$|$" operation.
- Meets (GLB): $\gcd$
- Joins (LUB): $\mathrm{lcm}$

Place node '1' at bottom. Above, '2' (left), '3' (right). To

Numerical Example: Meet and Join in Set Lattice

Let $S = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.

For $A = \{a\}$, $B = \{b\}$:
- $A \wedge B = \{a\} \cap \{b\} = \emptyset$
- $A \vee B = \{a\} \cup \{b\} = \{a, b\}$

Properties of Lattices

Derivations and Proofs

Commutativity:

$$ a \wedge b = b \wedge a $$

$$ a \vee b = b \vee a $$

Both GLB and LUB are symmetric in $a$ and $b$.

Associativity:

$$ (a \wedge b) \wedge c = a \wedge (b \wedge c) $$

$$ (a \vee b) \vee c = a \vee (b \vee c) $$

Proof:

GLB of $\{a, b, c\}$ is the same, regardless of grouping.
Absorption:

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

Consider: $a \leq a \vee b$ (by definition), so GLB of $a$ and $a \vee b$ is $a$, i.e. $a \wedge (a \vee b) = a$.

Idempotency:

$$ a \wedge a = a $$

$$ a \vee a = a $$

GLB and LUB of the same element is itself.

Table: Properties of Lattice Operations

Property	Meet $(\wedge)$	Join $(\vee)$
Commutativity	$a\wedge b = b\wedge a$	$a\vee b = b\vee a$
Associativity	$(a\wedge b)\wedge c$ = $a\wedge (b\wedge c)$	$(a\vee b)\vee c = a\vee (b\vee c)$
Idempotency	$a\wedge a = a$	$a\vee a = a$
Absorption	$a\wedge(a\vee b)=a$	$a\vee(a\wedge b)=a$

Importance/Applications

Lattices form abstract models for order.
Used in logic (Boolean Algebra), algebra (ideals), computer science (data flow analysis), and set theory.

Bounded Lattices

Definition

[!IMPORTANT]

A lattice $(L, \leq)$ is bounded if it has both a least element (0 or $\hat{0}$) and a greatest element (1 or $\hat{1}$); i.e., for all $a \in L,\, \hat{0} \leq a \leq \hat{1}$.

Examples of Bounded Lattices

The lattice of subsets $\mathcal{P}(S)$ is bounded: least element $\emptyset$, greatest element $S$.
The divisor lattice of $6$: $1$ is least, $6$ is greatest.

$For $\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$. Draw two no$

Numerical Example

Let $L = \{0, 1\}$ with $0 \leq 1$.

Least: $0$, Greatest: $1$
$0 \wedge 1 = 0$, $0 \vee 1 = 1$

So $(\{0,1\}, \leq)$ is a bounded lattice.

Complemented Lattices

Definition

[!IMPORTANT]

A bounded lattice $(L, \leq, \hat{0}, \hat{1})$ is complemented if, for every $a \in L$, there exists $b \in L$ such that:

$$ > a \wedge b = \hat{0} \quad \textrm{and} \quad a \vee b = \hat{1} > $$

$b$ is called a complement of $a$.

Uniqueness of Complements

In general lattices, complements may not be unique.
Boolean lattices: Complements are unique.

[!TIP]

State if the lattice is distributive and bounded to ensure unique complements.

Example: Boolean Lattice as Complemented Lattice

Consider $\mathcal{P}(\{a, b\})$, the lattice of $\{\emptyset, \{a\}, \{b\}, \{a, b\}\}$:
- Complement of $\{a\}$ is $\{b\}$ (union = whole set, intersection = $\emptyset$).
- Likewise for $\{b\}$.

Reproduce the power-set lattice diagram from earlier; label

Numerical Example

Let $L = (\mathcal{P}(\{a\}), \subseteq)$: $\{\emptyset, \{a\}\}$.

$\emptyset$'s complement is $\{a\}$
- $\emptyset \vee \{a\} = \{a\}$ (greatest)
- $\emptyset \wedge \{a\} = \emptyset$ (least)
$\{a\}$'s complement is $\emptyset$

Both elements have complements; thus, $L$ is a complemented (and Boolean) lattice.

End of UNIT 6 Notes

[!TIP]

For full marks: Write definitions exactly, always draw clean Hasse diagrams, emphasize algebraic proofs for lattice properties, and clearly contrast bounded/complemented/Boolean cases in tables or examples.