Skip to main content

Exercises 13.4 Exercises

1.

Let \(X=\{a,b,c,d\}\) and the relation \(R\) on \(X\) be defined by

\begin{equation*} R = \{(a,b),(a,d),(b,d),(c,c)\}. \end{equation*}

Calculate the reflexive closure of \(R\text{.}\)

2.

Let \(X=\{a,b,c,d\}\) and the relation \(R\) on \(X\) be defined by

\begin{equation*} R = \{(a,b),(a,d),(b,d),(c,c)\}. \end{equation*}

Calculate the symmetric closure of \(R\text{.}\)

3.

Let \(X=\{a,b,c,d\}\) and the relation \(R\) on \(X\) be defined by

\begin{equation*} R = \{(a,b),(a,d),(b,d),(c,c)\}. \end{equation*}

Calculate the transitive closure of \(R\text{.}\)

4.

Let \(Y=\{a,b,c,d,e\}\) and the relation \(S\) on \(Y\) be defined by

\begin{equation*} S = \{(a,b),(b,d),(c,d),(d,c),(d,e),(e,a)\}. \end{equation*}

Calculate the reflexive closure of \(S\text{.}\)

5.

Let \(Y=\{a,b,c,d,e\}\) and the relation \(S\) on \(Y\) be defined by

\begin{equation*} S = \{(a,b),(b,d),(c,d),(d,c),(d,e),(e,a)\}. \end{equation*}

Calculate the symmetric closure of \(S\text{.}\)

6.

Consider the relation

\begin{equation*} R = \{(a,c),(b,a),(b,b),(c,f),(d,e),(e,d)\} \end{equation*}

on the set \(X = \{a,b,c,d,e,f\}\text{.}\) Calculate the symmetric closure of \(R\text{.}\)

7.

Consider the relation

\begin{equation*} R = \{(a,c),(b,a),(b,b),(c,f),(d,e),(e,d)\} \end{equation*}

on the set \(X = \{a,b,c,d,e,f\}\text{.}\) Calculate the transitive closure of \(R\text{.}\)

8.

Consider the relation

\begin{equation*} R=\{ (1,1), (1,5), (2,1), (2,3), (3,1), (4,4), (5,1) \} \end{equation*}

on \(X=\{1,2,3,4,5\}\text{.}\) Calculate the reflexive closure of \(R\text{.}\)

9.

Consider the relation

\begin{equation*} R=\{ (1,1), (1,5), (2,1), (2,3), (3,1), (4,4), (5,1) \} \end{equation*}

on \(X=\{1,2,3,4,5\}\text{.}\) Calculate the symmetric closure of \(R\text{.}\)

10.

Consider the relation

\begin{equation*} R=\{ (1,1), (1,5), (2,1), (2,3), (3,1), (4,4), (5,1) \} \end{equation*}

on \(X=\{1,2,3,4,5\}\text{.}\) Calculate the transitive closure of \(R\text{.}\)

11.

Consider the relation \(R\) on the set \(\{x_1, x_2, x_3, x_4, x_5\}\) given by

\begin{equation*} R = \{(x_1,x_4), (x_2,x_4), (x_3,x_2), (x_3,x_3), (x_4,x_2), (x_4,x_5), (x_5,x_5)\}. \end{equation*}

  1. What pairs must you add to \(R\) to construct its reflexive closure?

  2. What pairs must you add to \(R\) to construct its symmetric closure?

  3. What pairs must you add to \(R\) to construct its transitive closure?

12.

What is the reflexive closure of the relation described by \(x \lt y\) on \(\mathbb{Z}\text{?}\)

Hint.

Your answer should be a statement like \(x \lt y\) that describes the reflexive closure of the relation. If you are having trouble starting, consider the set \(\{1,2,3,4,5\}\) instead of \(\mathbb{Z}\) and write the ordered pairs out.

13.

What is the symmetric closure of the relation described by \(x \lt y\) on \(\mathbb{Z}\text{?}\)

Hint.

See above hint.

14.

Let \(R\) and \(S\) be relations on \(X = \{x_1, x_2, x_3\}\) represented by the matrices

\begin{equation*} M_R = \left( \begin{array}{ccc} 1 \amp 0 \amp 1 \\ 0 \amp 0 \amp 1 \\ 1 \amp 1 \amp 0 \end{array} \right) \qquad M_S = \left( \begin{array}{ccc} 0 \amp 0 \amp 0 \\ 1 \amp 1 \amp 0 \\ 1 \amp 0 \amp 1 \end{array}\right). \end{equation*}

  1. a) Write down \(RS\) as a set of ordered pairs.

  2. b) Write down \(SR\) as a set of ordered pairs.

15.

Let \(R\) and \(S\) be relations on the set \(\{a,b,c,d\}\) with matrices given below:

\begin{equation*} M_R = \left( \begin{array}{cccc} 0 \amp 1 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \\ 1 \amp 1 \amp 1 \amp 0 \\ 1 \amp 0 \amp 1 \amp 0 \end{array} \right) \qquad M_S = \left( \begin{array}{cccc} 1 \amp 0 \amp 0 \amp 0 \\ 1 \amp 1 \amp 0 \amp 0 \\ 1 \amp 1 \amp 1 \amp 0 \\ 1 \amp 1 \amp 1 \amp 1 \end{array} \right) \end{equation*}

  1. a) Write down \(RS\) as a set of ordered pairs.

  2. b) Write down \(SR\) as a set of ordered pairs.

16.

Let

\begin{equation*} S = \{(a,b),(b,a),(b,d),(b,e),(b,f), (c,c),(d,e),(f,c),(f,f)\} \end{equation*}

be a relation on the set \(\{a,b,c,d,e,f\}\text{.}\) Write the relation \(S^2\) as a set of ordered pairs.

17.

Consider the relation \(R\) on the set \(\{u,v,w,x,y\}\) where

\begin{equation*} R = \{(u,v), (v,w), (v,y), (w,u), (x,y), (y,x)\}. \end{equation*}

Calculate \(R^2\) and express your answer as a set of ordered pairs.

18.

Let \(X=\{x_1,x_2,x_3,x_4\}\text{,}\) \(Y=\{y_1,y_2,y_3\}\text{,}\) and \(Z=\{z_1,z_2\}\text{.}\) Let \(R\) be the relation from \(X\) to \(Z\) with \(R=\{(x_1,z_1),(x_2,z_2),(x_3,z_1),(x_3,z_2)\}\text{.}\) Let \(S\) be the relation from \(Y\) to \(X\) where \(S = \{(y_1,x_4),(y_1,x_1),(y_2,x_3),(y_3,x_2)\}\text{.}\)

  1. Write down the matrices \(M_R\) and \(M_S\text{.}\) Order the rows and columns numerically.

  2. Write down the composition \(SR\) as a set of ordered pairs.

19.

Let \(A=\{a_1,a_2,a_3\}\text{,}\) \(B=\{b_1,b_2,b_3,b_4\}\text{,}\) and \(C=\{c_1,c_2\}\text{.}\) Let \(R\) and \(S\) be the relations between these sets given by

\begin{equation*} R = \{(a_1,b_2),(a_1,b_3),(a_2,b_1),(a_3,b_3)\} \end{equation*}

and

\begin{equation*} S = \{(b_2,c_1),(b_3,c_1),(b_3,c_2),(b_4,c_1)\} \end{equation*}

  1. Write down the matrices \(M_R\) and \(M_S\text{.}\) Order the rows and columns numerically.

  2. Write down the composition \(SR\) as a set of ordered pairs.

20.

Why is there no such thing as an antireflexive closure?

21.

Why is there no such thing as an antisymmetric closure, and why is this idea actually less useful than the idea of an antireflexive closure?