1
$\begingroup$

I want to give a direct proof of a conditionnal $$\forall\, n\in \Bbb Z : \left[ P(n) \Rightarrow \lnot Q(n) \right]$$ such that $$P(n)= n>2$$ and$$ Q(n)= \exists\ m \in \Bbb Z: (\,m+n=mn \wedge n|m\,)$$ hence, I want to prove that $$\forall\, n\in \Bbb Z : \left[\,n > 2 \Rightarrow \lnot \exists\ m \in \Bbb Z: (\,m+n=mn \wedge n|m\,) \,\right] $$ is true.

I think that I proved the statement:

I take the converse, so $Q(n) \Rightarrow \lnot P(n)$ and assume $Q(n)$ hence, $n|m$.

It follows that $$m=nk: k\in\Bbb Z $$ Thus, $$k=\frac 1{n-1} \Rightarrow \left[m=\frac n{n-1}\in \Bbb Z \iff n=2\right] \Rightarrow \lnot P(n)$$

Therefore, $$\left[ Q(n) \Rightarrow \lnot P(n) \right]\Rightarrow \left[P(n) \Rightarrow \lnot Q(n)\right]$$ is true, by contrapositive.

What would be a direct proof of this statement? Is the contrapositive considered a form of direct proof?

|cite|improve this question
$\endgroup$
  • $\begingroup$ @Matthew Leingang Thank you I edited my question, I think it is better now $\endgroup$ – user408202 Jan 25 '17 at 0:14
  • 1
    $\begingroup$ Yes, that helps. Note that statement $P$ is false, so $P\implies Q$ is true for all $Q$. $\endgroup$ – Matthew Leingang Jan 25 '17 at 0:14
  • $\begingroup$ $Q$ has a free variable, namely $n$. $\endgroup$ – ajotatxe Jan 25 '17 at 0:18
  • 1
    $\begingroup$ As noted, the statement $\forall n \in \Bbb Z : n > 2$ is false. Instead I think you mean to say, Let $n \in \Bbb Z$ with $n > 2$. $\endgroup$ – user4894 Jan 25 '17 at 0:19
  • 2
    $\begingroup$ I suspect No Thought-No Concept is trying to prove $$\forall n\in \Bbb Z:\Big[ n>2 \implies \neg\exists m\in\Bbb Z:\big( m+n=mn ~\wedge~n\mid m\big)\Big]$$ $\endgroup$ – Graham Kemp Jan 25 '17 at 0:19
0
$\begingroup$

You wish to prove the following statement.

For all integers $n$ such that $n > 2$, there does not exist an integer $m$ such that $m + n = mn$ and $n$ is divisible by $m$. We will prove this directly.

We first note that $mn = n + (m-1)n$. Therefore, $(m-1)n=m$ and $n = \frac {m}{m-1}$. I now cite some previous knowledge you may or may not know of. Two adjacent integers $a$ and $a+1$ do not share any prime factors. Therefore, $n = \frac {m}{m-1}$ is only true when $m-1$ has no prime factors to prevent the division from resulting in a whole number integer $n$. the only numbers with that quality are $-1$ and $1$. Therefore, $m$ can only be one of two values $m = 0$ or $m = 2$. This results in two values for $n$, which are $2$ and $0$. Note that the only time $m$ exists satisfying the first condition is when the value for $n$ does not satisfy the given statement. Therefore, $m$ does not exist and the statement is true.

Comments/Note: I didn't use the divisibility portion of the statement. That's because I didn't need it. $n$ and $m$ are always equal by the equation and equal to either $2$ or $0$. I can only presume that the mention of divisibility is a red herring meant to throw off the op and make them think more critically about what is and is not useful in a proof.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I was thinking that I proved it by contrapositive if I assumed $Q$ and so if $n|m$ then, $m=nk\,:\,k \in \Bbb Z$ so we have $nk \,+\, n=n^2k$ which means $k=\frac 1{n-1}$ hence, $m=\frac n{n-1} \, \in \Bbb Z \iff n=2$ which means $\lnot P$. Therefore, since $Q \Rightarrow \lnot P$ we have $P \Rightarrow \lnot Q$ by contrapositive. I think your direct proof is more beautiful because of the argument you used though. $\endgroup$ – user408202 Jan 25 '17 at 2:25
  • $\begingroup$ @NoThought-NoConcept thanks. I tried to do as much as I could without referring to the divisibility. Most things tend to get very bloated when that is thrown in. Plus, it seemed pretty strange to have $n > 2$. Looking at the equation, it seemed like only $2$ satisfied it which tied back to the inequality. The fact that $0$ did as well was actually a happy accidental find. At that point, there was no need to think of divisibility. Basically, I proved a stronger statement that was simpler and "cleaner" than yours. $\endgroup$ – The Great Duck Jan 25 '17 at 2:30
  • $\begingroup$ Should I always try to avoid referring to divisibility and simplify that kind of statement before I try to prove it or does that means taking the risk of loosing meaningful information? $\endgroup$ – user408202 Jan 25 '17 at 2:37
  • $\begingroup$ @NoThought-NoConcept Think of it this way. It's true because the other statement is true. However, if this is a homework, don't bother reducing it. Just ignore the unneeded restriction.If it's a proof for a paper or something else, maybe mention that the restriction is unneeded in hindsight like I did. However, for a simple proofing class, the general premise of a proof is to be efficient, clear, and concise.Needlessly saying the restriction is unneeded just serves as wasteful dialogue. Think of it like a post office package. You get charged by the pound (character). Don't waste characters. ;) $\endgroup$ – The Great Duck Jan 25 '17 at 2:43
  • 1
    $\begingroup$ @NoThought-NoConcept oh. I read that all wrong. slightly ignore the last two comments. I would not remove divisibility. I didn't do that either. I just wrote the statement in English words to make it sound pleasant to human readers and then just never used that restriction to solve regarding $m$. Pure coincidence it occurred. Proofs are done however you choose. Just think through it, but NEVER change the original statement. Rewording it slightly is fine,but changing it won't remove information. It just means you are proving an equivalent statement and never stating you proved the original. $\endgroup$ – The Great Duck Jan 25 '17 at 2:50

Your Answer

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