# Intro to Proof: if $x$ divides $y$, then $x \leq y$

I am teaching a very small intro to proofs class with Dana Ernst IBL book, and came to theorem 2.56. The section is about proof by contradiction but I felt that the solution I came up with is unsatisfying or not at all what is expected. The students have not gotten here yet, I am preparing for when they do.

Quick Note - IBL is inquiry based learning and the students are meant to come up with the proof themselves. In this case, to learn how to use proof by contradiction.

The instructions are: Prove the following theorem via contradiction. Afterward, consider the difficulties one might encounter when trying to prove the result more directly. (Also, here $\mathbb{N} = \{1,2,3,\ldots\}$).

Assume that $x,y \in \mathbb{N}$. If $x$ divides $y$, then $x \leq y$.

My proof goes something like this.

Assume to the contrary that $x>y$. Since $x$ divides $y$, there is some integer, in this case positive, $k$, such that $xk = y$. Note that $xk>x$, and hence $y>x$, a contradiction.

This feels unsatisfying because if we can say that $xk>x$, then this is hardly worth proving. AND it is unnecessary to prove using proof by contradiction, which makes me wonder about the instructions.

What am I missing here? I assume that there must be some other proof which makes more sense. Any ideas are appreciated.

• Unfortunately, I suggest that this question would go better on SE Mathematics. It's really about a math question, and doesn't have any pedagogical content. – Daniel R. Collins Sep 19 '18 at 8:37
• @DanielR.Collins I considered that at first, but feel that since this is in an IBL class, the math takes a backseat to the educational part of the question. Also, I assumed someone there would suggest it go here, like you did. – N. Owad Sep 19 '18 at 10:02
• The problem is that you need to base your proof on a set of axioms or prerequisites. If you assume that $kx \geq x$ for all $x$ then your proof is correct, although boring. If you have other things given, I would suggest to still prove $kx \geq x$ and then get this result as an easy corollary. However, I guess that your book does not pay attention to these formal problems, if not even $\leq$ got defined properly, so there is no way to do it properly in this case. – Dirk Sep 19 '18 at 11:40
• Worth emphasis: the author appears to be extremely fond of using contradiction when not needed, i.e. assuming $\lnot P$, then proving $P$ (without using $\lnot P$), e.g. see L5.4: existence of prime factorizations; T5.14: uniqueness of prime factorizations; T5.22: "Euclid's" proof of infinitely many primes. Given that, it is not surprising that he may be highly abusing contradiction in T2.56 too. Find a better textbook. – Bill Dubuque Sep 19 '18 at 15:40
• To pile on to @Number's comment, if you are teaching a class in the style of Moore (oh, sorry---we call that IBL now...), it is necessary to start from a good set of definitions and axioms from which to build a theory. This book seems to assume that a lot of definitions and results are already known to students (perhaps in an attempt to rely on past knowledge to build intuition), and does things out of order (footnote [1] at the end of section 2.1 is a little scary). I also would seek a better text (or write your own notes). – Xander Henderson Sep 19 '18 at 18:19