1
$\begingroup$

I am attempting to prove the following statement by proving the contrapositive.

For all natural numbers n, IF n = k * l and (k less than or equal to l) THEN k less than or equal to square root of n

I have found the contrapositive to be:

For all natural numbers n, IF k greater than the square root of n THEN n does not equal k * l OR k is greater than l

I know to prove this we must first assume the first the part to be true (that k is greater than the square root of n) and that can lead me to say that k squared is greater than n.

I am used to approaching the proof by expressing one variable in terms of another such that I can substitute the expression in for the variable in another expression. I would then solve for another variable and prove it is an integer or something like that. In this situation, how can I take the expression from one statement to sub into another if there are no equal signs involved? I do not know how to solve for an expression being not equal to another. Am I even on the right track? If I express k squared to be greater than n, how can I even move that into another equation and still keep the idea that it is greater than.

I don't understand how I can say anything about l without it being on the left side of the if/then statement. In the current iteration of the proof, I am only assuming k to be greater than the square root of n. I don't see how I can assume anything more?

Any hints on what direction I can go from here would be very appreciated.

$\endgroup$
  • $\begingroup$ If $n=k\cdot l$ and $k\geq l$ then $k\leq \sqrt{n}$ is false. Take $9=9\cdot 1$ for counterexample. You have an inequality sign in the wrong direction. $\endgroup$ – JMoravitz Oct 9 '17 at 17:50
  • $\begingroup$ also note that when negating $k \ge l$ the correct negation would be $k \lt l$. Maybe you wrote the first part wrong, but the negation is what's right, considering what @JMoravitz said $\endgroup$ – Francisco José Letterio Oct 9 '17 at 18:02
  • $\begingroup$ You are absolutely correct, I did have an inequality in the wrong direction and have corrected that. Sorry, thank you for noticing $\endgroup$ – Kaari Landry Oct 9 '17 at 18:11
  • $\begingroup$ "For all natural numbers n, IF k greater than the square root of n THEN n does not equal k * l OR k is greater than l" Another way of putting this: If $k>\sqrt{n}$ then if $n=k*l \implies k > l$. So if $n=k*l$ then $n>\sqrt{n}l$ and $l < \frac n{\sqrt{n}} = \sqrt{n} < k$. $\endgroup$ – fleablood Oct 9 '17 at 18:40
1
$\begingroup$

I find this easier to do when you do it in symbols.

So you have:

$$\forall n,k,l \in \mathbb{N} ((n = k\cdot l \land k \le l) \rightarrow k \le \sqrt{n})$$

Taking the contrapositive (or at least the contrapositive of the main body):

$$\forall n,k,l \in \mathbb{N} (\neg k \le \sqrt{n} \rightarrow \neg (n = k\cdot l \land k \le l))$$

which works out to:

$$\forall n,k,l \in \mathbb{N} (k > \sqrt{n} \rightarrow (\neg n = k\cdot l \lor k > l))$$

Also, since $\neg P \lor Q \Leftrightarrow P \rightarrow Q$, it might be nice to rewrite this to:

$$\forall n,k,l \in \mathbb{N} (k > \sqrt{n} \rightarrow (n = k\cdot l \rightarrow k > l))$$

And since $P \rightarrow (Q \rightarrow R) \Leftrightarrow (P \land Q) \rightarrow R$, we can also do:

$$\forall n,k,l \in \mathbb{N} ((k > \sqrt{n} \land n = k\cdot l) \rightarrow k > l)$$

which is probably the most useful format if you have to actually prove it.

$\endgroup$
  • $\begingroup$ With the correction I had made to the original question, I get ∀n,k,l∈ℕ((k>n‾√∧n=k⋅l)→k>l). It follows that k^2 > k.l so l must be less than k. I see how I can formally say that now thanks for the help with my formatting! $\endgroup$ – Kaari Landry Oct 9 '17 at 18:20
  • $\begingroup$ @KaariLandry OK, I updated my answer accordingly. This was easy to do exactly because of the logical formalization, which is one reason why that's a really good idea. :) $\endgroup$ – Bram28 Oct 9 '17 at 18:26
  • $\begingroup$ I accepted your response as the answer because you gave me generalized rules associated with each step. This gave me a format to be able to make the proof myself rather than providing an answer $\endgroup$ – Kaari Landry Oct 9 '17 at 19:16
  • $\begingroup$ @KaariLandry Glad I could help! $\endgroup$ – Bram28 Oct 9 '17 at 23:14
0
$\begingroup$

What you have stated is wrong, so it will be hard to prove.

You stated "For all natural numbers n, IF n = k * l and (k greater than or equal to l) THEN k less than or equal to square root of n".

However, you can always write $n = n\times 1$ and this $k$ (with $k=n$) does not satisfy the conclusion.

What is correct is

"For all natural numbers n, IF n = k * l and (k less than or equal to l) THEN k less than or equal to square root of n".

The contrapositive is

If $k > \sqrt{n}$ and $k \le l$ then $n \ne k \times l$.

The proof is easy:

Since $l \ge k > \sqrt{n}$, then $k \times l \gt \sqrt{n}\times \sqrt{n} =n $ so $k \times l \ne n$.

Note that this holds for any positive reals, not just integers.

$\endgroup$
  • $\begingroup$ I have since edited the question to include that correction, sorry for the confusion. $\endgroup$ – Kaari Landry Oct 9 '17 at 18:21
0
$\begingroup$

"For all natural numbers n, IF k greater than the square root of n THEN n does not equal k * l OR k is greater than l"

Assume $k > \sqrt {n}$.

If $k \le l$ then $k*l > k*k >{\sqrt{n}}^2 =n$.

If $k*l = n$ then $l = \frac {n}k < \frac {n}{\sqrt n} = \sqrt n < k$.

So either $n \ne kl$ or $k> l$.

$\endgroup$

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.