1

I want to solve this proof by the method of Contradiction. Though without using the well ordering principle. I don't have any idea how to start. I have found other ways to prove this theorem but only by using the well ordering principle. So is it even possible to solve without using the well ordering principle?

P.S. I'm new so any advice on formatting or setting up a question would be much appreciated. Thank you.

ShrooMsss
  • 13

1 Answers1

3

Suppose for a contradiction that $$m<a\quad\text{ but }\quad m\not\leq a-1$$ (Assume that $a\geq2$ since otherwise $a-1$ is not a natural number.)

Note that $m\not\leq a-1$ is completely equivalent to $m>a-1$. Combining those inequalities we get the following: $$a-1<m<a$$ This is a contradiction because you cannot fit a natural number strictly between two adjacent natural numbers. In particular since $m<a$ we have that $a-m$ is a natural number, and from $a-1<m$ we can obtain $$a-m<1$$ which contradicts the well-ordering principle.

  • Thank you, I understand how the contradiction a -1 < m < a works but what exact statement is it contradicting or would it just be considered a fact therefore makes it a contradiction against the original theorem? – ShrooMsss Mar 26 '19 at 04:07
  • Oh, if you are wanting to be more formal, I think you can first say that since $m<a$ then $a-m$ is a natural number. Then from $a-1<m$ you can obtain $a-m<1$, which contradicts well-ordering. In fact let me edit my answer since that seems to be the point. –  Mar 26 '19 at 04:10
  • You beat me to it; contradiction is a clean and easy approach here. +1 – ThisIsNotAnId Mar 26 '19 at 04:10
  • Okay, Thank you – ShrooMsss Mar 26 '19 at 04:11
  • I think have to use well-ordering, since for example if $m$ and $a$ were real numbers then the statement would not be true. –  Mar 26 '19 at 04:14
  • The set ${n/2 \mid n \in \mathbb{N}}$ is well-ordered by the "natural" ordering relation, and yet it does not satisfy $m < a \Rightarrow m \leq a-1$. – Fabio Somenzi Mar 26 '19 at 04:48