Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

17.6: Exercises

( \newcommand{\kernel}{\mathrm{null}\,}\)

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.

Exercise 17.6.1

Relation on P({a,b,c}).

Exercise 17.6.2

Relation < on {1,2,3,4}.

Exercise 17.6.3

Relation 3 on N<13.

Exercise 17.6.4

Relation “has the same number of occurrences of the letter a as” on Σ4 for alphabet Σ={a,z}.

Exercise 17.6.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.

Exercise 17.6.6

Relation < on R.

Exercise 17.6.7

Relation on R.

Exercise 17.6.8

Relation | on Z.

Exercise 17.6.9

Relation on PX, where X is an arbitrary, unspecified set.

Exercise 17.6.10

Relation “is taller than” on the set of all living humans.

Exercise 17.6.11

Relation “is parallel to” on the set of all straight lines in the plane.

Exercise 17.6.12

Relation “is perpendicular to” on the set of all straight lines in the plane.

Exercise 17.6.13

Relation “has the same length as” on Σ, where Σ is an arbitrary, unspecified alphabet set.

Exercise 17.6.14

Relation “is shorter than” on Σ, where Σ is an arbitrary, unspecified alphabet set.

Exercise 17.6.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 Σ.

Exercise 17.6.16

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

Exercise 17.6.17

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

Exercise 17.6.18

Symmetric and transitive, but neither reflexive nor antisymmetric.

Exercise 17.6.19

Reflexive, antisymmetric, and transitive, but not symmetric.

Exercise 17.6.20

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

Exercise 17.6.21

As described in Section 17.3, the definition of antisymmetric relation can be formulated in symbolic language as

(a1A)(a2A)(a1a2a1  a2a2  a1).
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.

Exercise 17.6.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)|xA}.


This page titled 17.6: Exercises is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?