5
$\begingroup$

I'm really sorry if this question has been asked before, I looked but couldn't find anything.

I'm going through an elementary number theory book and in the first chapter it introduces the least integer principle. There is no proof accompanied with it, it just states: "a nonempty set of integers that is bounded below contains a smallest element."

Is the reason the book doesn't give a proof because we take this as an axiom? Or is the proof so trivial that it need not be written?

Thanks!

$\endgroup$
  • $\begingroup$ It depends. It need not be an axiom, but sometimes it is. $\endgroup$ – Git Gud Aug 14 '14 at 18:08
  • 1
    $\begingroup$ It's an equivalent way to express the principle of induction on $\,\Bbb N,\,$ look up well-ordered. $\endgroup$ – Bill Dubuque Aug 14 '14 at 18:15
  • 1
    $\begingroup$ Given the Peano construction of the natural numbers, you can prove the well-ordering property using induction. $\endgroup$ – RRL Aug 14 '14 at 18:17
  • $\begingroup$ If we formalize set theory (the most commonly used formalization is ZFC) then the integers can be defined, and the Least Integer Principle is a theorem. $\endgroup$ – André Nicolas Aug 14 '14 at 18:28
3
$\begingroup$

I'm guessing you are a beginner and hence are expecting a rudimentary explanation. At this level I don't know if you've realised the need to define what natural numbers actually are. I mean it is easy enough to accept them as counting numbers initially. But in formal set theory and laying the foundations for Analysis we do try to develop the natural numbers using (sometimes) a set of five basic axioms.

The thing is one of these axioms must be either the "Well-Ordering Principle" or the "Principle of Mathematical Induction" which we use to inductively construct the whole set $\Bbb N$. So at this level one of these two principles must be accepted as part of the definition of the set $\Bbb N$. If you accept Mathematical Induction you can prove the Well Ordering Principle as a theorem. If you accept the Well-Ordering Principle you can use it to prove the Principle of Mathematical Induction. That is what people say when the two conditions are equivalent. Note that both conditions claim to be a "Principle" and not a theorem.

$\endgroup$
  • $\begingroup$ Thank you, that is very helpful. And you're right, I am a beginner at this. I'm interested, what are the other four axioms,you mentioned? Can you provide either a link or a list? Thanks! $\endgroup$ – candido Aug 15 '14 at 14:39
  • $\begingroup$ homepages.math.uic.edu/~kauffman/Landau.pdf $\endgroup$ – Ishfaaq Aug 15 '14 at 15:21
1
$\begingroup$

This is called the Well Ordering Principle and when I was taught it, there was an accompanying proof by induction. Unfortunately the proof for Induction was proved using the Well Ordering Principle by my teacher and he did mention that it was a bit circular and didn't expand on it anymore. http://www.cs.bsu.edu/homepages/fischer/math215/wellorder.pdf this is essentially the proof

$\endgroup$
  • $\begingroup$ Thanks for the reply. In your link, the well ordering principle says that all subsets of the natural numbers have a least element. Does this even mean infinite subsets of the natural numbers? $\endgroup$ – candido Aug 14 '14 at 18:22
  • $\begingroup$ Yes, natural numbers are non-negative so will always have a lowest bound of 0. $\endgroup$ – user162473 Aug 14 '14 at 18:25

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.