# Converting English to Quantifiers: 'There is no greatest prime'

I'm working on an exercise that appears rather simple, but the answer I keep coming up with differs from what the instructor found.

Say I want to convert the sentence 'there is no greatest prime' to quantifier notation, and I'm to work with two english variables, $a$ and $b$, within the universe of discourse of $\mathbb{N}$, and a predicate, $\text{prime$x$}$ that corresponds to "$x$ a prime."

My approach was: this sentence is equivalent to saying that, for any prime number, we can always find some other prime greater than it. So, take $a$ and $b$ to be naturals, and with $a$ we quantify over the entire universe of naturals. We need only find one larger prime, so we can allow an existential quantifer for $b$. Then, we apply the prime predicate to both $a$ and $b$, and reason that we can always choose a $b$ so that $b > a$. So, I come up with: $$\forall b, \exists a, \left(\text{prime a} \wedge \text{prime b} \wedge \left(b > a\right)\right).$$ This seemed to make sense, and I believe follows from the relatively famous proof by contradiction that there is no greatest prime.

However, this answer was apparently wrong, and I can't quite figure out why. I'd greatly appreciate any insights on this.

REVISION: Thank you all for the very helpful answers. For reference for anyone who may look up this problem, people have highlighted two fundamental mistakes in my above constructions. First, I incorrectly suggested, with prime $b$, that every natural number is prime, which is surely not the case: this should be framed as an implication, with antecedent "$b$ is prime." From there, that $b$ is prime would guarantee the existence of some prime, $a$, such that $a > b$. This was the second mistake, as I inadvertently reversed the inequality sign. This could be framed either with $p \implies q$ or, as with one answer, the logically equivalent expression $-p \lor q$.

Thanks again.

• You need $\forall b \big(\text{prime}(b) \to \exists a(\text{prime}(a) \land a>b)\big)$ Jul 13 '18 at 14:52

There's one mistake that just looks like a typo: it seems that you meant $a > b$ rather than $b > a$.
More fundamentally, what goes wrong is that you (in particular) claim that any $b$ is prime. Even if we forget all the conditions on $a$, your sentence still claims that $\forall b(\mathrm{prime}(b))$. What you probably mean is that if $b$ is prime, then there is a larger prime $a$. For example, $$\forall b(\mathrm{prime}(b) \to \exists a(\mathrm{prime}(a) \land a > b)).$$
There are 2 problems with your statement: $$\forall b, \exists a, \left(\text{prime a} \wedge \text{prime b} \wedge \left(b > a\right)\right)$$ which says: for every $b$, there is $a$, such that $b$ is prime, $a$ is prime, and $a<b$. First, why must $b$ be prime? Second, $a<b$ is in the wrong direction. I would fix it as follows $$\forall b, (\neg\text{ prime }b \vee (\exists a,\text{ prime a} \wedge \text{prime }b \wedge (a>b))).$$