Skip to main content\(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 6.1 Notation and Terminology
Definition Parts.
Definition 6.1.
A
poset is an ordered pair
\(\bfP=(X,P)\) with
\(X\) a set and
\(P\) a binary relation on
\(X\) that is reflexive, antisymmetric, and transitive.
-
Binary relation: Ordered pairs (subset of
\(X\times X\))
-
Reflexive: For all \(x\in X\text{,}\) \((x,x)\in P\text{.}\)
-
Antisymmetric: If \((x,y)\in P\) and \((y,x)\in P\text{,}\) then \(x=y\text{.}\)
-
If
\(x\leq y\) in
\(P\) and
\(y\leq x\) in
\(P\text{,}\) then
\(x=y\text{.}\)
-
Transitive: If \((x,y)\in P\) and \((y,z)\in P\text{,}\) then \((x,z)\in P\text{.}\)
-
If
\(x\leq y\) in
\(P\) and
\(y\leq z\) in
\(P\text{,}\) then
\(x\leq z\) in
\(P\text{.}\)
Peer instruction question 1
Key Concepts for Posets.
Let \(\bfP=(X,P)\) be a poset.
-
If
\(x\lt y\) in
\(P\) or
\(y\lt x\) in
\(P\text{,}\) then
\(x\) and
\(y\) are
comparable.
-
If
\(x \lt y\) in
\(P\) and there does not exist
\(z\) so that
\(x\lt z\lt y\) in
\(P\text{,}\) then
\(y\) covers \(x\)
-
If
\(x,y\in X\) and neither
\(x\lt y\) in
\(P\) nor
\(y\lt x\) in
\(P\text{,}\) then
\(x\) and
\(y\) are
incomparable.
-
A set
\(A\subseteq X\) is an
antichain if no pair of distinct points in
\(A\) is comparable in
\(P\text{.}\)
-
A set
\(C\subseteq X\) is a
chain if every pair of distinct points in
\(C\) is comparable in
\(P\text{.}\)
Peer instruction questions 2–3.
The order diagram of a poset with 34 points. The points are labeled from 1 to 34.
Maximal vs Maximum.
Definition 6.2.
A chain
\(C\) is
maximal if there is no chain
\(C'\) so that
\(C'\supsetneq C\text{.}\)
Definition 6.3.
A chain
\(C\) is
maximum if there is no chain
\(C'\) so that
\(|C'|\gt |C|\text{.}\)
Definition 6.4.
An antichain
\(A\) is
maximal if there is no antichain
\(A'\) so that
\(A'\supsetneq A\text{.}\)
Definition 6.5.
An antichain
\(A\) is
maximum if there is no antichain
\(A'\) so that
\(|A'|\gt |A|\text{.}\)
Peer instruction questions 4–6.
Maximal and Minimal Elements.
Definition 6.6.
Let
\(\bfP=(X,P)\) be a poset. An element
\(x\in X\) is
maximal if there is no
\(y\in X\) with
\(y\gt x\) in
\(P\text{.}\)
Definition 6.7.
Let
\(\bfP=(X,P)\) be a poset. An element
\(x\in X\) is
minimal if there is no
\(y\in X\) with
\(y\lt x\) in
\(P\text{.}\)
Activity 6.1.1.
With your group, list the
set of maximal elements and the
set of minimal elements for this poset.
The order diagram of a poset with 34 points. The points are labeled from 1 to 34.
Height and Width.
Definition 6.8.
The
height of a poset
\(\bfP\) is the number of points in a maxim
um chain in
\(\bfP\)
Definition 6.9.
The
width of a poset
\(\bfP\) is the number of points in a maxim
um antichain in
\(\bfP\)
Peer instruction question 7.
