Skip to main content
Logo image

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.

4.

Relation β€œhas the same number of occurrences of the letter a as” on Ξ£4βˆ— for alphabet Ξ£={a,z}.

5.

Recall that a relation on a set A is just a subset of the Cartesian product AΓ—A. Write out all relations on the set A={a,b} as subsets of AΓ—A. 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.

9.

Relation βŠ† on P(X), where X is an arbitrary, unspecified set.

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.

Relation β€œhas the same length as” on Ξ£βˆ—, where Ξ£ is an arbitrary, unspecified alphabet set.

14.

Relation β€œis shorter than” on Ξ£βˆ—, where Ξ£ is an arbitrary, unspecified alphabet set.

15.

Relation β€œcontains the same number of occurrences of the letter x as” on Ξ£βˆ—, where Ξ£ is an arbitrary, unspecified alphabet set and x is some fixed choice of letter in Ξ£.

16.

Relation ⇔ on the set of all logical statements involving the statement variables p1,p2,p3,….

17.

Relation R defined by β€œa1Ra2 if f(a1)=f(a2)” on a set A, where f:Aβ†’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.

18.

Symmetric and transitive, but neither reflexive nor antisymmetric.

19.

Reflexive, antisymmetric, and transitive, but not symmetric.

20.

Prove that a relation is symmetric if and only if it is equivalent to its own inverse relation.

22.

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)|x∈A}.