Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem on natural numbers.

  1. Jun 13, 2012 #1
    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. jcsd
  3. Jun 13, 2012 #2
    It is clear that k must be the least element of E. Do you know why the set E has a least element?
  4. Jun 13, 2012 #3
    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.
  5. Jun 13, 2012 #4
    Try to construct a proof by induction.
  6. Jun 13, 2012 #5
    Thanks micromass. I will try to figure out the proof using induction and will post it here once I make progress. Thanks once again.
  7. Aug 8, 2012 #6
    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.
  8. Aug 11, 2012 #7
    Seems ok!!
  9. Aug 11, 2012 #8
    Thanks very much Micromass!
  10. Nov 8, 2013 #9
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook