Intend to state the logical representation of the negation of the above proposition.

For the given proposition, the logical equivalent is: $\forall l \in \mathbb{Z+}, \exists n \in \mathbb{Z}, np = p^l.$
The logical equivalent reads: for all positive integer values of $l$, there exists some integer $n$ s.t. the equality $np = p^l$ holds true.

So, the negation of the given proposition will be :$\lnot (\forall l \in \mathbb{Z+}, \exists n \in \mathbb{Z}, np = p^l) = \exists l \in \mathbb{Z+}, \forall n \in \mathbb{Z}, np \ne p^l.$
The logical equivalent for the negated proposition reads:
for some positive integer value(s) of $l$, for all integers $n$, the equality $np = p^l$ never holds true.

By the above elaboration, it seems that the variable $n$ doesn't hold significance, and consequently can state the negated proposition's logical equivalent as:
$\lnot (\forall l \in \mathbb{Z+}, \exists n \in \mathbb{Z}, np = p^l) = \exists l \in \mathbb{Z+}, p \nmid p^l.$

  • 1
    $\begingroup$ Not clear... It is correct that $\lnot (\forall l \ \exists n \ \varphi)$ is equiv to $(\exists l \ \forall n \ \lnot \varphi)$. $\endgroup$ – Mauro ALLEGRANZA Feb 27 '18 at 16:15
  • 1
    $\begingroup$ But this does not mean that you can omit $n$. $\endgroup$ – Mauro ALLEGRANZA Feb 27 '18 at 16:15
  • 1
    $\begingroup$ To say that $p \nmid p^l$ means exactly that for no $n$ we have : $np=p^l$. $\endgroup$ – Mauro ALLEGRANZA Feb 27 '18 at 16:17
  • $\begingroup$ @MauroALLEGRANZA Then the existential quantifier for $l$ is insignificant for all practical purposes in the negated proposition. In fact, even though $l$ has the existential quantifier as : $\exists$, it serves as if the $\forall$ is in force actually. By that I mean that $\forall l \in \mathbb{Z}, \forall n \in \mathbb{Z}, np\ne p^l$ If so, then does the correct way to interpret the significance of the existential quantifiers depends on context? $\endgroup$ – jitender Feb 27 '18 at 16:24
  • 1
    $\begingroup$ Not exactly... If you write $ p∤p^l$, this already includes the quantification on $n$, because it is simply: $\forall n (p^l \ne pn)$ i.e. $\lnot \exists n (p^l=pn)$. But you want to assert it for some $l$ or for all $l$, and this needs the appropriate quantification on $l$. $\endgroup$ – Mauro ALLEGRANZA Feb 27 '18 at 16:47

The negation of the formula is correct: $¬(∀l \ ∃n \ \varphi)$ is equivalent to $(∃l \ ∀n \ ¬ \varphi)$.

We have the true fact that $p∣p^l$, for every $l \in \mathbb Z_{+}$, $p$ divides every power of $p$.

What is its negation ? There is a power of $p$ such that $p$ does not divide it, i.e.

$∃l \ (p^l \text { is not a multiple of } p)$,

and this is $p∤p^l$, for some $l \in \mathbb Z_{+}$.

If we unwind it we get:

$∃l \ \forall n \ (p^l \ne pn)$,

and this is exactly what you have written.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.