Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\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\,}$}}}
\)
Exercises 19.8 Exercises
Recognizing a partial order from its graph.
In each of
Exercises 1–2 , you are given a directed graph for a relation on the set
\(A = \{a,b,c,d\} \text{.}\) Determine whether the relation is a partial order. Justify your answers.
Testing partial orders.
In each of
Exercises 3–6 , you are given a set
\(A \) and a relation
\(R \) on
\(A \text{.}\) Determine whether the relation is a partial order. Justify your answers.
3.
\(A \) is the set of all Augustana students;
\(a \mathrel{R} b \) means that student
\(a \) has a higher GPA than student
\(b \text{.}\)
4.
\(A \) is the power set of some finite set;
\(S \mathrel{R} T \) means
\(\card{S} \le \card{T} \text{.}\)
5.
\(A \) is the set of words on some alphabet;
\(w \mathrel{R} w' \) means
\(\length{w} \le \length{w'} \text{,}\) where
\(\length{w} \) means the length of word
\(w \text{.}\)
6.
\(A = \R \cartprod \R \text{;}\) \((x1,y1) \mathrel{R} (x2,y2) \) means
\(x_1 \le x2 \) and
\(y_1 \le y2 \text{.}\)
Drawing Hasse diagrams.
In each of
Exercises 7–8 , you are given a finite, partially ordered set
\(A \text{.}\) Draw the Hasse diagram.
7.
\(A = \powset{\{1,2,3,4\}} \) under the subset relation.
8.
\(A = \words{\Sigma}_4 \text{,}\) the set of words of length
\(4 \) in the alphabet
\(\Sigma = \{0,1\} \text{,}\) under dictionary order.
9. Draw all possible valid Hasse diagrams for each of the sets
\(A = \{a,b\} \) and
\(B = \{a,b,c\} \text{.}\) (Thus, you will have determined all possible partial orders on those sets.)
10.
Consider the “divides” relation
\(\mathord{\mid} \) on
\(\posset{\N} \text{.}\) Provide an example of a set
\(A \subseteq \posset{\N} \)
(a) that is finite, and on which
\(\mathord{\mid} \) is a total order.
(b) that is infinite, and on which
\(\mathord{\mid} \) is a total order.
(c) on which
\(\mathord{\mid} \) is a partial order but not a total order.
11. Let
\(A = \{0,1,2\} \text{,}\) and consider the partial order
\(\mathord{\subseteq} \) on the power set
\(\powset{A} \text{.}\) List all pairs of incomparable elements in
\(\powset{A} \text{.}\)
Determining maximal/maximum/minimal/minimum elements.
In each of
Exercises 12–16 , you are given a partially ordered set
\(A \text{.}\) Determine any and all maximal, maximum, minimal, and minimum elements.
12.
\(A = \posset{\N} \) under the usual
\(\mathord{\le} \text{.}\)
13.
\(A = \posset{\Q} \) under the usual
\(\mathord{\le} \text{.}\)
14.
\(A = \N \relcmplmnt \{0,1\} \) under the “divides” relation
\(\mathord{\mid} \text{.}\)
15.
\(A = \{2,5,11,13,22,65,110,143,496\} \) under the “divides” relation
\(\mathord{\mid} \text{.}\)
16.
\(A \) is the set of the first ten prime numbers under the “divides” relation
\(\mathord{\mid} \text{.}\)
17. Suppose
\(\mathord{\partorder} \) is a partial order on the set
\(A = \{0,1,2\} \) such that
\(1 \) is a maximal element. What are the possibilities for the Hasse diagram of
\(\mathord{\partorder} \text{?}\)
