# 19: Partially ordered sets

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

• 19.1: Motivation
In many of the sets we encounter, there is some notion of elements being “less than or equal to” other elements in the set.
• 19.2: Definition and properties
Notice that in each of the examples in Section 19.1, the notion of “is smaller than” is defined via a relation.
• 19.3: Graph for a partial order
Hasse diagram: a diagram for the graph for a partial order on a finite set A, omitting reflexive loops and transitive “composite” edges, and placing “smaller” elements lower on the diagram instead of using arrows
• 19.4: Total Orders
Comparable Elements: elements a,b in a partially ordered set such that either a⪯b or b⪯a
• 19.5: Maximal/minimal Elements
Each of the following definitions are for a subset B of a partially ordered set A.
• 19.6: Topological Sorting
Sometimes we want to turn a partial order into a total order. What makes an order partial instead of total is the presence of pairs of incomparable elements.
• 19.7: Activities
• 19.8: Exercises

This page titled 19: Partially ordered sets is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.