TIFR CSE 2016 | Part B | Question: 4

Question

In the following, $A$ stands for a set of apples, and $S(x, y)$ stands for "$x$ is sweeter than $y$. Let

$$\Psi \equiv \exists x : x \in A$$

$$\Phi \equiv \forall x \in A : \exists y \in A : S(x, y).$$

Which of the following statements implies that there are infinitely many apples (i.e.,, $A$ is an inifinite set)?

• A. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)]$
• B. $\Psi \wedge \Phi \wedge [\forall x \in A : S(x, x)]$
• C. $\Psi \wedge \Phi \wedge [\forall x,y \in A : S(x, x) \wedge S(x, y) \rightarrow S(y,y)]$
• D. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)] \wedge [\forall x, y, z \in A : S(x, y) \wedge S(y, z) \rightarrow s(y, x)]$
• E. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)] \wedge [\forall x, y, z \in A : S(x, y) \wedge S(y, z) \rightarrow s(x, z)]$

Comments

An interesting point to note would be that this is gracefully similar to https://gateoverflow.in/26748/gate1991-15-b

---

This question can be converted in another Relation $R(x,y)$ such that $x<y$ , where domain of $x$ and $y$ is natural numbers.

Now our Relation $R$ has following restrictions

1)Relation can't be Null.

2) $\forall x\exists y : R(x,y)$ means every element is less than some element.

3) Relation is irreflexive.

4) Relation is transitive.

This relation is exactly same as option $e$ and there can't exist any finite $R$.

for example take 3 elements in R (1,2,3)

1<2 and 2<3 so to make it transitive (1,3) should be there so it can present as 1<3 but there is another property that every element is less than some element but 3 can't be less than some element so in that manner we can observe that R must have to be an infinite set.

---

can you explain how we got conclusions 3 and 4 ….1 and 2 are understandable as they are given in the question itself

---

Related to finite and infinite models. Refer: https://math.stackexchange.com/a/2229075/877824

Answer 1

(E) is the answer 

Let $A$ be $\{1,2\}$  (say apple $1$, apple $2$)

There is at least one element in $A$ : satisfied
For every element $x$ in $A$ there is a $y$ in $A$ such that $S(x,y)$ : Since nothing is told about the symmetry of the relation, we can have $S(1,2)$ and $S(2,1),$  so, satisfied

So, as of now, $A = \{1,2\}$ and $S=\{(1,2),(2,1)\}$

Now we can go through the options :

• A. $S(x,x)$ is not possible $\ldots$ I do not have that in $S$ $\ldots$ so satisfied $\ldots$ and still finite $A$
• B. $S(x,x)$ should be there $\ldots$ well, I will make $S=\{(1,2)(2,1),(1,1),(2,2)\}$ $\ldots$ satisfied and still finite $A$
• C. take the same case as above $\ldots$ satisfied and still finite $A$
• D. Now I can not have $(1,1)$ and $(2,2)$
  but even with $S=\{(1,2).(2,1)\}$ this condition is satisfied $\ldots$ still finite $A$
• E. I can not do this with $(1,2)$ and $(2,1)$ because the transitivity makes it $(1,1)$ which should not be there and whatever elements I add the transitivity will lead me to $(x,x)$ because any element added to $A$ should occur at least once on the left side of an ordered pair $\ldots$ so only solution is infinite $A.$

Comments

It should be an asymmetric relation. As both S(1,2) and S(2,1) cannot be in one relation.

So according to  option (E), irreflexive and transitive must generate an asymmetric relation.

How infinite A is possible?

---

nice explanation @ Anand vijayan

---

can anyone expalin the que. that symbols part ? and what is model, wher to study all these ?

Answer 2

$\Psi$ is the set containing at least one apple. $\Phi$ is the set containing all apples which are sweeter than at least one apple. 
Now,
(A) - Set of some apples such that they are sweeter than some apples and no Apple is sweeter than itself. Whether A is finite or infinite this statement always gives such apples therefore, this statement does not necessarily imply A is infinite. 

(B) - Set of some apples such that they are sweeter than some & itself. Whether A is finite or infinite this set is allways null as no Apple can be sweeter than itself. Therefore this statement doesn't imply A is infinite. 

(C)- Same as above with little variations.

(D)-  This statement also gives empty set whether A is finite or infinite due to given implication therefore this statement doesn't imply A is infinite. 

(E)- Set of some apples such that they are sweeter than some apples & no Apple among them is sweet than itself BUT every Apple among them is sweeter than some other apple. Now, if A is finite this statement is bound to give empty set since if A is finite we always can arrange Apples in order of their increasing degree of sweetnes & first apple can't have property "sweeter than some apple". But if A is infinite & that too unbounded set $(-\infty,+\infty)$(regarding degree of sweetnes) we can always have some Apples sweeter than others. Therefore they can have property "every apples among them can be sweeter than any other apple". Now considering this statement to be not null, statement will imply A is infinite. 

Therefore I think E is the answer. Lemme know if I'm wrong.

Comments

Okk...now what E is adding to that example?

---

Yes. You're right. I think somewhere is mistake. Let me think on this. Thank you for providing a loophole.

---

Sure.
Please let me know when you come up with an answer. :)

Answer 3

Psy says : There exists a apple.
Phy says : Every Apple is sweeter than some apple.

Option A says that : There is some apple And No apple is sweeter than itself And Every Apple is sweeter than some apple.
This is confusing option if you think in terms of apple because we would think that if apple A is sweeter than B then B cannot be sweeter than A. So, don’t think in terms of Apples and only in terms of some elements X,Y.
Option A can be true for set of two apples {A,B} if A is sweeter than B and B is sweeter than A.

Option B says that : There is some apple And every apple is sweeter than itself And Every Apple is sweeter than some apple.
It Does not mean there are infinitely many apples because set of one apple also satisfies this condition.

Option C Does not mean there are infinitely many apples because set of one apple also satisfy this condition.

Option D can be true for set of two apples {A,B} if A is sweeter than B and B is sweeter than A And No apple is sweeter than itself.

Option E is correct because it is irreflexive and transitive relation which makes it anti-symmetric. So, there is No least sweet apple and hence, infinite apples.

Answer 4

The first statement implies that there are infinitely many apples:

Ψ∧Φ∧[∀x∈A:¬S(x,x)].

The second statement is false and does not imply that there are infinitely many apples.