[Math] what is the meaning of this predicate statement

logicpredicate-logic

This question appeared in the GATE exam 2011 Q.32

Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
P(x) = ¬(x=1)∧∀y(∃z(x=y*z)⇒(y=x)∨(y=1))

 (A) P(x) being true means that x is a prime number
 (B) P(x) being true means that x is a number other than 1
 (C) P(x) is always true irrespective of the value of x
 (D) P(x) being true means that x has exactly two factors other than 1 and x

so far what I have got from the above is :

  1. the statement is true when both the parts AND are true
  2. so x is not 1 and the implication is true
  3. for the implication to be true the premise can either be false or the consequent can be true or the premise and the consequent should be true
  4. for the consequent to be true all y's should be either equal to x or equal to 1 -trivial case
  5. the premise is always false. since for any x we cannot get a z for all y's which satisfies the "?z(x=y*z)" part.
  6. so the implication is always true and so the only thing we can infer if the predicate is true is that x is not equal to one

are there any mistakes in my argument ? are there any other interpretations ?

edit:

After a bit of pondering I finally got what the crucial part of the question is .
∀y(∃z(x=y*z)⇒(y=x)∨(y=1))

especially the ∀y part.

the for all quantifier should be true no matter what.ie the implication should be true for all y's. the implication is normally true for all inputs except when the premise is true and the consequent is false.

Best Answer

Your argument after step 3 is not correct.

The conditional : $(∃z(x=y*z)⇒(y=x)∨(y=1))$ is universally quantified by $∀y$. This means that : for any $y$ we have to "test" if the antecedent $∃z(x=y*z)$ holds.

Thus, for the sake of argument, assume $x = 3$; we have that $x \ne 1$ and thus the first conjunct is true.

For the second conjunct, we have to check, for any $y$, if exists $z$ such that : $3=y*z$.

For $y = 1$ we have $z = 3$; for $y = 2$ there is no $z$; for $y = 3$ we have $z = 1$.

Thus, for $x = 3$, we have found only two values of $y$ for which condition $∃z(x=y*z)$ applies : the first one is $1$ and the second one is $3$, i.e. $x$ itself.

Thus the conditional is true for those values, while it is vacuously true for all other values of $y$ different from $1$ and $3$.

In conclusion, for $x = 3$, we have that $¬(x=1)∧∀y(∃z(x=y*z)⇒(y=x)∨(y=1))$ is true, i.e. $P(x)$ holds.

For $x = 4$, we can check that, with $y = 2$ we have $z = 2$ [i.e. : $4 = 2*2$]. For $y = 2$ we have that the antecedent of the conditional is satisfied but the consequent is not ($2$ is different from both $1$ and $4$). Thus, we have found a factor of $x = 4$ which is not $1$ or $x$ itself.

In this case, it is not true that $∃z(x=y*z)⇒(y=x)∨(y=1)$ holds for any $y$, and we conclude that $P(x)$ does not hold for $4$.

Conclusion : the correct answer is (A) $P(x)$ being true means that $x$ is a prime number.

Related Question