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

Proof of If S(m)=S(n), then m=n

  1. Nov 9, 2012 #1
    Proof of "If S(m)=S(n), then m=n"

    Hello all. I have a question regarding the statement

    If S(m)=S(n), then m=n, where S(m)=m[itex]\cup[/itex]{m}, the successor of the natural number m.

    I have come across two proofs for the above.

    1. This one is as simple as observing the fact that
    if S(m)=S(n), then [itex]\bigcup[/itex]S(m)=[itex]\bigcup[/itex]S(n) and since m and n are transitive (a set A is transitive if x[itex]\in[/itex]a[itex]\in[/itex]A[itex]\Rightarrow[/itex]x[itex]\in[/itex]A), it implies that m=n (for transitive sets like A, it can be proved that [itex]\bigcup[/itex]S(A)=A).

    This cheeky and cute proof is from Enderton's book.

    2. This proof is a longer one which is given in Halmos' book and Hrbacek and Jech's book
    follows a similar line of thought.

    It involves proving two Lemmas. To quote him,

    This is basically proving the ideas related to order defined on the set of natural numbers.

    I wish to know the reason, if there is any, as to why one proof might be better than the other. Proper perspective always helps in understanding abstract mathematical concepts. Your input is greatly appreciated.
  2. jcsd
  3. Nov 10, 2012 #2


    User Avatar
    Science Advisor

    Re: Proof of "If S(m)=S(n), then m=n"

    Hey StatOnTheSide.

    I just wanted to make a general comment about one proof being better than the other: I don't think that one proof is necessarily better than the other since all ways will provide some kind of insight that another may not (assuming all proofs don't drag on too much).

    They both say the same thing anyway (in terms of the statement of the proof) but one is not more correct than the other (since it is a proof and all proper proofs in mathematics are equivalent in terms of the two statements being equal under the appropriate logical system): it's just that one establishes it in a different way.

    Mathematics is like this: there are many ways to do something and when things are consistent and in a system that makes sense, then all paths from A to B take you from A to B regardless of what has happened in-between.
  4. Nov 10, 2012 #3
    Re: Proof of "If S(m)=S(n), then m=n"

    Thanks Chiro. I thought of asking because the length of the two proofs are very different. Proof 1. is like a one line statement in Enderton's book while proof 2. runs to like a page or two in Halmos' book and even in Hrbacek's book. I was just curious to know why one would write a one page proof when there is a one line proof for the same statement.

    Thanks very much for your input. :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook