Proving Existence of an Element in a Non-Empty Subset of Natural Numbers

[StatOnTheSide]

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

Prove that if E is a non-empty subset of some natural number, then there exists an element k in E such that k \in m whenever m is an element of E distinct from k.

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.

 

[micromass]

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

 

[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.

 

[micromass]

Try to construct a proof by induction.

 

[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.

 

[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\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.

 

[micromass]

Seems ok!

 

[StatOnTheSide]

Thanks very much Micromass!

 

[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?