GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
325 views

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)?

  1. $\Psi \wedge \Phi \wedge [\forall x \in A : \neg S(x, x)]$
  2. $\Psi \wedge \Phi \wedge [\forall x \in A : S(x, x)]$
  3. $\Psi \wedge \Phi \wedge [\forall x,y \in A : S(x, x) \wedge S(x, y) \rightarrow S(y,y)]$
  4. $\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)]$
  5. $\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)]$
asked in Mathematical Logic by Veteran (92.5k points) 957 2314 3109 | 325 views

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

2 Answers

+4 votes
Best answer

Here is my Approach ....i am also getting (E) as the answer 

let A be {1,2}  (say apple 1, apple 2)

there is atleast 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 throught the options :

(A) S(x,x) is not possible ....i dont have that in S ....so satisified .....and still finite A

(B)  S(x,x) should be there......well, i will make S={(1,2)(2,1),(1,1),(2,2)}....satisfied and still finite A

(C) take the same case as above ....satisfied and still finite A

(D) Now i cant have (1,1) and (2,2)

but even with S={(1,2).(2,1)} this condition is satisfied ....still finite A

(E) i cant do this with (1,2) and (2,1) ...because the trasitivity 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 atleast once in the left side of an ordered pair.......so only solution is infinite A ...

answered by Active (1.1k points) 3 11 24
selected by
Answer is not clear to me please give your explanation  @arjun sir

@ Arjun Sir,

I am unable to get the last line. Why infinite set is the solution? What elements does it contain according to the above answer? Can you please help me to clarify this?

Refer this similar question for detailed proof

http://gateoverflow.in/26748/gate1991-15-b

 

Still nice approach to solve such tricky question.Thanks.
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?
0 votes

$\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.

answered by Boss (5.3k points) 3 12 42
edited by
So A must be an uncountable set?
Yeah Sir,i think so. Otherwise even if A is countably infinite (we could enumerate order of degree of sweetnes in increasing order), then there can exist an apple that can not be sweeterr than some apple. Then, if set is null it might be due to finiteness or infiniteness of A.

Am I correct?
No. Say for integer set we can say for every integer there is a larger integer and the set is countable.
Thanks Sir, got it.
@arjun sir, can we say infinite set must be unbounded by both directions? Unbounded in terms of degree of sweetnes. Because if set is infinite but degree of sweetness can be in one to one correspondence then there might be an apple which not sweeter than any other?
Can you tell me what difference E is making to A?
Output of statement E if not null implies A is infinite. But output of statement A if not null doesn't imply A is infinite.
How can output of A be finite. Every apple should have an apple other than itself which is less sweet than it. So if A is finite as you are saying is possible, then how would that condition hold for least sweet apple?
Let A = { 1,2,3} , numbers denoting degree of sweetness. ∅ = { 2,3}

(A) can state about this set as well -

{1,2,3} ^ {2,3} ^ Universe = { 2,3} .
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:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23210 Points

  2. Bikram

    17018 Points

  3. Habibkhan

    6652 Points

  4. srestha

    5864 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4908 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4274 Points

  9. sushmita

    3954 Points

  10. Silpa

    3698 Points


Recent Badges

Regular Juhi Sehgal
Popular Question vineet.ildm
Nice Comment Arjun
100 Club vipul verma
Notable Question jothee
Popular Question jothee
Nice Question shivangi5
Regular rinks5
Notable Question shipra tressa
Regular sasi
27,247 questions
35,056 answers
83,703 comments
33,183 users