Exercises 17.6 Exercises
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.
5.
Recall that a relation on a set is just a subset of the Cartesian product Write out all relations on the set as subsets of 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.
6.
7.
8.
9.
10.
Relation βis taller thanβ on the set of all living humans.
11.
Relation βis parallel toβ on the set of all straight lines in the plane.
12.
Relation βis perpendicular toβ on the set of all straight lines in the plane.
13.
14.
15.
Relation βcontains the same number of occurrences of the letter asβ on where is an arbitrary, unspecified alphabet set and is some fixed choice of letter in
16.
17.
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 that possesses the given properties.
20.
Prove that a relation is symmetric if and only if it is equivalent to its own inverse relation.
21.
As described in Section 17.3, the definition of antisymmetric relation can be formulated in symbolic language as
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.
22.
Suppose is a relation on a set that is both symmetric and antisymmetric. Prove that is a subset of the identity relation