Partially Ordered Sets - Core Definitions

Partially ordered sets (posets) provide a mathematical framework for studying order relations. They appear throughout mathematics, from lattice theory to algebraic topology, and are fundamental to understanding combinatorial structures.

DefinitionPartially Ordered Set (Poset)

A partially ordered set is a pair $(P, \leq)$ where $P$ is a set and $\leq$ is a binary relation on $P$ satisfying:

Reflexivity: $x \leq x$ for all $x \in P$
Antisymmetry: if $x \leq y$ and $y \leq x$ , then $x = y$
Transitivity: if $x \leq y$ and $y \leq z$ , then $x \leq z$

We write $x < y$ if $x \leq y$ and $x \neq y$ . Elements $x, y$ are comparable if $x \leq y$ or $y \leq x$ ; otherwise they are incomparable (written $x \parallel y$ ).

ExampleCommon Posets

Natural numbers $(\mathbb{N}, \leq)$ with usual ordering (totally ordered)
Divisibility poset $(\mathbb{N}^+, |)$ where $a | b$ if $a$ divides $b$
Power set $(\mathcal{P}(S), \subseteq)$ ordered by inclusion
Integer partitions ordered by dominance: $\lambda \geq \mu$ if $\sum_{i=1}^k \lambda_i \geq \sum_{i=1}^k \mu_i$ for all $k$
Young's lattice: integer partitions ordered by diagram inclusion

DefinitionSpecial Elements

For a poset $(P, \leq)$ and subset $A \subseteq P$ :

Maximum: $m \in A$ with $a \leq m$ for all $a \in A$
Minimum: $m \in A$ with $m \leq a$ for all $a \in A$
Maximal: $m \in A$ with no $a \in A$ satisfying $m < a$
Minimal: $m \in A$ with no $a \in A$ satisfying $a < m$
Upper bound: $u \in P$ with $a \leq u$ for all $a \in A$
Lower bound: $l \in P$ with $l \leq a$ for all $a \in A$
Supremum (least upper bound): $\sup A = \min\{$ upper bounds of $A\}$
Infimum (greatest lower bound): $\inf A = \max\{$ lower bounds of $A\}$

DefinitionChains and Antichains

A chain is a totally ordered subset where all elements are pairwise comparable
An antichain is a subset where all elements are pairwise incomparable
The width of a poset is the maximum size of an antichain
The height (or length) is the maximum size of a chain minus 1

ExampleBoolean Lattice

The Boolean lattice $B_n = (\mathcal{P}(\{1,2,\ldots,n\}), \subseteq)$ has:

Size: $2^n$ elements
Height: $n$ (chains from $\emptyset$ to $\{1,\ldots,n\}$ )
Width: $\binom{n}{\lfloor n/2 \rfloor}$ (Sperner's theorem)
Rank function: $r(A) = |A|$

The Hasse diagram forms a hypercube graph in $n$ dimensions.

DefinitionLattice

A lattice is a poset in which every pair of elements $x, y$ has:

A join (supremum): $x \vee y = \sup\{x, y\}$
A meet (infimum): $x \wedge y = \inf\{x, y\}$

A complete lattice has joins and meets for all subsets (not just pairs). Every finite lattice is complete.

Remark

The Hasse diagram is a visual representation of a finite poset where:

Elements are drawn as vertices
$x < y$ is shown by $y$ above $x$
An edge connects $x$ to $y$ if $x < y$ and no $z$ satisfies $x < z < y$ (covering relation)

This eliminates reflexive loops and transitive edges for clarity.

DefinitionOrder-Preserving Maps

A function $f: P \to Q$ between posets is:

Order-preserving (monotone) if $x \leq_P y \implies f(x) \leq_Q f(y)$
Order-embedding if $x \leq_P y \iff f(x) \leq_Q f(y)$ (injective)
Order-isomorphism if it's a bijective order-embedding

An automorphism is an order-isomorphism from a poset to itself.

ExampleDilworth's Theorem Application

For the divisibility poset on $\{1, 2, \ldots, 12\}$ :

Primes $\{2, 3, 5, 7, 11\}$ form an antichain of size 5
A chain might be $1 < 2 < 4 < 12$
Maximum antichain size = width
Minimum chain decomposition covers all elements

Dilworth's theorem states: width = minimum number of chains needed to cover the poset.

Posets unify diverse mathematical structures and provide powerful tools for analyzing order relationships in combinatorics, algebra, and computer science.