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

Problem on successor/predecessor set

  1. Jun 7, 2012 #1
    Hi All. There is a problem in Halmos's Naive Set Theory on page 49. It states that

    "if n[itex]\neq[/itex]0 and if n is a natural number, prove that n=S(m) for some natural number m." Here, S(m) denotes the successor of the number m and is given by S(m)=m[itex]\bigcup[/itex]{m}.

    My attempted solution to this was to use induction. Let P be a set which has "0" in it. Also, let P contain all the natural numbers such that if n[itex]\in[/itex]P, then n=S(m) for some natural number m. Now 1=S(0). So 1[itex]\in[/itex]P. 2=S(1). Hence 2[itex]\in[/itex]P. Now let this be true for some n. Now as the successor of n, namely S(n) is, by definition, successor of n, we have that S(n) has a number (equal to n) such that S(n)=S(n). Therefore S(n)[itex]\in[/itex]P. Hence by induction, it must be true for all n.

    Since every natural number is in P, which posesses the property that all its elements have a predecessor, it must be true that all natural numbers have a predecessor.

    I have two questions.

    1. Is my proof right?

    2. If it is wrong, kindly point out the mistake

    3. If it is right, then I feel that "S(n)[itex]\in[/itex]P whenever n[itex]\in[/itex]P" is a funny statement. S(n)[itex]\in[/itex]P even if n[itex]\notin[/itex]P because it has a number n which is its predecessor. Why do we need n to be in P to prove it? In other words,
    can this be proved without using induction? Please let me know.
    Last edited: Jun 7, 2012
  2. jcsd
  3. Jun 11, 2012 #2
    I also wanted to add that I read elsewhere that Induction can be used to prove it. It is in Terence Tao's book and is contained as an excercise where he has hinted that Induction has to be used. I just wish to know if I have used induction properly.
  4. Jun 13, 2012 #3
    Answering this question really depends on how the natural numbers are being defined. I don't have Halmos' book, but a standard construction is that 0 is defined to be the empty set, and every other number is defined to be the set containing all the previous 'numbers'. So [itex]0=\emptyset, 1= \{\emptyset\}, 2=\{\{\emptyset\},\emptyset\}[/itex] etc. From what you write it seems Halmos is using this definition, though I was slightly thrown initially by your use of [itex]\bigcup[/itex] rather than [itex]\cup[/itex].

    This is a recursive definition, and an inductive proof of the proposition you're asking about is trivial when viewed this way. We easily establish that 1 has the required property, which is our base case, and the successor case is tautological. Of course, this requires that the natural numbers be defined in this way. Depending on how exactly Halmos has set things up it may be more complicated, and there's also the possibility that he has formally defined induction in such a way as to require more work here, but basically the result falls out of the recursive definition of natural numbers.

    With regard your proof, I think you have an idea that leads to a correct answer, but it seems a little round about. I don't understand, for example, why you introduce P rather than just working with the set of all (non-zero) natural numbers directly. Possibly this is related to the way induction has been introduced. Also, your statement " let P contain all the natural numbers such that if [itex]n\in P[/itex], then [itex]n= S(m)[/itex] for some natural number [itex]m[/itex]" is a little confusing , and is not formally correct as it references itself, and in any case P could be empty if we overlook the formal problem. I think you want to say that P contains every natural number that is a successor.
  5. Jun 13, 2012 #4
    Hi dcpo. Thanks very much for the reply.

    Halmos has defined 0=∅, 1 as being equal to {0}, 2 as being equal to {0,1} etc. In general, n+[itex]\equiv[/itex]n[itex]\cup[/itex]{n}.

    I am sorry about the confusion. I meant to use [itex]\cup[/itex] :).

    It is true that natural numbers have been defined that way.

    I wish to quote the induction definition here from the book. It states:

    Also, he states elsewhere that any property is identified with a set. In his own words,

    That is true. I introduced P because he has defined principle of induction to be the fact that a subset S of ω is equal to ω if it is a successor set. I started the proof on the same lines saying that let P (instead of S) be the set of all natural numbers having a predecessor and also the number 0. Then 1, 2, 3,.. all belong to it. Also, whenever n belongs to it, so does n+ in a trivial way. Hence P=ω.

    That is correct. If I were to reword it, I would say "let P be the set containing 0, and all the numbers which have a predecessor. Then 1, 2, 3..... all have predecessors and hence, are in P........"

    With this correction, will the proof look OK? Please let me know.
    Last edited: Jun 13, 2012
  6. Jun 13, 2012 #5
    With the definition of induction you give the proof is straightforward. You take the set containing 0 along with all natural numbers which have predecessors. The inductive step is a tautology; by definition the successor of every number must be in this set. Therefore your set contains 0 and every successor number, and thus must be the set of all natural numbers, and thus all non-zero natural numbers must have a predecessor. This seems to be what you are getting at but you need to make explicit the induction.
  7. Jun 13, 2012 #6
    Thanks very much dcpo. It feels very comforting to get the right direction while solving problems in something as abstract as set theory :).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook