# A problem on natural numbers.

1. Jun 13, 2012

### StatOnTheSide

Hello all. I have been reading Halmos's Naive set theory. In chapter 12., there is an excercise problem which states

I thought a lot about this but this seems like a theorem to me and is not at all trivial to prove it.

I would greatly appreciate it if you can give me a hint or a clue as to where to begin in order to prove the above.

2. Jun 13, 2012

### micromass

It is clear that k must be the least element of E. Do you know why the set E has a least element?

3. Jun 13, 2012

### StatOnTheSide

Hi micromass. I know that there is a theorem which states that given two natural numbers n and m, either n belongs to m or m belongs to n in case n is not equal to m.
However, I do not know the proof of that and I suppose it appears in later chapters in Halmos's book.

In other words, I do not know the proof for why E has to have a least element even though it is kind of obvious to me. How can a proof of that be constructed? Kindly suggest a hint.

4. Jun 13, 2012

### micromass

Try to construct a proof by induction.

5. Jun 13, 2012

### StatOnTheSide

Thanks micromass. I will try to figure out the proof using induction and will post it here once I make progress. Thanks once again.

6. Aug 8, 2012

### StatOnTheSide

It is interesting that the next chapter in Halmos introduces the concept of order and things become magically simple in the context of proving the above statement.

1. There is a theorem, called the comparability theorem, that he proves, which states that "Two natural numbers m and n are always comparable, meaning exactly one of the following three statements is true: a. m$\in$n, b. m=n, or c. n$\in$m".

2. There is another theorem that he proves which comes in very handy. A natural number is not a subset of any of its elements.

3. Another one he proves: An element of a natural number is also a subset of it.

4. Theorems 3. and 2. imply that a natural number is not an element of any of its elements. ie if m$\in$n, then n$\notin$m as otherwise, 3 implies that m$\subset$n also and this contradicts 2. which states that no natural number is a subset of any of its element.

Now the statement (that any nonempty subset E of a natural number n has an element k such that it belongs to all the other elements of E distinct from k) is true for n=0 as there are no subsets of n in that case for it to be true. Let it be true for n. Now let E$\subset$n$^{+}$ (n$^{+}$ meaning successor of n). Then either n belongs to E or it doesn't. If n doesn't belong to E, then E$\subset$n and hence, induction hypothesis holds. Otherwise, consider E-{n}. If it is empty, there is nothing to be proved. Otherwise, E-{n} has to be a subset of n and hence, induction hypothesis holds for n and there exists an element k of E-{n} such that it belongs to all the other elements of E-{n} distinct from k. Between n and k, the comparability theorem implies the either n=k, n$\in$k or k$\in$n. Now if n=k, then n is the element which belongs to all the elements of E-{n}. This contradicts 4. above as any element of E-{n} is an element of n and n cannot belong to any of its elements from 4. If n$\in$k, then it contradicts 4. again as k is an element of n and hence, n cannot belong to it from 4. Hence the only other option that gets left off is that k$\in$n. Hence k, which was the element of E-{n} such that it belonged to all the elements of E-{n}, is also the element which belongs to E such that it belongs to every other element of E. Hence by induction, it is true for all n.

I would greatly appreciate it if you can provide feedback and let me know if there has been a mistake in the proof I have provided. It looks fine to me but I may not have realized a mistake if I made one.

7. Aug 11, 2012

### micromass

Seems ok!!

8. Aug 11, 2012

### StatOnTheSide

Thanks very much Micromass!

9. Nov 8, 2013

### dustbin

I'm a little bit stuck on this problem myself. I understand the above proof, but I don't want to use the comparability result of the following section.

I'm thinking that since E is nonempty, we can take the intersection of E to establish a minimal element in E... But I am not able to complete the proof. Any hints?