a hard question about quantifiers

Question

For every integer $n>1$, there is a prime strictly between $n$ and $2n$.

(a) Express the statement in terms of quantifiers, variable(s), inequality symbols $<$ or $>$, logical operators ($∧$, $∨$, $\implies$) and predicate $P(n)$: $n$ is a prime number.

(b) Express the negation of (a) without using the logical operator $¬$.

I guess the answer to part a is $∀n∃x(n>1→(P(n)>n)∧(P(n)<2n))$, but I don't know how to do part b... Help...

Answer 1

For part b, use $\lnot\forall xP(x)\equiv\exists x\lnot P(x)$ and $\lnot\exists xP(x)\equiv\forall x\lnot P(x)$.

Answer 2

Once you have finished a), note that b) is just an exercise in how to "percoloate" a negation symbol into a formula by using rules such as $\neg\forall x\phi\equiv \exists x\neg\phi$, $\neg(p\land q)\equiv\neg p\lor \neg q$, $\neg(p\to q)\equiv p\land \neg q$, $\neg(a>b)\equiv a\leq b$ (where that latter assumes - as probably justified in your context - that the universe of discourse is something like numbers)

Answer 3

This is a kind of question that is no good candidate for guessing an answer and then trying to justify it. Instead you should go about it systematically and construct the expression. You can start from inside.

First "there is a prime" means there is a number $x$ and that $x$ is a prime. Furthermore there is the statement that it's also between $n$ and $2n$. This means that there's a number $x$ and that $x$ is a prime and also $n<x<2x$. Or "there is a prime in the range between $n$ and $2n$" put in formula language:

$$\exists x: (P(x) \land n<x<2x)$$

Then this should be true for all $n$:

$$\forall n\exists x: (P(x) \land n<x<2n)$$

Then in order to negate it you just negate it:

$$\neg\forall n\exists x: (P(x) \land n<x<2n)$$

And to get rid of the negation you repeatedly use DeMorgan laws, but first you expand $n<x<2x$ which means that $n<x\land $x<2n$:

$$\exists n\neg\exists x: (P(x) \land n<x \land x<2n)$$ $$\exists n\forall x: \neg(P(x) \land n<x \land x<2n)$$ $$\exists n\forall x: (\neg P(x) \lor \neg n<x \lor \neg n<2x)$$

Now $\neg n<x$ is of course $n\ge x$. To get rid of the the $\neg P(x)$ you use the fact that $\phi\rightarrow\psi$ is the same as $\neg\phi\lor\psi$: $$\exists n\forall x: (P(x) \rightarrow (n\ge x \lor n\ge2x)$$