Let’s refresh 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.”
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.
A vacuous proof of a conditional statement p->q is a proof where we show that p is false, then the conditional statement must be true, according to the truth values for a conditional statement. This type of proof is usually used to prove special cases of some theorems.
Reflexive:
If x∈S, then (x,x)∈R for every element a ∈ A
x∈S is false because S=∅
Therefore, it is reflexive by vacuous proof.
Symmetric:
If (a,b)∈R, then (b,a)∈R for all a,b ∈ A
∀a,b (a,b)∉R
Therefore, it is symmetric by a vacuous proof.
Transitive:
If (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A
∀a,b (a,b)∉R, therefore (a,b)∈R and (b,c)∈R is false.
Therefore, it is transitive by a vacuous proof.
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
- 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
