0

I'm having a very rough time wrapping my head around with well-ordering principle, and how to use it with proofs..

For example:

If S is a subset of Z(integers) which is bounded below, then there is a natural number k so that $$ S + k \subset N $$

Honestly, I have no idea where to start... but my understanding of well-ordering principle with the term bounded below is that a set S of integers is bounded below if there is an integer n (smallest element) so that n <= s for all elements s of S.

But what exactly is happening here with the set S being added to the natural number k? You can't really add a number to a set, can you?

A walkthrough of the proof would be appreciated..

dendritic
  • 315

1 Answers1

1

While, pedantically, you can't "add a number to a set", you can add the same number to every element of a set, and that is what $k+S$ indicates.

If every element of $S$ is positive then there is nothing to prove. Otherwise, let $$A=\{a\in S|a\leq 0\}$$ $A$ has a lower bound, say $M$, so that $M\leq a$ for all $a\in A$. Since $M$ and $a\in A$ are all nonpositive, we have $-M=|M|\geq |a|=-a$ for all $a\in A$. We may then choose $k=|M|+1$, as $|M|+1$ is larger in absolute value than every element of $A$ by at least $1$, so adding it to any element of $A$ yields a positive number. (Every element of $S$ that is not in $A$ is already positive, so adding $|M|+1$ to them will also yield a positive number.)

Matt Samuel
  • 58,164
  • No, bounded below and "having a smallest element" are not the same thing (without the well-ordering principal.) For example, the positive rationals $x$ with $x^2>2$ are bounded below. But you are correct that this theorem doesn't need a least element. – Thomas Andrews Sep 19 '15 at 02:01
  • @ThomasAndrews duh. Let me fix it. – Matt Samuel Sep 19 '15 at 02:02
  • I have a question about the term "bounded below". For example, in a number line from 1 to 8. If I let the set S be {6,7,8], then would this set be "bounded below" because there is an integer n (1, 2, ... , or 5) such that n is less than all elements of the set S? – dendritic Sep 19 '15 at 02:08
  • @dendritic Yes, a lower bound of a set is any element that is less than or equal to every element of the set, so $6$ would also work. – Matt Samuel Sep 19 '15 at 02:09
  • Alright, makes sense. Thanks! By what reasoning can you take the absolute value for M and a? – dendritic Sep 19 '15 at 02:29
  • @dendritic I learned most of the set theory I know from the textbook "Topology" by Munkres, Chapter 1. He goes pretty deeply into it, for example one of the exercises is to prove the well ordering theorem given the axiom of choice (it's a many-part exercise). I only use the internet for casual reference, and for that I use Wikipedia, which is terrible for learning, so I don't know any good sites. – Matt Samuel Sep 19 '15 at 02:34
  • @dendritic YOU EDITED YOUR COMMENT. To answer: it seems you're allowed to use basic properties of arithmetic since the problem involves addition. – Matt Samuel Sep 19 '15 at 02:38