Answer to Question #267851 in Discrete Mathematics for Jaishree

Question

Determine whether the relation R on the set of all

Web pages is reflexive, symmetric, antisymmetric, and/or

transitive, where (a, b) ∈ R if and only if

a) everyone who has visited Web page a has also visited

Web page b.

b) there are no common links found on both Web

page a and Web page b.

c) there is at least one common link on Web page a and

Web page b.

d) there is a Web page that includes links to both Web

page a and Web page b.

Answer 1

The relation is reflexive if every element in A, (a,a) exists in the relation.

The relation is symmetric if (a,b)∈R whenever (b,a)∈R

The relation is antisymmetric if the existence of (a,b) and (b,a) indicates that a=b

The relation is transitive if (a,b)∈R and (b,c)∈R then (a,c)∈R

Assume A= set of all webpages

a)

If a person has visited webpage A then he has visited webpage. So, (a,a)∈R

 for every element in A. Thus, the relation is reflexive.

It is possible that some people has visited webpage B but not has visited webpage A. So, the relation is not symmetric.

If everyone who has visited webpage A has also visited webpage B and If everyone who has visited webpage B has also visited webpage A, then these webpages are equal. So, the relation is not antisymmetric.

If everyone who has visited webpage A has also visited webpage B and If everyone who has visited webpage B has also visited webpage C, then everyone who has visited webpage A has also visited webpage C. Thus, the relation is transitive.

b)

The relation will always have a common link to itself. So, the relation is not reflexive.

If webpage A and webpage B have no common link then, webpage B and webpage A will also have no common link. So, the relation is symmetric.

If webpage A and webpage B has no common link and webpage B and webpage A has no common link, then it is not necessary that these webpages are equal. So, the relation is not anitsymmetric.

If webpage A and webpage B has no common link and webpage B and webpage C has no common link, then it is possible that webpage A and webpage B has some common link. So, the relation is not transitive.

c)

All elements in A will have not common link with itself. So, the relation is not reflexive.

If webpage A and webpage B has one common link, then webpage A and webpage B will also has one common link. So, the relation is symmetric.

If webpage A and webpage B has one common link and webpage B and webpage A has one common link, then it is not necessary that these webpages are equal. So, the relation is not antisymmetric.

If webpage A and webpage B has one common link and webpage B and webpage C has one common link, then it is not necessary that webpage A and webpage C has one common link. So, the relation is not transitive.

d)

NOT Reflexive: (a,b) ∈ R, if there exist a web-page (say web-page m) such that m has links for both web-page a and web-page b . Now, 

     (a, a) need not belong to R, as the could be no web-page pointing to web-page a.

   (II) Symmetric: if (a, b) ∈ R, i.e there is a web-page linking to web-page a and web-page b, then (b,a) ∈ R. Hence, Symmetric.

    (III) NOT Transitive: If ( a, b) ∈ R, and (b, c) ∈ then it is not necessary that (a,c)∈ R. If web-page e points to web-page a and web-page b,      web-page f points to web-page b and web-page c then it is not necessary that there exit a web-page which'll point to both web-page a and 

     web-page c.

    (IV) NOT Antisymmetric: As it is symmetric.