2.2 Finite and infinite posets

Definition of posets

A partially ordered set (poset) is a set paired with a binary relation that lets you compare some, but not necessarily all, of its elements. Unlike a total order (where every pair of elements is comparable), a poset allows for incomparable elements, two elements where neither one "comes before" the other.

Posets show up everywhere: organizing files into folders, ranking tasks by dependency, or structuring mathematical objects by containment or divisibility.

Partial order relations

A binary relation $\leq$ on a set $P$ is a partial order if it satisfies three properties:

1. Reflexivity: Every element is related to itself. For all $a \in P$, $a \leq a$.
2. Antisymmetry: If two elements are each related to the other, they must be equal. If $a \leq b$ and $b \leq a$, then $a = b$.
3. Transitivity: Relations chain together. If $a \leq b$ and $b \leq c$, then $a \leq c$.

The relation symbol varies by context: $\leq$ for numerical ordering, $\subseteq$ for subset inclusion, $\mid$ for divisibility, or $\sqsubseteq$ in domain theory.

Two classic examples:

• Subset inclusion on a collection of sets: $A \subseteq B$ means every element of $A$ is in $B$. The sets $\{1,2\}$ and $\{2,3\}$ are incomparable since neither is a subset of the other.
• Divisibility on positive integers: $a \mid b$ means $b$ is a multiple of $a$. For instance, $2 \mid 6$ but $2$ and $3$ are incomparable under divisibility.

Properties of posets

• Reflexivity ensures every element is related to itself, giving the order a "starting point" at each element.
• Antisymmetry prevents two distinct elements from being mutually related, which is what separates partial orders from preorders.
• Transitivity lets you chain comparisons: knowing $a \leq b$ and $b \leq c$ is enough to conclude $a \leq c$.

When two elements $a$ and $b$ satisfy neither $a \leq b$ nor $b \leq a$, they are incomparable, written $a \| b$. The presence of incomparable pairs is exactly what makes a partial order partial.

Posets can be represented visually with Hasse diagrams or algebraically as a pair $(P, \leq)$ where $P$ is the underlying set.

Finite posets

A finite poset has a finite number of elements. This finiteness makes them far more tractable: you can enumerate all elements, draw complete diagrams, and run algorithms over them directly.

Characteristics of finite posets

• Every finite poset has at least one maximal element and at least one minimal element. (This follows from finiteness alone; you don't need Zorn's Lemma here.)
• The height of a finite poset is the length of its longest chain (longest path of comparable elements). The width is the size of its largest antichain (largest set of pairwise incomparable elements).
• Finite posets can be completely represented by Hasse diagrams.
• Many efficient algorithms apply to finite posets, such as topological sorting, which produces a linear extension of the partial order.

Examples of finite posets

• Power set of a finite set ordered by inclusion: $(P(\{1,2,3\}), \subseteq)$ has $2^3 = 8$ elements. The set $\{1\}$ is below $\{1,2\}$, but $\{1\}$ and $\{2\}$ are incomparable.
• Divisors of an integer ordered by divisibility: the poset $(\{1,2,3,4,6,12\}, \mid)$ has $1$ as the least element and $12$ as the greatest.
• Vertices of a directed acyclic graph (DAG) ordered by reachability: if there's a directed path from $u$ to $v$, then $u \leq v$.
• Finite lattices such as distributive lattices and Boolean lattices.

Hasse diagrams for finite posets

A Hasse diagram is the standard way to visualize a finite poset:

1. Draw each element as a point (vertex).
2. If $a < b$ and there is no element $c$ with $a < c < b$ (meaning $b$ covers $a$), draw an edge from $a$ up to $b$.
3. Omit all edges that would be implied by transitivity.
4. Read the diagram bottom-to-top: lower elements are "smaller" in the order.

From a Hasse diagram you can quickly spot comparable pairs (connected by an upward path), incomparable pairs (no upward path in either direction), and special elements like maximal, minimal, greatest, and least elements.

Infinite posets

An infinite poset has infinitely many elements. These can be countably infinite (like $\mathbb{N}$) or uncountably infinite (like $\mathbb{R}$). The original guide states that infinite posets "contain an uncountable number of elements," but that's not always true. Many important infinite posets are countable.

Characteristics of infinite posets

• May or may not have maximal or minimal elements. The integers $(\mathbb{Z}, \leq)$ have neither.
• Cannot be fully drawn as a Hasse diagram, though you can diagram finite substructures.
• Can contain infinite chains (like $1 < 2 < 3 < \cdots$ in $\mathbb{N}$) and infinite antichains.
• Can exhibit structural features impossible in finite posets, such as dense orders (between any two comparable elements there's a third, as in $\mathbb{Q}$) and well-orders (every nonempty subset has a least element).
• Often require tools like order topology, completions, or transfinite induction for analysis.

Examples of infinite posets

• Real numbers with the standard order: $(\mathbb{R}, \leq)$. This is actually a total order, but every total order is a special case of a partial order.
• Power set of an infinite set ordered by inclusion: $(P(\mathbb{N}), \subseteq)$. This is uncountable and has many incomparable elements.
• Function spaces ordered pointwise: for functions $f, g : \mathbb{R} \to \mathbb{R}$, define $f \leq g$ iff $f(x) \leq g(x)$ for all $x$.
• Ordinal numbers with their standard ordering, central to set theory.

Representation of infinite posets

Since you can't just draw the whole thing, infinite posets are studied using:

• Set-theoretic notation to define elements and the relation precisely.
• Order-preserving maps (embeddings) that relate a complex poset to a simpler one while preserving structure.
• Order topology, which defines open sets using the order relation, enabling tools from topology like continuity and convergence.
• Completion techniques such as the Dedekind-MacNeille completion, which adds elements to make every subset have a least upper bound and greatest lower bound.
• First-order logic and axiomatic set theory for formal treatments.
• Diagrams of finite substructures or approximations when visualization is needed.

Comparisons of finite vs infinite posets

The distinction between finite and infinite posets affects which theorems apply, which algorithms work, and what structural phenomena are possible.

Structural differences

• Finite posets always have maximal and minimal elements. Infinite posets may lack them entirely.
• Dense suborders (where between any two comparable elements there exists another) are impossible in finite posets but common in infinite ones (e.g., $\mathbb{Q}$).
• Chains and antichains in finite posets have bounded length/size. In infinite posets, both can be infinite.
• Finite posets have finite height and width. Infinite posets can have infinite height, infinite width, or both.
• Infinite posets can exhibit limit points and accumulation points, connecting order theory to topology.

Computational considerations

• Algorithms for finite posets typically rely on enumeration or graph traversal, which isn't possible for infinite posets.
• Infinite posets often require transfinite induction or other set-theoretic methods.
• Topological methods become essential for analyzing convergence and continuity in infinite ordered structures.
• Storing or representing infinite posets in a computer requires approximation or symbolic techniques.
• Certain properties that are decidable for finite posets (like whether two posets are isomorphic) may become undecidable for infinite ones.

Operations on posets

You can build new posets from existing ones using several standard operations. These constructions are fundamental for studying the algebraic side of order theory.

Union and intersection

• The union of two posets combines their elements, preserving order relations where they agree. This doesn't always produce a valid poset unless the relations are compatible.
• The intersection keeps only elements (and relations) common to both posets.
• The disjoint union places two posets side by side with no order relations between them. Every element of one poset is incomparable to every element of the other.
• Order-preserving maps between posets can induce unions and intersections, but you need to verify the partial order axioms still hold in the result.

Product of posets

Given posets $(P, \leq_P)$ and $(Q, \leq_Q)$, their Cartesian product $(P \times Q)$ becomes a poset under the product order:

$(a_1, b_1) \leq (a_2, b_2) \quad \text{iff} \quad a_1 \leq_P a_2 \text{ and } b_1 \leq_Q b_2$

Both components must satisfy the relation simultaneously. This means many pairs in the product will be incomparable even if the original posets are total orders.

The product order preserves several properties of the original posets (such as completeness) and is important in category theory and universal algebra.

Special elements in posets

Identifying special elements is one of the first things you do when analyzing a poset. These elements characterize the "boundary" behavior of the order.

Maximal and minimal elements

• A maximal element $m$ has no element strictly above it: there is no $x$ with $m < x$.
• A minimal element $m$ has no element strictly below it: there is no $x$ with $x < m$.
• A poset can have multiple maximal elements and multiple minimal elements.
• Every finite poset has at least one of each. This is a direct consequence of finiteness (not Zorn's Lemma, which is a tool for infinite posets).
• Infinite posets may have none: $(\mathbb{Z}, \leq)$ has no maximal or minimal element.

Don't confuse these with greatest/least elements (see below). A maximal element just has nothing above it; a greatest element is above everything.

Greatest and least elements

• A greatest element (also called a top or maximum) satisfies $x \leq \top$ for all $x$ in the poset.
• A least element (also called a bottom or minimum) satisfies $\bot \leq x$ for all $x$ in the poset.
• If a greatest or least element exists, it is unique (this follows from antisymmetry).
• Not every poset has them. The poset $(\{2, 3, 5\}, \mid)$ has no greatest element since no single element is divisible by all others.
• When they do exist, they simplify analysis considerably and are central to lattice theory.

Chains and antichains

Chains and antichains are the two extreme types of subsets in a poset. In a chain, every pair of elements is comparable. In an antichain, no pair is comparable.

Finite chains and antichains

• A chain is a totally ordered subset: for any two elements $a, b$ in the chain, either $a \leq b$ or $b \leq a$.
• An antichain is a subset where all elements are pairwise incomparable.
• The length of the longest chain defines the height of the poset. The size of the largest antichain defines the width.
• Dilworth's theorem: In any finite poset, the minimum number of chains needed to cover all elements equals the size of the largest antichain. This is a powerful result connecting two seemingly different measurements.
• Sperner's theorem: In the power set poset $(P(\{1, \ldots, n\}), \subseteq)$, the largest antichain has size $\binom{n}{\lfloor n/2 \rfloor}$, consisting of all subsets of size $\lfloor n/2 \rfloor$.

Infinite chains and antichains

• Infinite chains arise naturally: $1 < 2 < 3 < \cdots$ in $(\mathbb{N}, \leq)$.
• Infinite antichains also exist: in $(P(\mathbb{N}), \subseteq)$, the collection of all singleton sets $\{\{1\}, \{2\}, \{3\}, \ldots\}$ forms an infinite antichain.
• A well-ordered set is a totally ordered set where every nonempty subset has a least element. Equivalently, it has no infinite descending chains.
• The study of infinite chains and antichains connects deeply to set theory and cardinal arithmetic.
• The Erdős–Szekeres theorem and its generalizations relate the existence of long chains or antichains to the size of the poset.

Isomorphisms between posets

Two posets are isomorphic if there's a bijection between them that preserves the order relation in both directions. Isomorphic posets are structurally identical; they differ only in the labels on their elements.

Finite poset isomorphisms

• An order isomorphism is a bijection $f: P \to Q$ such that $a \leq_P b$ if and only if $f(a) \leq_Q f(b)$.
• For finite posets, you can verify an isomorphism by checking all pairs of elements.
• Isomorphic finite posets have identical Hasse diagrams (up to relabeling of vertices).
• This concept is useful for recognizing when two posets that look different are actually the same structure. For example, the divisor poset of 12 is isomorphic to a certain sub-poset of the power set of $\{a, b, c\}$.
• Algorithms exist for testing finite poset isomorphism, though the problem is computationally nontrivial in general.

Infinite poset isomorphisms

• The same definition applies, but establishing a bijection between infinite sets is harder.
• Proofs often require transfinite methods or back-and-forth arguments (as in Cantor's proof that any two countable dense linear orders without endpoints are isomorphic).
• Infinite poset isomorphisms can reveal surprising connections between seemingly different structures.
• Verifying isomorphism algorithmically is generally not feasible for infinite posets; indirect or axiomatic arguments are used instead.

Applications of finite and infinite posets

Order theory in mathematics

• Set theory: Posets structure the study of cardinal and ordinal hierarchies.
• Algebra: Lattices, Boolean algebras, and other ordered algebraic structures are all posets with additional properties.
• Topology: Order topologies define open sets from the order relation, connecting order theory to continuity and convergence.
• Logic: Implication structures and proof trees are naturally ordered.
• Category theory: Posets are categories where there is at most one morphism between any two objects.
• Analysis: Completions of ordered sets (like the construction of $\mathbb{R}$ from $\mathbb{Q}$) rely on poset theory.

Real-world applications

• Scheduling and dependency resolution: Tasks with prerequisites form a poset. Topological sorting produces a valid execution order.
• Database query optimization: Posets model partial orderings on query plans to find efficient execution strategies.
• Project management: PERT charts and critical path methods use poset structure to schedule tasks and allocate resources.
• Biology: Phylogenetic trees and gene regulatory networks have natural partial order structure.
• Economics: Preference orderings in decision theory are often partial orders, since a consumer may not be able to rank every pair of options.

Theorems and proofs

Key theorems for finite posets

• Dilworth's theorem: The minimum number of chains needed to partition a finite poset equals the maximum size of an antichain.
• Mirsky's theorem: The dual result: the minimum number of antichains needed to partition a finite poset equals the maximum length of a chain.
• Sperner's theorem: The largest antichain in $(P(\{1,\ldots,n\}), \subseteq)$ has size $\binom{n}{\lfloor n/2 \rfloor}$.
• Birkhoff's representation theorem: Every finite distributive lattice is isomorphic to the lattice of downsets of some finite poset.
• Fixed point theorems: Tarski's fixed point theorem guarantees that every order-preserving map on a complete lattice has a fixed point. For finite lattices (which are always complete), this applies directly.

Key theorems for infinite posets

• Zorn's Lemma: If every chain in a poset has an upper bound, then the poset has a maximal element. This is equivalent to the Axiom of Choice and is used throughout mathematics for existence proofs.
• Hausdorff Maximal Principle: Every poset contains a maximal chain. Also equivalent to the Axiom of Choice.
• Well-ordering theorem: Every set can be well-ordered. Again equivalent to the Axiom of Choice.
• Completeness theorems for various classes of infinite posets, such as the fact that every complete lattice has the fixed point property (Tarski).
• Theorems on ordinals and cardinals that rely on the well-ordering of ordinal numbers.
• König's theorem in cardinal arithmetic, relating sums and products of infinite cardinals.