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\inn, b. m=n, or c. n\inm".
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\inn, then n\notinm as otherwise, 3 implies that m\subsetn 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\subsetn^{+} (n^{+} meaning successor of n). Then either n belongs to E or it doesn't. If n doesn't belong to E, then E\subsetn 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\ink or k\inn. 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\ink, 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\inn. 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.
