Elementary Discrete Mathematics 2

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.