6
$\begingroup$

Usually, I find it a cakewalk to write the contrapositive, but the following statement is quite complex for the task:

For all integers $n > 1$, if $n$ is not prime, then there exists a prime number $p$ such that $p \leq \sqrt n$ and $n$ is divisible by $p$.

Is it "There exists no prime number $p$ such that $p \leq \sqrt n$ and $p \, | \, n$ given that $(n > 1)$ for a prime integer $n$"? The weird thing here is that the first universal statement (for all integers $n$) was not converted into a conditional, which makes me uncomfortable.

I'd appreciate some guidance.

$\endgroup$
1
  • 2
    $\begingroup$ Only a statement of the form "If A then B" has a contrapositive. The statement "For all integers..." etc. does not have a contrapositive. The statement within it, "if $n$ is not prime," etc., has a contrapositive. $\endgroup$ Commented Jul 23, 2013 at 17:27

3 Answers 3

4
$\begingroup$

You have the statement:

For all integers $n > 1$, if $n$ is not prime, then there exists a prime number $p$ such that $p \leq \sqrt n$ and $n$ is divisible by $p$.

This is a statement of the form $$\text{Let }\;n\in \mathbb Z, n > 1: \quad \forall n\left [\lnot P(n) \implies \exists p (Q(n, p) \land R(n, p))\right]$$

It's contrapositive is:

For all integers $n\gt 1$, if there does not exist a prime number $p$ such that $p \leq \sqrt n$ and $n$ is divisible by $p$, then $n$ is prime.

Which is a statement of the form $$\text{Let}\;n\in \mathbb Z, n > 1:\quad \forall n [\lnot \exists p(Q(n,p) \land R(n,p)) \implies P(n))$$

$\endgroup$
14
  • $\begingroup$ Did you mean to write $p \leq \sqrt n$ instead of $p \geq \sqrt n$ in the contrapositive? $\endgroup$
    – ankush981
    Commented Jul 23, 2013 at 16:59
  • $\begingroup$ Oh, yes, of course. So sorry for that typo! $\endgroup$
    – amWhy
    Commented Jul 23, 2013 at 17:00
  • $\begingroup$ Phew! Scared the hell out of me for a while. :-) $\endgroup$
    – ankush981
    Commented Jul 23, 2013 at 17:00
  • $\begingroup$ Sorry 'bout that, corrected. Your hunch is right on, in your post. As I wrote in a comment below another answer, you can think of the "for all integers $n > 1$..." as restricting the domain: "n is to be taken as any integer greater than one", and the rest is the conditional, over which we take the contrapositive. I understand that it can seem confusing. If we were negating the entire given statement, that would indeed modify the statement more drastically. $\endgroup$
    – amWhy
    Commented Jul 23, 2013 at 17:03
  • 1
    $\begingroup$ Like in my comment above, yes. However, the statement at hand only makes sense when we take as given that $n$ is an integer greater than $1$: since it does not make sense to talk about 1 being prime, or of a non-integer being divisible, etc. A statement like "if all x are P, then some y is Q" would be" if there does not exist a y that is Q, then it is not the case that all x are P$. But that isn't really the case here. $\endgroup$
    – amWhy
    Commented Jul 23, 2013 at 18:12
2
$\begingroup$

The contrapositive is: Let $n > 1$ be an integer. If there does not exist a prime $p$ such that $p \leq \sqrt{n}$ and $n$ is divisible by $p$, then $n$ is prime.

Or in other words: let $n > 1$. If for all primes $p$, either $p > \sqrt{n}$ or $n$ is not divisible by $p$, then $n$ is prime.

We are starting out with an arbitrary integer $n > 1$. The contrapositive to "if $n$ is not prime, then there exists a prime number $p$ such that $p≤ \sqrt{n}$ and $n$ is divisible by $p$" is "if for all primes $p$, either $p > \sqrt{n}$ or $n$ is not divisible by $p$, then $n$ is prime." The contrapositive to $A \implies B$ is "if not $B$, then not $A$." But your original statement was of the form "For all $n > 1$, $A$ implies $B$." So the "contrapositive" would be "For all $n > 1$, not $B$ implies not $A$."

$\endgroup$
2
$\begingroup$

Let's write it as FO formula: $$(n>1)\wedge(\mbox{ $n$ is not prime})\Longrightarrow \exists p((p \mbox{ is prime}) \wedge (p\leq n)\wedge (p|n)) $$ So the contapositive statement will be $$\sim( \exists p((p \mbox{ is prime}) \wedge (p\leq n)\wedge (p|n)))\Longrightarrow \sim ((n>1)\wedge(\mbox{ $n$ is not prime}))$$ which is same as $$ \forall p((p \mbox{ is not prime}) \vee (p> n)\vee (p\not|n))\Longrightarrow ((n\leq1)\vee(\mbox{ $n$ is prime}))$$

$\endgroup$
3
  • 1
    $\begingroup$ The conditional exists within the scope of the universal quantifier, so the contrapositive of the conditional must exist within the scope of the universal quantifier. The statement does NOT read: "IF (for all $n\gt 1$ and blah) THEN (exists blah or blah or blah)". The universal quantifier remains unaltered. $\endgroup$
    – amWhy
    Commented Jul 23, 2013 at 16:33
  • 1
    $\begingroup$ I think another way of looking at amWhy's point is that a statement of the form $\forall \cdots$ doesn't itself have a contrapositive. Some expression within that may have one. $\endgroup$
    – dfeuer
    Commented Jul 23, 2013 at 16:47
  • $\begingroup$ I guess this was the stumbling block for me. I couldn't deal with the universal at the start. $\endgroup$
    – ankush981
    Commented Jul 23, 2013 at 17:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .