Chapter 6

(a) Let \(B=\\{a, b\\}\) and \(U=\mathcal{P}(B)\). Draw a Hasse diagram for \(\subseteq\) on \(U\). (b) Let \(A=\\{1,2,3,6\\} .\) Show that divides, \(\mid,\) is a partial ordering on \(A\). (c) Draw a Hasse diagram for divides on \(A\). (d) Compare the graphs of parts a and \(\mathrm{c}\).

Let \(A_{1}=\\{1,2,3,4\\}, A_{2}=\\{4,5,6\\},\) and \(A_{3}=\\{6,7,8\\} .\) Let \(r_{1}\) be the relation from \(A_{1}\) into \(A_{2}\) defined by \(r_{1}=\\{(x, y) \mid y-x=2\\},\) and let \(r_{2}\) be the relation from \(A_{2}\) into \(A_{3}\) defined by \(r_{2}=\\{(x, y) \mid y-x=1\\}\). (a) Determine the adjacency matrices of \(r_{1}\) and \(r_{2}\). (b) Use the definition of composition to find \(r_{1} r_{2}\). (c) Verify the result in part b by finding the product of the adjacency matrices of \(r_{1}\) and \(r_{2}\)

Let \(A=\\{1,2,3,4\\},\) and let \(r\) be the relation \(\leq\) on \(A\). Draw a digraph for \(r\)

For each of the following relations \(r\) defined on \(\mathbb{P}\), determine which of the given ordered pairs belong to \(r\) (a) \(x r y\) iff \(x \mid y ;(2,3),(2,4),(2,8),(2,17)\) (b) \(x r y\) iff \(x \leq y ;(2,3),(3,2),(2,4),(5,8)\) (c) \(x r y\) iff \(y=x^{2} ;(1,1),(2,3),(2,4),(2,6)\)

Let \(B=\\{1,2,3,4,6,8,12,24\\},\) and let \(s\) be the relation "divides" on \(B\). Draw a digraph for \(s\).

The following relations are on \\{1,3,5\\} . Let \(r\) be the relation \(x r y\) iff \(y=x+2\) and \(s\) the relation \(x s y\) iff \(x \leq y\) (a) List all elements in \(r s\). (b) List all elements in \(s r\). (c) Illustrate \(r s\) and sr via a diagram. (d) Is the relation \(r s\) equal to the relation \(s r ?\)

Let \(A=\\{1,2,3,4,5\\} .\) Define \(t\) on \(A\) by atb if and only if \(b-a\) is even. Draw a digraph for \(t\).

Let \(A=\\{1,2,3,4,5\\}\) and define \(r\) on \(A\) by \(x r y\) iff \(x+1=y .\) We define \(r^{2}=r r\) and \(r^{3}=r^{2} r .\) Find: (a) \(r\) (b) \(r^{2}\) (c) \(r^{3}\)

Determine which of the following are equivalence relations and/or partial ordering relations for the given sets: (a) \(A=\\{\) lines in the plane \(\\}\), and \(r\) defined by \(x r y\) if and only if \(x\) is parallel to \(y\). Assume every line is parallel to itself. (b) \(A=\mathbb{R}\) and \(r\) defined by \(x r y\) if and only if \(|x-y| \leq 7\).

Let \(A\) be the set of strings of \(0^{\prime} s\) and \(1^{\prime} s\) of length 3 or less. (a) Define the relation of \(d\) on \(A\) by \(x d y\) if \(x\) is contained within \(y\). For example, 01d101. Draw a digraph for this relation. (b) Do the same for the relation \(p\) defined by \(x p y\) if \(x\) is a prefix of \(y\). For example, \(10 p 101\), but \(01 p 101\) is false.

Given \(s\) and \(t,\) relations on \(\mathbb{Z}, s=\\{(1, n): n \in \mathbb{Z}\\}\) and \(t=\\{(n, 1): n \in \mathbb{Z}\\},\) what are st and \(t s ?\) Hint: Even when a relation involves infinite sets, you can often get insights into them by drawing partial graphs.

Consider the relation on \\{1,2,3,4,5,6\\} defined by \(r=\\{(i, j):|i-j|=\) 2\\} (a) Is \(r\) reflexive? (b) Is \(r\) symmetric? (c) Is \(r\) transitive? (d) Draw a graph of \(r\).

How many different reflexive, symmetric relations are there on a set with three elements? Hint. Consider the possible matrices.

Let \(\rho\) be the relation on the power set, \(\mathcal{P}(S),\) of a finite set \(S\) of cardinality \(n\) defined \(\rho\) by \((A, B) \in \rho\) iff \(A \cap B=\emptyset\) (a) Consider the specific case \(n=3\), and determine the cardinality of the set \(\rho\) (b) What is the cardinality of \(\rho\) for an arbitrary \(n ?\) Express your answer in terms of \(n\).

For the set of cities on a map, consider the relation \(x r y\) if and only if city \(x\) is connected by a road to city \(y .\) A city is considered to be connected to itself, and two cities are connected even though there are cities on the road between them. Is this an equivalence relation or a partial ordering? Explain.

Let \(A=\\{a, b, c, d\\}\). Let \(r\) be the relation on \(A\) with adjacency matrix \(\begin{array}{llll}a & b & c & d\end{array}\) $$ \begin{array}{l} a \\ b \\ c \\ d \end{array}\left(\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right) $$ (a) Explain why \(r\) is a partial ordering on \(A\). (b) Draw its Hasse diagram.

Let \(C=\\{1,2,3,4,6,8,12,24\\}\) and define \(t\) on \(C\) by atb if and only if \(a\) and \(b\) share a common divisor greater than 1. Draw a digraph for \(t\).

What common relations on \(\mathbb{Z}\) are the transitive closures of the following relations? (a) \(a S b\) if and only if \(a+1=b\). (b) \(a R b\) if and only if \(|a-b|=2\).

Let \(r_{1}, r_{2},\) and \(r_{3}\) be relations on any set \(A .\) Prove that if \(r_{1} \subseteq r_{2}\) then \(r_{1} r_{3} \subseteq r_{2} r_{3}\)

Equivalence Classes. Let \(A=\\{0,1,2,3\\}\) and let $$ r=\\{(0,0),(1,1),(2,2),(3,3),(1,2),(2,1),(3,2),(2,3),(3,1),(1,3)\\} $$ (a) Verify that \(r\) is an equivalence relation on \(A\). (b) Let \(a \in A\) and define \(c(a)=\\{b \in A \mid\) arb \(\\} . \quad c(a)\) is called the equivalence class of \(a\) under \(r\). Find \(c(a)\) for each element \(a \in A\). (c) Show that \(\\{c(a) \mid a \in A\\}\) forms a partition of \(A\) for this set \(A\). (d) Let \(r\) be an equivalence relation on an arbitrary set \(A\). Prove that the set of all equivalence classes under \(r\) constitutes a partition of \(A\).

(a) Let \(A\) be any set and \(r\) a relation on \(A,\) prove that \(\left(r^{+}\right)^{+}=r^{+}\). (b) Is the transitive closure of a symmetric relation always both symmetric and reflexive? Explain.

Define \(r\) on the power set of \\{1,2,3\\} by \(A r B \Leftrightarrow|A|=|B| .\) Prove that \(r\) is an equivalence relation. What are the equivalence classes under \(r ?\)

(a) Prove that if \(r\) is a transitive relation on a set \(A,\) then \(r^{2} \subseteq r\) (b) Find an example of a transitive relation for which \(r^{2} \neq r\).

The definition of the Transitive Closure of \(r\) refers to the "smallest transitive relation that contains \(r\) as a subset." Show that the intersection of all transitive relations on \(A\) containing \(r\) is a transitive relation containing \(r\) and is precisely \(r^{+}\).

Consider the following relations on \(\mathbb{Z}_{8}=\\{0,1, \ldots, 7\\}\). Which are equivalence relations? For the equivalence relations, list the equivalence classes. (a) arb iff the English spellings of \(a\) and \(b\) begin with the same letter. (b) asb iff \(a-b\) is a positive integer. (c) atb iff \(a-b\) is an even integer.

We define \(\leq\) on the set of all \(n \times n\) relation matrices by the rule that if \(R\) and \(S\) are any two \(n \times n\) relation matrices, \(R \leq S\) if and only if \(R_{i j} \leq S_{i j}\) for all \(1 \leq i, j \leq n\). (a) Prove that \(\leq\) is a partial ordering on all \(n \times n\) relation matrices. (b) Prove that \(R \leq S \Rightarrow R^{2} \leq S^{2},\) but the converse is not true. (c) If \(R\) and \(S\) are matrices of equivalence relations and \(R \leq S,\) how are the equivalence classes defined by \(R\) related to the equivalence classes defined by \(S ?\)