91Ó°ÊÓ

Show that the closure of a relation R with respect to a property P, if it exists, is the intersection of all the relations with property P that contain R.

Let \(R_{1}\) and \(R_{2}\) be relations on a set \(A\) represented by the matrices $$\mathbf{M}_{R_{1}}=\left[\begin{array}{ccc}{0} & {1} & {0} \\ {1} & {1} & {1} \\ {1} & {0} & {0}\end{array}\right] \text { and } \mathbf{M}_{R_{2}}=\left[\begin{array}{ccc}{0} & {1} & {0} \\ {0} & {1} & {1} \\\ {1} & {1} & {1}\end{array}\right]$$ Find the matrices that represent $$\begin{array}{llll}{\text { a) } R_{1} \cup R_{2}} & {\text { b) } R_{1} \cap R_{2}} & {\text { c) } R_{2} \circ R_{1}} \\ {\text { d) } R_{1} \circ R_{1}} & {\text { e) } R_{1} \oplus R_{2}}\end{array}$$

Find two incomparable elements in these posets. a) \((P(\\{0,1,2\\}), \subseteq)\) b) \((\\{1,2,4,6,8\\}, |)\)

Let \(R\) be a relation on a set \(A\) with \(n\) elements. If there are \(k\) nonzero entries in \(\mathbf{M}_{R},\) the matrix representing \(R,\) how many nonzero entries are there in \(\mathbf{M}_{R^{-1}},\) the matrix representing \(R^{-1}\) , the inverse of \(R ?\)

A relation \(R\) on the set \(A\) is irreflexive if for every \(a \in A,(a, a) \notin R .\) That is, \(R\) is irreflexive if no element in \(A\) is related to itself. Use quantifiers to express what it means for a relation to be irreflexive.

Find the lexicographic ordering of these \(n\) -tuples: a) \((1,1,2),(1,2,1)\) b) \((0,1,2,3),(0,1,3,2)\) c) \((1,0,1,0,1),(0,1,1,1,0)\)

Find the lexicographic ordering of these strings of lowercase English letters: a) quack, quick, quicksilver, quicksand, quacking b) open, opener, opera, operand, opened c) zoo, zero, zoom, zoology, zoological

(Requires calculus) a) Let \(n\) be a positive integer. Show that the relation \(R\) on the set of all polynomials with real-valued coefficients consisting of all pairs \((f, g)\) such that \(f^{(n)}(x)=g^{(n)}(x)\) is an equivalence relation. [Here \(f^{(n)}(x)\) is the \(n\) th derivative of \(f(x) . ]\) b) Which functions are in the same equivalence class as the function \(f(x)=x^{4},\) where \(n=3 ?\)

Let \(R\) be the relation on the set of all people who have visited a particular Web page such that \(x R y\) if and only if person \(x\) and person \(y\) have followed the same set of links starting at this Web page (going from Web page to Web page until they stop using the Web). Show that \(R\) is an equivalence relation.

Draw the Hasse diagram for the greater than or equal to relation on \(\\{0,1,2,3,4,5\\}\)