Exercises 16.3 Exercises
1.
Let \(X=\{a,b,c,d,e,f\}\) and \(R\) be the relation on \(X\) defined by
Is \(R\) a partial order? If so, draw its partial order diagram. If not, give an example showing why.
2.
Let \(X=\{a,b,c,d,e,f\}\) and \(S\) be the relation on \(X\) defined by
Is \(S\) a partial order? If so, draw its partial order diagram. If not, give an example showing why.
3.
Let \(X=\{a,b,c,d,e,f\}\) and \(T\) be the relation on \(X\) defined by
Is \(T\) a partial order? If so, draw its partial order diagram. If not, give an example showing why.
4.
Let \(X=\{1,2,3,4,5,6\}\) and \(R\) be the relation on \(X\) defined by
Is \(R\) a partial order? If so, draw its partial order diagram. If not, give an example showing why.
5.
Let \(X\) be any set and define the relation \(S\) on \(\mathscr{P}(X)\) where
Is \(S\) a linear order? Tell why or why not.
6.
Let \(X\) be any set and define the relation \(S\) on \(\mathscr{P}(X)\) where
If \(X=\{a,b,c,d\}\text{,}\) draw the partial order diagram for \(S\text{.}\)
7.
Let \(\mathcal{B}_2\) be the set of all \(2\times 2\) Boolean matrices, and let \(T\) be the relation on \(\mathcal{B}_2\) where
(If necessary reread the chapter on Boolean matrices to remind yourself what \(\le\) means for Boolean matrices.)
Give the maximal and minimal elements of \(T\text{.}\)
8.
Let \(\mathcal{B}_2\) be the set of all \(2\times 2\) Boolean matrices, and let \(T\) be the relation on \(\mathcal{B}_2\) where
(If necessary reread the chapter on Boolean matrices to remind yourself what \(\le\) means for Boolean matrices.)
Draw the partial order diagram for \(T\text{.}\)
9.
Consider the relation on \(\mathbf{N}\) where \(m\) is related to \(n\) if \(n|m\text{.}\) That is, \(m\) is related to \(n\) if \(n\) divides \(m\text{,}\) so \(6\) is “less than” \(3\text{.}\) This is the “upside down” (dual) version of the partial order described the beginning of the chapter.
Restrained to just the set \(X=\{0,1,2,3,4,6,8,12\}\text{,}\) draw a partial order diagram.
10.
It sure seems like this should be a partial order: take a family of sets, and declare \(E\) to be related to \(F\) if \(|E| \le |F|\text{.}\) Why isn't it? Provide a specific example using two sets.
Antisymmetry is where things start to fall apart.
The following exercises concern the partial order \(R\text{,}\) diagrammed below.
A partial order is diagrammed. The element \(a\) is related to \(b\) and \(c\text{,}\) which are both related to \(d\text{.}\) The element \(c\) is also related to \(e\text{.}\) Both \(d\) and \(e\) are related to \(f\text{.}\)
11.
List the minimal and maximal elements of the partial order. Is there a minimum? Maximum?
12.
Give the lower bounds, upper bounds, least upper bound, and greatest lower bound (when they exist) of the set \(\{a,b,c\}\text{.}\)
13.
Does the partial order shown form a lattice? Why or why not?
The following exercises concern the partial order \(S\text{,}\) diagrammed below.
A partial order is diagrammed. The element \(a\) is related to \(b\text{,}\) which is related to both \(c\) and \(d\text{.}\) The element \(d\) is related to \(e\text{.}\) The element \(c\) is related to both \(f\) and \(g\text{,}\) which are both related to \(h\text{.}\)
14.
List the minimal and maximal elements of the partial order. Is there a minimum? Maximum?
15.
Give the lower bounds, upper bounds, least upper bound, and greatest lower bound (when they exist) of the set \(\{b,c,d\}\text{.}\)
16.
Does the partial order shown form a lattice? Why or why not?
The following exercises concern the partial order \(T\text{,}\) diagrammed below.
A partial order is diagrammed. The element \(x\) is related to \(w\text{,}\) which is related to both \(y\) and \(z\text{,}\) both of which are related to \(v\text{.}\) Also, the element \(u\) is related to \(z\) as well.
17.
List the minimal and maximal elements of the partial order. Is there a minimum? Maximum?
18.
Give the lower bounds, upper bounds, least upper bound, and greatest lower bound (when they exist) of the set \(\{v,y,z\}\text{.}\)
19.
Give the lower bounds, upper bounds, least upper bound, and greatest lower bound (when they exist) of the set \(\{u,w,z\}\text{.}\)
20.
Does the partial order shown form a lattice? Why or why not?
The following exercises concern the partial order \(R\text{,}\) diagrammed below.
A partial order is diagrammed. The element \(8\) is related to \(6\) and \(7\text{.}\) The element \(6\) is related to \(1\) and \(3\text{,}\) which are both related to \(2\text{.}\) The element \(7\) is related to \(3\) and \(5\text{,}\) which are both related to \(4\text{.}\)
21.
List the minimal and maximal elements of the partial order. Is there a minimum? Maximum?
22.
Give the lower bounds, upper bounds, least upper bound, and greatest lower bound (when they exist) of the set \(\{1,3,6\}\text{.}\)
23.
Give the lower bounds, upper bounds, least upper bound, and greatest lower bound (when they exist) of the set \(\{3,6,7\}\text{.}\)
24.
Does the partial order shown form a lattice? Why or why not?