GO Classes Test Series 2024 | Discrete Mathematics | Test 2 | Question: 9

Answer 1

On a non-empty set $A,$ we define a relation $S.$

$∀x∀y(S(x,y)⇔¬S(y,x))$ means that for all pairs $(x,y) \in A \times A,$  $S(x,y)⇔¬S(y,x)$ must be true, which is NEVER possible to be true for any non-empty set $A$ because when $x,y$ refer to same element, $S(x,y)⇔¬S(y,x)$ will be False.

Hence, there is NO finite Or infinite model for the given expression, Or we can say that on any non-empty set $A,$ we cannot define any such relation $S.$

Hence, answer is C,D.

---

In the same question, if we have the following definition of relation $S:$

 

$∀x∀y(S(x,y) \rightarrow ¬S(y,x))$

∧

$[∀x∃yS(x,y)]$

∧

$∀x∀y∀z(S(x,y)∧S(y,z)⇒S(x,z))$

Now, it becomes satisfiable but has no finite model.

Similar question and my explanation you can find here: GATE CSE 1991 | Question: 15,b Deepak Poonia Explanation

Comments

Sir, what is the difference between the expression given in the question and the equation you have posted in the later part of the answer? How is the latter satisfiable?

UPD: After reading the comments it seems you meant implication and not bi-implication, right?

---

@Deepak Poonia sir I think you meant to write implication rather than bi-implication in the solution given by you.

---

It has been corrected now. Please check.