19: Partially ordered sets
- Page ID
- 83498
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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.