Posets and Hasse Diagrams

In discrete mathematics and order theory, we study how elements of a set relate to one another in terms of hierarchy and precedence. While equivalence relations group similar elements together, partial orderings allow us to compare and sequence elements systematically, providing the foundation for analyzing complex structured hierarchies.

1. Foundations of Partially Ordered Sets (Posets)

A relation $R$ on a set $A$ is a subset of the Cartesian product $A \times A$ . We say that $a$ is related to $b$ , denoted as $a R b$ or $a \preceq b$ , if $(a, b) \in R$ .

To establish a hierarchical order over a set, we require a relation that behaves predictably with respect to comparison. This leads us to define a partial ordering.

Mathematical Definition of a Partial Ordering

A binary relation $\preceq$ on a set $S$ is called a partial ordering (or partial order) if it satisfies three axiomatic properties for all $a, b, c \in S$ :

Reflexivity: Every element is related to itself. $a \preceq a \quad \forall a \in S$
Antisymmetry: If two distinct elements relate in one direction, they cannot relate in the opposite direction. $((a \preceq b) \land (b \preceq a)) \implies a = b \quad \forall a, b \in S$

A set $S$ together with a partial ordering relation $\preceq$ is called a partially ordered set, or simply a poset, and is denoted as $\langle S, \preceq \rangle$ .

Key Examples of Posets

1. The "Greater Than or Equal To" Relation $\langle \mathbb{Z}, \ge \rangle$

Let us prove that $\ge$ is a partial ordering on the set of integers $\mathbb{Z}$ :

Reflexivity: For any integer $a$ , $a \ge a$ is always true.
Antisymmetry: For any integers $a$ and $b$ , if $a \ge b$ and $b \ge a$ , then .

2. The Subset Inclusion Relation $\langle P(A), \subseteq \rangle$

Let $P(A)$ be the power set of a set $A$ . The subset relation $\subseteq$ is a partial ordering:

Reflexivity: $X \subseteq X$ for any set $X \in P(A)$ .
Antisymmetry: If $X \subseteq Y$ and $Y \subseteq X$ , then .

3. The Divisibility Relation $\langle \mathbb{Z}^+, \mid \rangle$

Let $\mathbb{Z}^+$ be the set of positive integers. The "divides" relation ( $a \mid b$ , meaning $a$ divides $b$ without a remainder, or $b = ac$ for some ) is a partial ordering:

Reflexivity: $a \mid a$ since $a = a \cdot 1$ .
Antisymmetry: If $a \mid b$ and $b \mid a$ , then there exist positive integers such that and . Substituting gives , which implies . Since , , so .

2. Comparability and Total Orders

In a poset $\langle S, \preceq \rangle$ , it is not guaranteed that every pair of elements can be compared. This is why the ordering is termed "partial."

Comparability vs. Incomparability

The elements $a$ and $b$ in a poset $\langle S, \dots \rangle$ are called comparable if: $a \preceq b \quad \text{or} \quad b \dots a$
If neither $a \preceq b$ nor holds, the elements and are called .

Total Orders (Chains)

If every single pair of elements in a poset is comparable, the relation is called a total ordering (or linear ordering), and the set is called a totally ordered set (or a chain).

$\forall a, b \in S \implies (a \preceq b) \lor (b \dots a)$

Example: The poset $\langle \mathbb{Z}, \le \rangle$ is totally ordered because for any two integers $x$ and $y$ , either $x \le y$ or $y \le x$ .

3. Covering Relations and Hasse Diagram Construction

Representing a poset as a standard directed graph (digraph) results in significant visual clutter due to reflexive loops and transitive paths. Hasse diagrams solve this by displaying only the essential order relationships.

The Covering Relation

To construct a Hasse diagram, we must first define the concept of covering:

In a poset $\langle P, \preceq \rangle$ , an element $y \in P$ is said to cover $x \in P$ (or $y$ is an immediate successor of $x$ ) if:

$x \prec y$ (meaning $x \preceq y$ and $x \neq y$ ).
There is no element $z \in P$ such that .

Rules for Drawing a Hasse Diagram

We construct a Hasse diagram from the digraph of a partial order relation using the following three steps:

Remove Reflexive Loops: Since every element $a$ satisfies $a \preceq a$ by default, we omit all self-loops.
Remove Transitive Edges: If $a \preceq b$ and $b \dots c$ , the transitive relationship $a \dots c$ is implied. We remove the direct edge from to .

Step-by-Step Visualization Examples

Example 1: Power Set $\langle P(S), \subseteq \rangle$ where $S = \{a, b, c\}$

The elements are $\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}$ .

text

                     {a, b, c}
                    /    |    \
                   /     |     \
             {a, b}    {a, c}   {b, c}
              /  \     /    \    /  \
             /    \   /      \  /    \
           {a}     {b}       {c}
             \      |        /
              \     |       /
               \    |      /
                  { }

Example 2: Divides relation $\langle X, \mid \rangle$ where $X = \{2, 3, 6, 12, 24, 36\}$

Let us verify the covering relations for this poset:

$6$ covers $2$ and $3$ .
$12$ covers $6$ (it does not cover $2$ or $3$ because $6$ lies between them).
covers .

text

             24       36
              \       /
               \     /
                 12
                 |
                 6
                / \
               /   \
              2     3

4. Extremal Elements in Posets

Certain elements occupy critical positions at the boundaries of a poset. We categorize these as maximal, minimal, greatest, or least elements.

Definitions

Maximal Element: An element $a \in P$ is maximal if it is not covered by any other element. That is, there exists no $x \in P$ such that $a \prec x$ . They appear at the top level of a Hasse diagram.
Minimal Element: An element $b \in P$ is minimal if no element is covered by it. That is, there exists no such that . They appear at the bottom level of a Hasse diagram.

Key Properties and Differences

Uniqueness: Greatest and least elements are guaranteed to be unique if they exist. Maximal and minimal elements do not have to be unique.
Existence: In a finite poset, maximal and minimal elements are guaranteed to exist, but greatest and least elements may not.

Proof of Uniqueness for the Greatest Element

Let $\langle P, \preceq \rangle$ be a poset. Suppose $g_1$ and $g_2$ are both greatest elements in $P$ .

Since $g_1 \in P$ and $g_2$ is a greatest element, we must have $g_1 \preceq g_2$ .

Analysis of the Divides Example

Referencing our Hasse diagram for $X = \{2, 3, 6, 12, 24, 36\}$ under the divides relation:

Minimal Elements: $2$ and $3$ (no elements divide them within $X$ ).
Maximal Elements: $24$ and $36$ (no elements in $X$ are multiples of them).
Least Element: None. For an element to be the least, it must divide all elements in $X$ . Neither nor divides the other.

5. Bounds, Supremum, and Infimum

When studying subsets of a poset, we often need to determine limits or bounds that constrain the subset from above or below.

Upper and Lower Bounds

Let $\langle P, \preceq \rangle$ be a poset, and let $A \subseteq P$ be a subset.

An element $x \in P$ is an upper bound of $A$ if: $a \preceq x \quad \forall a \in A$
An element $y \in P$ is a lower bound of if:

Note: The bounds $x$ and $y$ are not required to belong to the subset $A$ ; they only need to belong to the parent poset $P$ .

Least Upper Bound (LUB) and Greatest Lower Bound (GLB)

Least Upper Bound (LUB / Supremum): An element $x \in P$ $x \in P$ is the least upper bound of $A$ $A$ (denoted $\text{lub}(A)$ $lub (A)$ or $\sup(A)$ $sup (A)$ ) if:
1. $x$ is an upper bound of $A$ .

Worked Example: Computing Bounds

Using the poset $\langle P, \preceq \rangle$ shown in the Hasse diagram below:

text

               h       i
                \     /
                 \   /
                   g
                  / \
                 /   \
                d     e     f
                 \   /     /
                  \ /     /
                   b     c
                    \   /
                     \ /
                      a

Let our subset be $A = \{d, e\}$ .

Finding the LUB of $A = \{d, e\}$

Identify the upper bounds of $\{d, e\}$ : Elements that are larger than or equal to both $d$ and $e$ . These are $\{g, h, i\}$ .
Find the least element among these upper bounds:
- $g \preceq h$ and .

Finding the GLB of $A = \{d, e\}$

Identify the lower bounds of $\{d, e\}$ : Elements that are smaller than or equal to both $d$ and $e$ . These are $\{b, a\}$ .
Find the greatest element among these lower bounds:
- $a \preceq b$ , meaning is larger than .

Introduction to Lattices

A poset $\langle P, \preceq \rangle$ in which every two-element subset $\{a, b\} \subseteq P$ has both a unique least upper bound ( $a \lor b$ , called the join) and a unique greatest lower bound ( $a \land b$ , called the ) is called a .

Summary

A poset $\langle S, \preceq \rangle$ is a set paired with a relation that is reflexive, antisymmetric, and transitive.
Elements in a poset can be comparable or incomparable. If all pairs are comparable, the poset is a total order (or chain).
Hasse diagrams simplify partial order graphs by removing self-loops and transitive edges, displaying the ordering vertically.
An element is maximal (or minimal) if no element is above (or below) it. Greatest (or least) elements must be comparable to all other elements, making them unique when they exist.
Upper and lower bounds define boundaries for subsets within a poset. The unique extremes of these boundary sets are the Least Upper Bound (LUB/Supremum) and the Greatest Lower Bound (GLB/Infimum).

Assessed progress

Posets and Hasse Diagrams

Posets and Hasse Diagrams

1. Foundations of Partially Ordered Sets (Posets)

Mathematical Definition of a Partial Ordering

Key Examples of Posets

1. The "Greater Than or Equal To" Relation $\langle \mathbb{Z}, \ge \rangle$

2. The Subset Inclusion Relation $\langle P(A), \subseteq \rangle$

3. The Divisibility Relation $\langle \mathbb{Z}^+, \mid \rangle$

2. Comparability and Total Orders

Comparability vs. Incomparability

Total Orders (Chains)

3. Covering Relations and Hasse Diagram Construction

The Covering Relation

Rules for Drawing a Hasse Diagram

Step-by-Step Visualization Examples

Example 1: Power Set $\langle P(S), \subseteq \rangle$ where $S = \{a, b, c\}$

Example 2: Divides relation $\langle X, \mid \rangle$ where $X = \{2, 3, 6, 12, 24, 36\}$

4. Extremal Elements in Posets

Definitions

Key Properties and Differences

Proof of Uniqueness for the Greatest Element

Analysis of the Divides Example

5. Bounds, Supremum, and Infimum

Upper and Lower Bounds

Least Upper Bound (LUB) and Greatest Lower Bound (GLB)

Worked Example: Computing Bounds

Finding the LUB of $A = \{d, e\}$

Finding the GLB of $A = \{d, e\}$

Introduction to Lattices

Summary

Key Concepts

Partial Ordering

Partially Ordered Set (Poset)

Hasse Diagram

Extremal Elements

Bounds (LUB and GLB)

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures