Let’s start with the relevant definitions that will help us to solve this exercise.
Definition: “A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A.”
Definition: “A relation R on a set A is called symmetric if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.”
Definition: “A relation R on a set A is called transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A.”
The definitions above are from the textbook “Discrete Mathematics and its applications” By Rosen.
Table of Contents
- 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
a) everyone who has visited Web page a has also visited Web page b
Reflexive: Everyone who has visited Webpage a, has also visited Web page a. Therefore, it is Reflexive.
Symmetric: The fact that everyone who has visited web page a has also visited Web page b, does not mean that everyone who has visited b has also visited a.
Here is an example.
Person a and b visited both Web pages a and b. However, person c visited web page b but didn’t visit web page a. So, (b,a) ∉R because there is someone who visited web page b but didn’t visit web page a.
Antisymmetric: Let’s (a,b)∈R and (b,a) ∈R. Web pages a and b can still be different. Therefore, it is not antisymmetric.
Transitive: If everyone who has visited Webpage a, has also visited Web page b, and everyone who has visited Webpage b, has also visited Web page c, it follows that everyone who has visited web page has also visited web page c. Therefore, it is Transitive.
Answer: Reflexive, not symmetric, not antisymmetric, and transitive.
b) there are no common links found on both Web page a and Web page b
Reflexive: All links are common between a web page and itself. Therefore, not reflexive.
Symmetric: If there are no common links between web page and web page b, then there are no common links between web page b and web page a. Therefore, it is symmetric.
Antisymmetric: There might not be common links between different web pages. Therefore, not antisymmetric.
Transitive: Web pages a and b might not have common links, and web pages b and c might also not have any common links. But this does not mean that web pages a and c have no common links. Therefore, it is not transitive.
Answer: not reflexive, symmetric, not antisymmetric, and not transitive.
c) there is at least one common link on Web page a and Web page b
Reflexive: Some web pages have no links. Therefore, not reflexive.
Symmetric: If there is at least one common link between web pages a and b, then there is at least 1 common link between web pages b and a. Therefore, it is symmetric.
Antisymmetric: Two different web pages can have at least 1 common link. Therefore, not antisymmetric.
Transitive: not transitive. Same explanation as in the exercise above.
Answer: not reflexive, symmetric, not antisymmetric, and not transitive.
d) there is a Web page that includes links to both Web page a and Web page b
Reflexive: some web pages don’t have any links. Therefore, not reflexive.
Symmetric: if a web page a have links to both web pages a and b, the same web page will have links to both web pages b and a. Therefore, it is symmetric.
Antisymmetric: A web page can have links to two different web pages a and b. Therefore, not antisymmetric.
Transitive: not transitive.
Answer: not reflexive, symmetric, not antisymmetric, and not transitive.
Related exercises:
- Give an example of a relation on a set that is a) both symmetric and antisymmetric. b) neither symmetric nor antisymmetric
- Show that the relation R = ∅ on a nonempty set S is symmetric and transitive, but not reflexive
- Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y)∈R if and only if
- a) List all the ordered pairs in the relation R = {(a,b) | a divides b} on the set {1,2,3,4,5,6}. b) Display this relation graphically, as was done in Example 4. c)Display this relation in tabular form, as was done in Example 4
- Show that the relation R=∅ on the empty set S=∅ is reflexive, symmetric, and transitive