GATE CSE 2015 | Set 3 | Question: 41

Question

Let $R$ be a relation on the set of ordered pairs of positive integers such that $((p,q),(r,s)) \in R$ if and only if $p-s=q-r$. Which one of the following is true about $R$?

• A. Both reflexive and symmetric
• B. Reflexive but not symmetric
• C. Not reflexive but symmetric
• D. Neither reflexive nor symmetric

Comments

Ans

---

Very Easy and Intutive Explanation 

Let the elements of the set be ordered pairs of positive integers i.e $\mathbf{R \subseteq (\mathbb{Z}^+ \times \mathbb{Z}^+) \times (\mathbb{Z}^+ \times \mathbb{Z}^+)}$:

$$x = (p,q), \qquad y = (r,s)$$

The relation $R$ is defined by:

$$(p,q) \, R \, (r,s) \iff p - s = q - r$$

1. Reflexive

A relation is reflexive if every element is related to itself:

$$xRx \quad \text{for all } x$$

• Verification: For an arbitrary pair $x = (p,q)$, we check:

  $$(p,q) \, R \, (p,q) \iff p - q = q - p \iff 2p = 2q \iff p = q$$

• Analysis: An ordered pair $(p,q)$ is related to itself only when $p = q$, not for every single ordered pair in the domain.

• Counterexample: Take the pair $(1,2)$.

  $$(1,2) \, R \, (1,2) \iff 1 - 2 = 2 - 1 \iff -1 = 1 \quad \text{(False)}$$

$\boxed{\text{Result: } R \text{ is not reflexive}}$

2. Irreflexive

A relation is irreflexive if no element is related to itself:

$$\neg(xRx) \quad \text{for all } x$$

• Analysis: Some elements in our domain do satisfy self-relation.

• Example: Take the pair $(1,1)$.

  $$(1,1) \, R \, (1,1) \iff 1 - 1 = 1 - 1 \iff 0 = 0 \quad \text{(True)}$$

$\boxed{\text{Result: } R \text{ is not irreflexive}}$

3. Symmetric

A relation is symmetric if:

$$xRy \implies yRx$$

• Proof: Assume $(p,q) \, R \, (r,s)$ holds true. This implies:

  $$p - s = q - r \implies p + r = q + s$$

• Rearranging this exact equation yields:

  $$r - q = s - p$$

• This is precisely the structural condition required for:

  $$(r,s) \, R \, (p,q)$$

$\boxed{\text{Result: } R \text{ is symmetric}}$

4. Antisymmetric

A relation is antisymmetric if:

$$xRy \text{ and } yRx \implies x = y$$

• Analysis: Since this relation is symmetric, if any two distinct elements are related once, they are automatically related both ways. It can only be antisymmetric if no two distinct pairs relate, which is not the case here.

• Counterexample: Take $x = (1,2)$ and $y = (2,1)$.

  $$(1,2) \, R \, (2,1) \iff 1 - 1 = 2 - 2 \iff 0 = 0 \quad \text{(True)}$$

  $$(2,1) \, R \, (1,2) \iff 2 - 2 = 1 - 1 \iff 0 = 0 \quad \text{(True)}$$

• However, $(1,2) \neq (2,1)$.

$\boxed{\text{Result: } R \text{ is not antisymmetric}}$

5. Asymmetric

A relation is asymmetric if:

$$xRy \implies \neg(yRx)$$

• Analysis: This property is impossible here because the relation has already been proven to be symmetric. If $xRy$ is true, then $yRx$ is always true.

• Counterexample: As shown above, $(1,2) \, R \, (2,1)$ and $(2,1) \, R \, (1,2)$ both hold simultaneously.

$\boxed{\text{Result: } R \text{ is not asymmetric}}$

6. Transitive

A relation is transitive if:

$$xRy \text{ and } yRz \implies xRz$$

• Analysis: We can disprove transitivity using a structural counterexample.

• Counterexample: Let $x = (1,2)$, $y = (2,1)$, and $z = (1,2)$.

  • We verified that $xRy \implies (1,2) \, R \, (2,1)$ is True.

  • We verified that $yRz \implies (2,1) \, R \, (1,2)$ is True.

• For transitivity to hold, we require $xRz \implies (1,2) \, R \, (1,2)$. However, as shown in the reflexivity check:

  $$(1,2) \, R \, (1,2) \iff 1 - 2 = 2 - 1 \iff -1 = 1 \quad \text{(False)}$$

$\boxed{\text{Result: } R \text{ is not transitive}}$

7. Equivalence Relation

An equivalence relation must simultaneously satisfy three structural properties: Reflexive, Symmetric, and Transitive.

• Analysis: Since this relation fails both reflexivity and transitivity, it cannot be classified as an equivalence relation.

$\boxed{\text{Result: } R \text{ is not an equivalence relation}}$

 

---

superb!!

Answer 1

The key trick here is to realize that the relation is of the form :

 {ordered pair, ordered pair} and not simply ordered pair.

Ok, so for reflexive

$\forall_{a,b}\, if((a,b),(a,b)) \in \mathrel{R} \rightarrow \text{reflexive}$

$((a,b),(a,b)) \in \mathrel{R} \;\leftrightarrow(a-b=b-a) $ (not possible for any postive integers b and a) 

But that is a contradiction hence it is not reflexive.

Now, for symmetric

$((a,b),(c,d))\in \mathrel{R}\rightarrow((c,d),(a,b))\in \mathrel{R}$

$((a,b),(c,d))\in\mathrel{R} \rightarrow(a-d=b-c)$

$((c,d),(a,b))\in\mathrel{R}$

$\because (c-b=d-a)\leftrightarrow (d-a=c-b)\leftrightarrow(-(a-d)=-(b-c))\leftrightarrow(a-d=b-c)$

So, it is symmetric.

Hence, C is the correct option.

Comments

If we take all symmetric pairs such as {((1,1)(1,1)),((2,2),(2,2)) and so on... according to que p-s=q-r will always be 0. Then how it is not reflexive?

---

we should check ((p,q),(p,q))∈R for reflexivity like (a,a)∈R for two elements, not ((p,p),(p,p))∈R

---

for reflexive, we need to check ((p,q),(p,q))∈R or not

for symmetric, we need to check whether (p,q) (r,s) ∈R then (r,s) (p,q) ∈R or not, it eventually fails,

also it is not transitive.

---

I tried to solve this taking these pairs as reference and got confused

Answer 2

1. take example for symmetric relation ... for p=6, q=4,r=4, s=6, (6,4)(4,6) 

p-s=6-6=0
q-r=4-4=0
so if we will check the condition (means p-s and q-r) for symmetric relation then p-s =q-r will b same always 

     
now we can see the relation (6,4)(4,6) is not reflexive but exist  in the relation R. so we can say that R may or may not b reflexive.
so option C is correct Not reflective but symmetric

 

Comments

if we take example (1,1) (2,2) then also it will give same value -1 after performing p-s and q-r  so now it seems like reflexive. plz correct me

---

no thats not reflexive!

when we say ((p,q)(r,s)) belongs to R means

{(1,1)(1,1) } or{ (2,2)(2,2)} should belong to R;

here first orederd pair is taken as first element and second ordered pair will be taken as second element;

it will not be reflexive as {(1,2)(1,2)} does not belongs to R;

hope it clears ur doubt!!

above relation is not reflexive ,symmetric and not transitive!!

Answer 3

Let us first rearrange the equation to make it look simple

p−s=q−r

p+r=q+s // which means sum of first elements is same as sum of last two elements.

Reflexive:-

(p,q)R(p,q) iff p+p=q+q ,which is not true always so not reflexive

Symmetric.

If (p,q)R(r,s) => (r,s)R(p,q)

p+r=q+s       =>  r+p=s+q

which will always hold.Hence symmetric

So, c is correct

Comments

Why are we assuming that if (a,B) exists then (B,a) must exist? Can't we have a pair of ordered set such as{ (6,5), (3,4) }alone in the relation. This follows the rule above. But it's neither symmeteric nor reflexive.

---

Why {5,6} and {3,4} is not there? If you define on 3,4,5,6 then you should take all the pairs which follow this property

---

I don't think I understood the question. :(

Answer 4

((p, q), (r, s)) ∈ R if and only if p–s = q–r

(p, q) is not related to (p, q)

as p-q is not same as q-p.

The relation is symmetric because if p–s = q–r, then s-q = s-p. 

Answer 5

p – s = q – r

=> p + r = q + s

=> sum of first terms = sum of second terms of ordered pair (p,q) and (r,s).

we shall now take examples to reach the answer.

Is (1,3)R(1,3) ? No because 1+1 != 3+3. Therefore the Relation is not reflexive.

consider (2,3) and (3,2). Now (2,3) R (3,2) because 2+3=3+2. Also (3,2) R (3,2).This relation is symmetric.

From the same example we can see that the  transitive pair would be (2,3) and (3,2) which again satisfies the condition, therefore is transitive.

Hence option C is a matching with our conclusion.

Answer 6

Option C

Given, $((p,q),(r,s)) \in R$ iff $p-s=q-r$

Simple check:

Let $(p,q) = a \ \& \ (r,s)  =b \implies aRb$

For Reflexive:

$a R a? \implies (p,q) R (p,q)?$

$p-q \neq q-p, hence\ not \ reflexive.$

For Symmetric: 

If $aRb$ then $bRa \ ?$ 

$(p,q)R(r,s) → (r,s)R(p,q) ? $

LHS : Is given $((p,q),(r,s)) \in R$ iff $p-s=q-r$

RHS: $r-q = s-p \implies p-s = q-r$

$LHS = RHS , hence \ symmetric$

Comments

@Abhrajyoti00

The relation you considered here for proving symmetricity is wrong ,

here the (p,q) & (r,s) is one relation.

consider (p,q) = a and (r,s)=b then it is like aRb , 

so to prove or disprove reflexivity we can take as     a R a [ i.e (p,q) R (p,q)]  

but in case of symmetricity we have to take  aRb → bRa [i.e (p,q)R(r,s) → (r,s)R(p,q)].

---

@Pranavpurkar Thanks :) Edited the answer.