I have come up with the following expression for "There is no largest prime number."
$$\neg \left( \exists q. \left( Prime(q) \wedge \left( \forall p. Prime(p) \wedge q \ge p \right) \right) \right) \tag 1$$
However a solution given is:
$$\neg \left( \exists q. \left( Prime(q) \wedge \left( \forall p. Prime(p) \implies q \ge p \right) \right) \right) \tag 2$$
The only difference is that there is an implication used instead of an conjunction.
Why is (1) wrong? How do the truth tables for (1) and (2) differ and why?
Best Answer
$(\forall p. Prime(p) \land q \ge p )$ is saying that every natural number (since the universal quantifier quantifies over your whole domain ... which is the natural numbers) is both a prime and smaller or equal to $q$. Well, just focusing on that first part: clearly it is not true that every natural number is prime. So with the conjunction instead of a conditional, that part ends up makes the rather trivially false statement that every number is a prime ... clearly not what you want. What you want is that if you have some prime $p$, then that must be smaller or equal than the largest prime $q$.
Now, in predicate logic, you can't really use truth-tables anymore, because you start dealing with infinitely many different kinds of worlds (worlds in which there is 1 object, worlds in which there are 2, etc.)
However, we don't have to resort to a truth-table to show that these statements can take on different truth-values and are therefore not equivalent. We just need to create some interpretation of the predicates that makes one true and the other false. Now, as to not be distracted by the predicates you are using, let's first abstract the 2 statements to:
$\neg \exists q (P(q) \land \forall p (P(p) \land R(p,q))$
$\neg \exists q (P(q) \to \forall p (P(p) \land R(p,q))$
In other words, we have some 1-place predicate $P$, and some 2-place predicate $R$ ... left to be interpreted any way we want.
OK, now ... let's consider a world where no objects have property $P$. Then clearly $P(q) \land \forall p (P(p) \land R(p,q)$ is false, and hence it is true that $\neg \exists q (P(q) \land \forall p (P(p) \land R(p,q))$. On the other hand, $P(q) \to \forall p (P(p) \land R(p,q)$ is vacuously true, and hence is is false that $\neg \exists q (P(q) \to \forall p (P(p) \land R(p,q))$. OK, so there is your counterexample to the claim of their equivalence