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.

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[itex]\in[/itex]n, b. m=n, or c. n[itex]\in[/itex]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[itex]\in[/itex]n, then n[itex]\notin[/itex]m as otherwise, 3 implies that m[itex]\subset[/itex]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[itex]\subset[/itex]n[itex]^{+}[/itex] (n[itex]^{+}[/itex] meaning successor of n). Then either n belongs to E or it doesn't. If n doesn't belong to E, then E[itex]\subset[/itex]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[itex]\in[/itex]k or k[itex]\in[/itex]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[itex]\in[/itex]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[itex]\in[/itex]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.

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?