17.6: Exercises
- Page ID
- 93823
Directed graph for a relation.
In each of Exercises 1–4, you are given a relation on a specific set. Draw a directed graph that represents the relation.
Relation \(\subsetneqq\) on \(\mathscr{P}(\{a,b,c\})\text{.}\)
Relation \(\lt\) on \(\{1,2,3,4\}\text{.}\)
Relation \(\equiv_3\) on \(\mathbb{N}_{<13}\text{.}\)
Relation “has the same number of occurrences of the letter \(\mathrm{a}\) as” on \(\Sigma^\ast_4\) for alphabet \(\Sigma = \{a, z\}\text{.}\)
Recall that a relation on a set \(A\) is just a subset of the Cartesian product \(A \times A\text{.}\) Write out all relations on the set \(A = \{a,b\}\) as subsets of \(A \times A\text{.}\) Which of these relations are reflexive? Symmetric? Antisymmetric? Transitive?
Testing reflexivity/symmetry/antisymmetry/transitivity.
In each of Exercises 6–17, you are given a relation on a specific set. Determine which of the properties reflexive, symmetric, antisymmetric, and transitive the given relation possesses.
Relation \(\lt\) on \(\mathbb{R}\text{.}\)
Relation \(\mathord{\ge}\) on \(\mathbb{R}\text{.}\)
Relation \(\mathord{\vert}\) on \(\mathbb{Z}\text{.}\)
Relation \(\mathord{\subseteq}\) on \(\mathscr{P}{X}\text{,}\) where \(X\) is an arbitrary, unspecified set.
Relation “is taller than” on the set of all living humans.
Relation “is parallel to” on the set of all straight lines in the plane.
Relation “is perpendicular to” on the set of all straight lines in the plane.
Relation “has the same length as” on \(\Sigma^\ast\text{,}\) where \(\Sigma\) is an arbitrary, unspecified alphabet set.
Relation “is shorter than” on \(\Sigma^\ast\text{,}\) where \(\Sigma\) is an arbitrary, unspecified alphabet set.
Relation “contains the same number of occurrences of the letter \(x\) as” on \(\Sigma^\ast\text{,}\) where \(\Sigma\) is an arbitrary, unspecified alphabet set and \(x\) is some fixed choice of letter in \(\Sigma\text{.}\)
Relation \(\Leftrightarrow\) on the set of all logical statements involving the statement variables \(p_1,p_2,p_3,\ldots\text{.}\)
Relation \(R\) defined by “\(a_1 \mathrel{R} a_2\) if \(f(a_1) = f(a_2)\)” on a set \(A\text{,}\) where \(f: A \rightarrow B\) is an arbitrary, unspecified function.
Properties of relations reflected in their graphs.
In each of Exercises 18–19, you are given a list of properties. Draw the directed graph of a relation on the set \(\{a,b,c,d\}\) that possesses the given properties.
Symmetric and transitive, but neither reflexive nor antisymmetric.
Reflexive, antisymmetric, and transitive, but not symmetric.
Prove that a relation is symmetric if and only if it is equivalent to its own inverse relation.
As described in Section 17.3, the definition of antisymmetric relation can be formulated in symbolic language as
\begin{equation*} (\forall a_1 \in A)(\forall a_2 \in A)(a_1 \neq a_2 \Rightarrow a_1\ \not R\ a_2 \lor a_2\ \not R\ a_1) \text{.} \end{equation*}
Prove that each of the two conditionals provided in the Antisymmetric Relation Test are equivalent to the symbolic formulation of the definition of antisymmetric given above.
Suppose \(R\) is a relation on a set \(A\) that is both symmetric and antisymmetric. Prove that \(R\) is a subset of the identity relation \(\{(x,x)\vert x \in A\}\text{.}\)