📊Order Theory Unit 2 – Partially ordered sets

What are Partially Ordered Sets?

• Partially ordered sets (posets) consist of a set and a binary relation that is reflexive, antisymmetric, and transitive
• The binary relation is often denoted as $\leq$ and read as "less than or equal to"
• For elements $a, b$ in a poset, if $a \leq b$ or $b \leq a$, then $a$ and $b$ are said to be comparable
• In a poset, not all elements need to be comparable (unlike total orders)
• Posets generalize the concept of ordering from total orders (like real numbers) to partial orders
• Example: The set of subsets of $\{1, 2, 3\}$ with the subset inclusion relation $\subseteq$ forms a poset
• Posets appear in various branches of mathematics (combinatorics, algebra, topology) and computer science (data structures, algorithms)

Key Properties and Terminology

• A binary relation $\leq$ on a set $P$ is called a partial order if it satisfies the following properties:
  • Reflexivity: For all $a \in P$, $a \leq a$
  • Antisymmetry: For all $a, b \in P$, if $a \leq b$ and $b \leq a$, then $a = b$
  • Transitivity: For all $a, b, c \in P$, if $a \leq b$ and $b \leq c$, then $a \leq c$
• If $a \leq b$ and $a \neq b$, we write $a < b$ and say "$a$ is strictly less than $b$"
• Two elements $a, b \in P$ are comparable if either $a \leq b$ or $b \leq a$; otherwise, they are incomparable
• A chain is a subset of a poset in which any two elements are comparable
• An antichain is a subset of a poset in which any two distinct elements are incomparable
• The height of a poset is the maximum length of a chain in the poset
• The width of a poset is the maximum size of an antichain in the poset

Types of Partial Orders

• Linear order (total order): A poset in which any two elements are comparable (e.g., real numbers with $\leq$)
• Weak order: A poset in which incomparability is transitive (i.e., if $a$ is incomparable to $b$ and $b$ is incomparable to $c$, then $a$ is incomparable to $c$)
• Lattice: A poset in which any two elements have a unique least upper bound (join) and a unique greatest lower bound (meet)
  • Examples: The power set of a set with the subset inclusion relation, the set of positive integers with the divisibility relation
• Well-founded order: A poset with no infinite descending chains (i.e., there is no infinite sequence $a_1 > a_2 > a_3 > \ldots$)
• Preorder (quasiorder): A binary relation that is reflexive and transitive but not necessarily antisymmetric
• Strict partial order: An irreflexive, transitive binary relation (often denoted as $<$)

Hasse Diagrams: Visualizing Posets

• A Hasse diagram is a graphical representation of a poset that captures the ordering relation
• Elements of the poset are represented as vertices in the diagram
• If $a < b$ in the poset and there is no element $c$ such that $a < c < b$, then there is an edge drawn from $a$ to $b$
• The edges are directed upwards, so the greater element is always above the lesser element
• Transitive relations are not explicitly shown in the diagram to avoid clutter
• Example: The Hasse diagram of the divisibility relation on $\{1, 2, 3, 4, 6, 12\}$ is a lattice
• Hasse diagrams help visualize the structure of a poset and identify properties like chains, antichains, and lattices

Important Elements in Posets

• Minimal element: An element $a \in P$ is minimal if there is no element $b \in P$ such that $b < a$
• Maximal element: An element $a \in P$ is maximal if there is no element $b \in P$ such that $a < b$
• Least element (bottom): An element $a \in P$ is the least element if $a \leq b$ for all $b \in P$
• Greatest element (top): An element $a \in P$ is the greatest element if $b \leq a$ for all $b \in P$
• Lower bound: An element $a \in P$ is a lower bound of a subset $S \subseteq P$ if $a \leq b$ for all $b \in S$
• Upper bound: An element $a \in P$ is an upper bound of a subset $S \subseteq P$ if $b \leq a$ for all $b \in S$
• Infimum (greatest lower bound): An element $a \in P$ is the infimum of a subset $S \subseteq P$ if it is the greatest element among all lower bounds of $S$
• Supremum (least upper bound): An element $a \in P$ is the supremum of a subset $S \subseteq P$ if it is the least element among all upper bounds of $S$

Operations on Posets

• Dual of a poset: The dual of a poset $(P, \leq)$ is the poset $(P, \leq^*)$, where $a \leq^* b$ if and only if $b \leq a$ in the original poset
  • The dual poset reverses the order relation
• Product of posets: The product of two posets $(P_1, \leq_1)$ and $(P_2, \leq_2)$ is the poset $(P_1 \times P_2, \leq)$, where $(a_1, a_2) \leq (b_1, b_2)$ if and only if $a_1 \leq_1 b_1$ and $a_2 \leq_2 b_2$
• Disjoint union of posets: The disjoint union of two posets $(P_1, \leq_1)$ and $(P_2, \leq_2)$ is the poset $(P_1 \sqcup P_2, \leq)$, where $a \leq b$ if and only if either $a, b \in P_1$ and $a \leq_1 b$, or $a, b \in P_2$ and $a \leq_2 b$
• Ordinal sum of posets: The ordinal sum of two posets $(P_1, \leq_1)$ and $(P_2, \leq_2)$ is the poset $(P_1 \oplus P_2, \leq)$, where $a \leq b$ if and only if either $a, b \in P_1$ and $a \leq_1 b$, or $a, b \in P_2$ and $a \leq_2 b$, or $a \in P_1$ and $b \in P_2$
• Interval of a poset: For elements $a, b$ in a poset $P$ with $a \leq b$, the interval $[a, b]$ is the subposet $\{x \in P : a \leq x \leq b\}$

Applications in Mathematics and Computer Science

• Order theory: Posets are the main objects of study in order theory, a branch of mathematics that investigates the abstract notion of ordering
• Combinatorics: Posets are used to study various combinatorial structures (graphs, hypergraphs, simplicial complexes) and their properties
• Algebra: Posets appear in the study of algebraic structures (groups, rings, modules) and their relationships
• Topology: Posets are used to define topological spaces (Alexandrov topology) and study their properties
• Domain theory: Posets are used to model the semantics of programming languages and study the properties of programs
• Scheduling and resource allocation: Posets can model task dependencies and resource constraints in scheduling problems
• Data structures: Posets can be used to design and analyze efficient data structures (priority queues, search trees)
• Algorithms: Posets appear in the analysis and design of algorithms (sorting, searching, graph algorithms)

Common Examples and Practice Problems

• The set of natural numbers with the usual "less than or equal to" relation $(\mathbb{N}, \leq)$ is a linear order
• The set of subsets of a set with the subset inclusion relation $(\mathcal{P}(X), \subseteq)$ is a lattice
• The set of positive integers with the divisibility relation $(\mathbb{Z}^+, \mid)$ is a poset (not a lattice)
• The set of points in the plane with the coordinate-wise comparison relation $(\mathbb{R}^2, \leq)$ is a poset (not a linear order)
• Practice problem: Draw the Hasse diagram of the divisibility relation on the set $\{1, 2, 3, 5, 6, 10, 15, 30\}$
• Practice problem: Find the minimal and maximal elements, least and greatest elements (if they exist), and the height and width of the poset $(\mathcal{P}(\{1, 2, 3\}), \subseteq)$
• Practice problem: Prove that a finite poset has at least one minimal element and at least one maximal element
• Practice problem: Given a poset $(P, \leq)$, define a relation $\sim$ on $P$ by $a \sim b$ if and only if there exists an element $c \in P$ such that $a \leq c$ and $b \leq c$. Prove that $\sim$ is an equivalence relation on $P$