This is a MCQ of a competitive exam(GATE) , defined below . I found many different -2 explanation in market books and many other sources , but there is conflict between each explanation , I found all option correct by that different sources , I confused ,finally , I need explanation for this MCQ.
Problem is :
Consider the following formula and its two interpretations I1 and I2.
α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]I1 : Domain: the set of natural numbers
Px = 'x is a prime number'
Qxy = 'y divides x'
I2 : same as I1 except that Px = 'x is a composite number'.
Which of the following statements is true?
(A) I1 satisfies α, I2 does not
(B) I2 satisfies α, I1 does not(C) Neither I1 nor I2 satisfies α
(D) Both I1 and I2 satisfies α
One explanation is :
α in words: LHS implies RHS, where for I1
LHS = If for all x, x is prime if and only if for all y, y is a factor of x if and only if y does not divide itself. In other words, for all x, if x is prime, x cannot have any factor and if x is not having any factor then x is prime. RHS = All x are non-prime
Here LHS is always TRUE but RHS is not true as domain of x is set of natural numbers and hence x cannot be always not prime. So, α is not satisfiable for I1.
Now for I2,
LHS = If for all x, x is composite if and only if for all y, y is a factor of x if and only if y does not divide itself. In other words, for all x, if x is composite, x cannot have any factor and if x is not having any factor then x is composite. RHS = All x are non-composite
Here, LHS can never be true. x can either be prime or composite. If x is composite, P(x) is true but the right side of double implication is false. If x is prime, P(x) is false, but right side of double implication is true. So, the double implication never returns TRUE making LHS of α always FALSE. So, α becomes TRUE irrespective of RHS and I2 is satisfiable.
another solution is :
First of all, note that, in α, ¬Qyy is always false, because every number divides itself. Also not that rightmost formula (∀x)[¬Px] is always false, because clearly it is not the case that every number is not the prime number (in case of I1), nor it is the case that every number is not the composite number (in case of I2). Also note that, variable x in this expression is not same as variable x in leftside expression, they are independent. In fact, we can rewrite α as α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀z)[¬Pz]. Let us consider I1 first. So let us assign some value to x, and see if it satisfies α. We can partition assignments of x into 3 parts : when x is prime, when x is composite, when x is 1.
When x is prime : Px is true, also Qxy is false for all y except 1, because only 1 divides x. So formula Qxy⇔¬Qyy is true for all y except 1, but due to ∀y outside this, whole formula ∀y[Qxy⇔¬Qyy] becomes false, because it would have been true if Qxy⇔¬Qyy was true for every y. So now (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]] becomes false. So whole α becomes true. When x is composite : Px is false, also Qxy is true for some y (which divide x), and false for some y (which do not divide x), so Qxy⇔¬Qyy becomes true for some y and false for some y, but again due to ∀y outside, ∀y[Qxy⇔¬Qyy] becomes false. So (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]] becomes true, and so α becomes false. So for some x, I1 satisfies α, but for some, it doesn't, so overall, it doesn't satisfies α. Note that we don't need to look into case of x=1, because we already know the answer. Now consider I2. Here Px means x is composite. Again we look into same cases as above :
When x is prime : Px is false, also ∀y[Qxy⇔¬Qyy] becomes false because of same reasons as above. So now (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]] becomes true. So whole α becomes false. So clearly I2 also doesn't satisfy α. Again we won't go into other cases, as we already got false for some x. So Neither I1 nor I2 satisfies α, so option (C) is correct.
As the problem is stated, the correct answer is: (D) both I1 and I2 satisfies α.
Let us look in the details.
First note that α can be rewritten as
α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀z)[¬Pz]
Take any prime number x, so Px is TRUE, but since $1$ and x divides x, and both $1$ and x divide themselves respectively, we have that (∀y)[Qxy⇔¬Qyy] is FALSE. So (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]] is FALSE. and so α is true in I1. It means I1 satisfies α.
Take any composite number x, so Px is TRUE, but since $1$ and x divides x, and both $1$ and x divide themselves respectively, we have that (∀y)[Qxy⇔¬Qyy] is FALSE. So (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]] is FALSE. and so α is true in I2. It means I2 satisfies α.
So, both I1 and I2 satisfies α.