Posets

Definition

A poset is a pair $(P, \leq)$ , where $P$ is a set and $\leq$ is a binary relation on $P$ satisfying the following three properties:

1. Reflexive

: For every $a \in P$ , $a \leq a$ .

2. Antisymmetric

: If $a \leq b$ and $b \leq a$ , then $a = b$ .

3. Transitive

: If $a \leq b$ and $b \leq c$ , then $a \leq c$ .

A relation satisfying these properties is called a partial order.

Example

Let $P = \{1, 2, 3, 6\}$ with the relation “divides” $(\mid)$ .

$1 \mid 2$ , $1 \mid 3$ , $1 \mid 6$
$2 \mid 6$ , $3 \mid 6$
But $2$ and $3$ are incomparable because neither divides the other.

So $(P, \mid)$ is a poset.

Important terminology

Comparable elements

: Two elements $a$ and $b$ are comparable if $a \leq b$ or $b \leq a$ .

Incomparable elements

: Two elements are incomparable if neither $a \leq b$ nor $b \leq a$ holds.

Partial order

: A relation satisfying reflexive, antisymmetric, and transitive properties.

Main Content

1. First Concept: Partial Order Relation

A partial order relation is the defining feature of a poset. It organizes elements in a structured way, but unlike total order, not every pair must be comparable.

Reflexivity

ensures every element is related to itself, which gives consistency to the ordering.

Antisymmetry

prevents two distinct elements from being mutually related in both directions.

Transitivity

allows the ordering to extend logically across chains of elements.

Example

Consider the set $A = \{a, b, c\}$ with relation $\leq$ defined by:

$a \leq a, b \leq b, c \leq c$
$a \leq b$
$b \leq c$
therefore $a \leq c$ by transitivity

This relation is a partial order if it satisfies all three conditions.

Notes on partial order

A partial order may represent hierarchy, containment, divisibility, or precedence.
In a partial order, some elements may remain unrelated.
This is what makes posets more flexible than total orders.

2. Second Concept: Comparable and Incomparable Elements

In a poset, understanding whether elements can be compared is essential.

Comparable elements

lie in a direct ordering relationship.

Incomparable elements

cannot be placed above or below one another using the relation.

Example using divisibility

Let $P = \{1, 2, 3, 4, 6\}$ with divisibility:

$2$ and $4$ are comparable because $2 \mid 4$
$2$ and $3$ are incomparable because $2 \nmid 3$ and $3 \nmid 2$

Example using subset relation

Let $S = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$ ordered by $\subseteq$ :

$\{a\} \subseteq \{a,b\}$
$\{b\} \subseteq \{a,b\}$
$\{a\}$ and $\{b\}$ are incomparable

This concept is crucial because many mathematical structures are naturally only partially ordered.

3. Third Concept: Hasse Diagram Representation

A Hasse diagram is a graphical way to represent a poset more simply. It shows the order relation without drawing all reflexive and transitive edges.

Elements are drawn as points.
If $a < b$ , then $b$ is placed higher than $a$ .
Edges are drawn only for covering relations, not for every implied relation.
No arrows are usually needed because the vertical placement already shows direction.

Example: Poset of divisors of 6

Elements: $\{1,2,3,6\}$

This diagram shows:

$1$ is below $2$ and $3$
$2$ and $3$ are below $6$
$2$ and $3$ are incomparable

Why Hasse diagrams are useful

They make posets easier to visualize.
They remove unnecessary information.
They help identify minimal elements, maximal elements, and chains.

Working / Process

1. Identify the set and relation

Determine the set of objects and the relation used to compare them.
Examples include $\leq$ , $\mid$ , and $\subseteq$ .

2. Verify the partial order properties

Check reflexivity: every element relates to itself.
Check antisymmetry: mutual relation implies equality.
Check transitivity: ordering is preserved through intermediate elements.

3. Analyze the structure

Find comparable and incomparable pairs.
Identify minimal and maximal elements.
Draw a Hasse diagram if needed.
Use the diagram to study chains, antichains, and ordering behavior.

Advantages / Applications

Models real-life hierarchies and dependencies

Posets are used in task scheduling, course prerequisites, project planning, and version control.

Foundation for lattice theory

Posets are the starting point for studying lattices, which are important in algebra and logic.

Useful in combinatorics and computer science

They help analyze subsets, divisibility, sorting constraints, data structures, and partially ordered information.

Summary

Posets are sets with a partial order relation.
The relation must be reflexive, antisymmetric, and transitive.
Not every pair of elements needs to be comparable.
Important terms to remember: poset, partial order, comparable, incomparable, Hasse diagram, minimal element, maximal element, chain, antichain.