Relations and Graphs (Home Work)

Question

1. Let A= {-2, -1, 0, 1, 2}. Let r be the relation defined by xry if and only if y=-x . Let S be the relation defined by xsy if and only if y= |x|.

(a) Write down as a subset of A X A .

(b) Write down as a subset of AXA.

(c) With rows and columns labelled in the order (-2, -1, 0, 1, 2) , write down the adjacency matrix of r.

(d) With rows and columns labelled in the order (-2, -1, 0, 1, 2) , write down the adjacency matrix of s.

(e) Using your answers to parts (c) and (d) calculate the adjacency matrix of the relation rs.

(f) Using your answers to parts (c) and (d) calculate the adjacency matrix of the relation sr.

(g) From the solutions to parts (e) and (f) which property, associated with multiplication on numbers, is lacking for the operation of composition for relations?

 

 

2. Let  A = {(1,2), (2,4), (3,6), (1,4), (2,8), (3,12), (1,3), (2,6), (3,4)}. Let r by the relation defined by (a,b)r(c,d) if and only if  ad = bc.

 

(a) The relation r is reflexive. Give one example of two elements of r (not A ) that demonstrate the reflexive property. Show clearly that the elements you choose satisfy the reflexive property.

(b) The relation r is symmetric. Give one example of two elements of r (not A) that demonstrate the symmetric property. Show clearly that the elements you choose satisfy the symmetric property.

(c) The relation r is transitive. Give one example of three elements of r (not A) that demonstrate the transitive property.  Show clearly that the elements you choose satisfy the transitive property.

(d) As r is reflexive, symmetric and transitive it follows that r is an equivalence relation. What are the equivalence classes of r ?

Answer 1

Jude,

 

Sorry for the delay in replying. Here is some help.

 

1a) The relation r as a subset of A×A: {(-2,2), (-1,1), (0,0), (1,-1), (2,-2)}.

1b) The relation s as a subset of A×A: {(-2,2), (-1,1), (0,0), (1,1), (2,2)}.

1c) Strictly speaking, what you are being asked is not the adjacency matrix. The adjacency matrix is used to represent a graph numerically. Even so, you can construct the matrix as requested by listing the elements of A (in increasing order) down the left side of the matrix and across the top of the matrix. You put a 1 for each ordered pair (x,y) in row x and column y. The matrix which results is:

 

[0 0 0 0 1

 0 0 0 1 0

 0 0 1 0 0

 0 1 0 0 0

 1 0 0 0 0]

 

1d) Similarly, the required matrix is:

 

[0 0 0 0 1

 0 0 0 1 0

 0 0 1 0 0

 0 0 0 1 0

 0 0 0 0 1]

 

1e)

 

[1 0 0 0 0

 0 1 0 0 0

 0 0 1 0 0

 0 0 0 1 0

 0 0 0 0 01]

 

1f) The matrix for this relation is the same as that in 1c).

 

1g) The Commutative property, since rs ≠ sr.

 

2a) The wording in this question is a little confusing. In order to demonstrate the reflexive property, you need only choose one ordered pair in A and check that it is related to itself. I am not sure whether you need to verify this twice or not, so I will show you one and leave the other to you, if you actually need it. Choosing the element (1,2) from A, one can see that (1,2)r(1,2) because 1·2 = 2·1. The element of r which corresponds to this relationship is ((1,2), (1,2)).

 

You will get another example by choosing any other element of A and repeating what I just showed you.

 

2b) Choosing the two elements (1,2) and (2,4) from A, you can check that (1,2)r(2,4) and that (2,4)r(1,2) are both true. Thus, (1,2)r(2,4) implies (2,4)r(1,2), demonstrating the symmetric property.

 

2c) Choosing (1,2), (2,4), and (3,6), one can see that (1,2)r(2,4) and (2,4)r(3,6), and also that (1,2)r(3,6) using the definition of the relation r. This, the transitive property is shown because the first two relationships imply the last one.

 

2d) To find the equivalence classes, you must find all elements of A which are related to each other. It can be done by trial and error, or by systematically verifying that for any (x,y), y = kx, for a constant k specific to the equivalence class.

 

Here are the four equivalence classes:

 

E₁ = {(1,2), (2,4), (3,6)}  (y = 2x for each ordered pair)

E₂ = {(1,4), (2,8), (3,12)}  (y = 4x for each)

E₃ = {(1,3), (2,6)}  (y = 3x for each)

E₄ = {(3,4)}  (there are no other ordered pairs related to (3,4), so it is its own equivalence class).

 

If you require more explanation, do not hesitate to ask in a later post.