4
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 3
    $\begingroup$ 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. $\endgroup$
    – Daniel R. Collins
    Commented Sep 19, 2018 at 8:37
  • 2
    $\begingroup$ @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. $\endgroup$
    – N. Owad
    Commented Sep 19, 2018 at 10:02
  • 8
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Sep 19, 2018 at 15:40
  • 2
    $\begingroup$ 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). $\endgroup$
    – Xander Henderson ♦
    Commented Sep 19, 2018 at 18:19
  • 2
    $\begingroup$ Okay, now that I've read the book, it looks like the author is taking letting students use obvious things like "$0<k$ implies $1 \leq k$" without proof". I agree with you; it seems to me that by the standards of the book, the following should be a correct solution. "By the definition of divides, there is an integer $k$ with $y=xk$. Since $y$ and $x>0$, we have $k>0$, so $k \geq 1$. But then $y = xk \geq x$." This is not a good example to demonstrate contradition, even if a contradiction is hiding somewhere implicitly in this. $\endgroup$
    – David E Speyer
    Commented Oct 7, 2019 at 17:35

1 Answer 1

Reset to default
1
$\begingroup$

Let some $k>1$ - since for $k=1$ we have nothing to prove ($x=x$). Starting from the fact that $a<b∧ c<d\Rightarrow a+c<b+d$ we arrive to the fact that for any $x>0$ we have $x+x>0$. Similarly, we can have $x+x+x>0$ and, so on, applying this "trick" $k-1$ times we arrive to:

$$\underbrace{x+x+\ldots+x}_{k-1\text{ times}}>0.$$

Now, add $x$ to both sides and we are done:

$$\underbrace{x+x+\ldots+x}_{k\text{ times}}>x\Leftrightarrow k\cdot x>x.$$

So, we have proved that for $k\geq1$ we have $k\cdot x\geq x$.

Now, since $x\mid y$ we have that $y=k\cdot x$ for some positive integer $k$, which implies that: $y\geq x$.

In general, in cases where a constructive proof is easy and possible, I usually avoid proof by contradiction.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Your first equivalence is wrong. For $a=c=b=0$, $d=1$ the RHS is true while the LHS is false. $\endgroup$
    – Jasper
    Commented Oct 8, 2019 at 12:08
  • $\begingroup$ @Jasper Yeap, clumsiness, Thanks! $\endgroup$
    – Vassilis Markos
    Commented Oct 8, 2019 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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