# Predicate logic: There is no largest prime number.

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?

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

• What do you mean by "world" and "different kinds of worlds"? (I haven't heard the word "world" in logic since I'm a complete beginner.) – FizzleDizzle May 29 at 13:59
• @FizzleDizzle In logic you are dealing with statements. Those statements are true or false depending on the situation. For example, the statement "It rains" would be true when it is raining, but false when it is not raining. Or, as another example: "The sum of the angles in a triangle equals the sum of two right angles" is true in Eucledian geometry, but false in non-Eucledian geometry. This is why we say that the truth of a claim depends on what world we evaluate it in. (cont'd) – Bram28 May 29 at 14:53
• @FizzleDizzle Indeed, any "logically possible" world is a world without contradicitons. So, I could consider worlds where pigs fly, where grass is purple, etc. The rows in a truth-table show these different kinds of worlds: A row where $P$ and $Q$ are both true represents the world (or rather, all kinds of worlds) where $P$ and $Q$ are both true. etc. And now we can also say things like: A statement is a tautology if and only if it is true in all possible worlds ... i.e. it is true under all circumstances/in all situations/no matter what – Bram28 May 29 at 14:56
• @FizzleDizzle P.s. For an absolute beginner you're doing very well on these symbolizations! – Bram28 May 29 at 15:03