Skip to main content
Contents Embed Prev Up Next \(\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.4 Interval Orders
An
interval order is a special type of poset
\(\mbf{P}=(X,P')\text{.}\)
Each
\(x\in X\) is associated with an interval
\([a_{x},b_{x}]\)
\(x\lt y\) in \(P'\) if and only if \(b_{x} \lt a_{y}\)
\(x\) ’s interval is completely
We call the collection of intervals an
interval representation of
\(\mbf{P}\text{.}\)
Sketch of an example, then
peer instruction questions 1–2 and handout activity .
Activity 6.4.1 .
The poset below is denoted
\(\bftwo+\bftwo\text{,}\) which we read as “two plus two”. Draw an interval representation for this poset or explain why it is not possible.
The order diagram of a poset with four points. The points are labeled
\(x,y,z,w\text{.}\) There are two cover relations:
\(y\lt x\) and
\(w\lt z\text{.}\)
There are four incomparabilities we must check when confirming a
\(\bftwo+\bftwo\)
Peer instruction question 3
Theorem 6.14 . Fishburn’s Theorem.
A poset is an interval order if and only if it does not contain
\(\bftwo+\bftwo\) as a subposet.
Intransitive Indifference with Unequal Indifference Intervals by Peter C. Fishburn of the Research Analysis Corporation, McLean, Virginia. Masthead indicates Journal of Mathematical Psychology , volume 7, pages 144–149 (1970).
Can we find a representation?
The order diagram of a poset with 10 points. The points are labeled from 1 to 10.
For a poset \(\mbf{P}=(X,P')\text{,}\) we define the following notation:
Down-set (or down set):
\(D(x) = \{y\in X\colon y \lt x\text{ in }P'\}\text{.}\)
Up-set (or up set):
\(U(x) = \{y\in X\colon y > x\text{ in }P'\}\text{.}\)
\(\mc{D}\text{:}\) the set of all down-sets.
\(\mc{U}\text{:}\) the set of all up-sets.
Activity 6.4.2 .
Find the down-sets
\(D(2)\) and
\(D(8)\) as well as the up-sets
\(U(5)\text{,}\) \(U(6)\text{,}\) \(U(7)\text{,}\) and
\(U(9)\) for the poset shown below.
The order diagram of a poset with 10 points. The points are labeled from 1 to 10.
Proposition 6.15 .
Let \(\mbf{P}\) be a poset. Then the following are equivalent:
\(\mbf{P}\) is an interval order.
Any two distinct sets in
\(\mc{D}\) are ordered by inclusion.
Any two distinct sets in
\(\mc{U}\) are ordered by inclusion.
Proposition 6.16 .
If
\(\mbf{P}\) is an interval order, then
\(|\mc{D}|=|\mc{U}|\text{.}\)
Algorithm 6.17 . Poset to Interval Representation.
Input: An interval order \(\mbf{P}=(X,P')\text{.}\)
Determine
\(D(x)\) for each
\(x\in X\text{.}\)
Write down
\(\mc{D}\) as
\(\{\} = D_{1} \subsetneq D_{2}\subsetneq \cdots\subsetneq D_{d}\text{.}\)
Determine
\(U(x)\) for each
\(x\in X\text{.}\)
Write down
\(\mc{U}\) as
\(U_{1} \supsetneq U_{2}\supsetneq \cdots\supsetneq U_{d} = \{\}\text{.}\)
For each
\(x\in X\text{,}\) find
\(D(x) = D_{i}\) and
\(U(x)=U_{j}\text{.}\) Then let
\(I(x)=[i,j]\text{.}\)
(Optional unless instructed) Draw the interval representation.
Peer instruction questions 4–5.
