EF Exercises

Skip to main content

Exercises 18.7 Exercises

1.

Let

\equiv

represent the relation on

R \times R

where

(x_{1}, y_{1}) \equiv (x_{2}, y_{2})

means

y_{1} - x_{1}^{2} = y_{2} - x_{2}^{2} .

(a)

Verify that

\equiv

is an equivalence relation.

(b)

Describe the equivalence classes

[(0, 0)],

[(0, 1)],

and

[(1, 0)]

geometrically as sets of points in the plane.

2.

Given a connected (undirected) graph

G,

we can define a relation on the set

V

of vertices in

G

as follows: let

v_{1} R v_{2}

mean that there exists a trail within

G

beginning at vertex

v_{1}

and ending at vertex

v_{2}

that traverses an even number of edges.

(a)

Prove that

R

is an equivalence relation on

V .

(b)

Determine the equivalence classes for this relation when

G

is the graph below.

An example graph for vertices equivalent when connected by an “even” trail.

Equivalence relations and classes.

In each of Exercises 3–12, you are given a set

A

and a relation

R

on

A .

Determine whether

R

is an equivalence relation, and, if it is, describe its equivalence classes. Try to be more descriptive than just “

[a]

is the set of all elements that are equivalent to

a .

”

3.

A = {a, b, c};

R = {(a, a), (b, b), (c, c), (a, b), (b, a)} .

4.

A = {- 1, 0, 1};

R = {(x, y) | x^{2} = y^{2}} .

5.

A

is the power set of some set;

R

is the subset relation.

6.

A = R;

x_{1} R x_{2}

means

f (x_{1}) = f (x_{2}),

where

f : R \to R

is the function

f (x) = x^{2} .

7.

A

is some abstract set;

a_{1} R a_{2}

means

f (a_{1}) = f (a_{2}),

where

f : A \to B

is an arbitrary function with domain

A .

8.

A

is the set of all “formal” expressions

a / b,

where

a, b

are integers and

b

is nonzero;

(a / b) R (c / d)

means

a d = b c .

Note: Do not think of

a / b

as a fraction in the usual way; instead think of it as a collection of symbols consisting of two integers in a specific order with a forward slash between them.

9.

A

is the power set of some finite set;

X R Y

means

| X | = | Y | .

10.

A

is the set of all straight lines in the plane;

L_{1} R L_{2}

means

L_{1}

is parallel to

L_{2} .

11.

A

is the set of all straight lines in the plane;

L_{1} R L_{2}

means

L_{1}

is perpendicular to

L_{2} .

12.

A = R \times R;

(x_{1}, y_{1}) R (x_{2}, y_{2})

means

x_{1}^{2} + y_{1}^{2} = x_{2}^{2} + y_{2}^{2} .

Does the expression

x^{2} + y^{2}

remind you of anything from geometry?

<Prev ^Top Next>