Test: Types of Relations - Computer Science Engineering (CSE) MCQ

Concept: 
Reflexive relation: Relation is reflexive If (a, a) ∈ R ∀ a ∈ A.
Symmetric relation: Relation is symmetric, If (a, b) ∈ R, then (b, a) ∈ R.
Transitive relation: Relation is transitive, If (a, b) ∈ R & (b, c) ∈ R, then (a, c) ∈ R,
If the relation is reflexive, symmetric, and transitive, it is known as an equivalence relation.

Explanation:
Given that, A = {1, 2, 3} and R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1,3)}.
Now,
 (1,1),(2,2),(3,3) ∈ R
⇒ R is reflexive.
(1,2),(2,3),(1,3) ∈ R but (2,1),(3,2),(3,1) ∉ R
⇒ R is not symmetric.
Also, (1,2) ∈ R and (2,3) ∈ R ⇒ (1,3) ∈ R
⇒ R is transitive.
∴ R is reflexive, and transitive but not symmetric.

Concept: 
Reflexive relation: Relation is reflexive If (a, a) ∈ R ∀ a ∈ A.
Symmetric relation: Relation is symmetric, If (a, b) ∈ R, then (b, a) ∈ R.
Transitive relation: Relation is transitive, If (a, b) ∈ R & (b, c) ∈ R, then (a, c) ∈ R,
If the relation is reflexive, symmetric, and transitive, it is known as an equivalence relation.

Explanation:
Let A = {1, 2, 3}
The relation R is defined by R = {(1, 2)}
Since, (1, 1) ∉ R
∴ It is not reflexive.
Since, (1, 2) ∈ R but (2, 1) ∉ R
∴ It is not symmetric.
But there is no counter-example to disapprove of transitive condition.
∴ It is transitive.

Not reflexive -> (3,3) not present; not irreflexive -> (1, 1) is present; not symmetric -> (2, 1) is present but not (1, 2); not antisymmetric – (2, 3) and (3, 2) are present; not asymmetric -> asymmetry requires both antisymmetry and irreflexivity. So, it is transitive closure of relation.

For a set with k elements the number of binary relations should be 2^(n*n) and the number of functions should be nⁿ. Now, 2^(n*n) => n²log (2) [taking log] and nⁿ => nlog (n) [taking log]. It is known that n²log (2) > nlog (n). Hence, the number of binary relations > the number of functions i.e, N_r > N_f.

Calculation of transitive closure results into matrix multiplication. We can do matrix multiplication in O(n³) time. There are better algorithms that do less than cubic time.

Since, x² = y² is just a special case of equality, so all properties that apply to x = y also apply to this case. Hence, the relation satisfies symmetric, reflexive and transitive closure.

A relation is asymmetric if and only if it is both antisymmetric and irreflexive. As a consequence, a relation is transitive and asymmetric if and only if it is a strict partial order. If D(A) is a diagonal of A set and intersection of D(A) and R is empty, then R is asymmetric.

Concept:
If x ∈  R then we express it by writing xRy and say that " x is related to y with relation R"
Thus, (x, y) ∈ R ⇔ xRy

Calculation:
Given
2x + 3y = 20
The relation R can be written as
R = {(1,6), (4, 4), (7, 2)}
There are 3 elements in the form (x, y) are there in R.

Concept:
1. Reflexive: Each element is related to itself.
R is reflexive if for all x ∈ A, xRx.
2. Symmetric: If any one element is related to any other element, then the second element is related to the first.
R is symmetric if for all x, y ∈ A, if xRy, then yRx.
3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.
R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.
4. R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:
For reflexive:
(a, a) = a – a = 0 is divisible by 3.
For symmetric:
If (a - b) is divisible by 3, then (b – a) = - (a - b) is also divisible by 3.
Thus relation is symmetric.
For transitive:
If (a - b) and (b - c) is divisible by 3
Then (a - c) is also divisible by 3
Thus relation is transitive.
∴ R is an equivalence relation
Hence, option (d) is correct.

In terms of set theory, the binary relation R defined on the set X is a transitive relation if, for all a, b, c ∈ X, if aRb and bRc, then aRc. If there are two relations on a set satisfying transitive property then there union must satisfy transitive property.