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

Well-ordered set of Natural Numbers

  1. Apr 20, 2008 #1
    I was reading "Introduction To Set Theory" by Karel Hrbacek and Thomas Jeck and stuck with some logical trap in the proposition that "([tex]\textbf{N}[/tex],[tex]\prec[/tex]) is a well ordered set" where [tex]\textbf{N}[/tex] is set of all natural numbers. I will try to present the argument briefly to clarify the subjective trap that i am facing.

    First, the least element is defined as,
    If R is an ordering of set A and B[tex]\subseteq[/tex]A, then b[tex]\in[/tex]B is called least element of B in the ordering R if bRx for all x[tex]\in[/tex]B

    The relation [tex]\prec[/tex] on [tex]\textbf{N}[/tex] is defined as follows,
    m[tex]\prec[/tex]n if and only if m[tex]\in[/tex]n

    Third, ([tex]\textbf{N}[/tex],[tex]\prec[/tex]) is a linearly ordered set because [tex]\prec[/tex] is a strict ordering on [tex]\textbf{N}[/tex] and every two elements of the [tex]\textbf{N}[/tex] is comparable in [tex]\prec[/tex]

    Fourth, (A,R) will be called well-ordered if every non-empty subset of A has least element in the linear ordering R.

    Now, the the the trap is,
    if ([tex]\textbf{N}[/tex],[tex]\prec[/tex]) is a well ordered set, then every non empty subset of [tex]\textbf{N}[/tex] will have least element in [tex]\prec[/tex].
    Suppose, B={n} for some n[tex]\in[/tex][tex]\textbf{N}[/tex]
    So, B is a subset of [tex]\textbf{N}[/tex] and if we say that S has least element, b, then
    b[tex]\prec[/tex]x for all x[tex]\in[/tex]B
    Since B is singleton, it implies from above assumption that n[tex]\prec[/tex]n or n[tex]\in[/tex]n , which i guess violates Axiom of Choice.

    I may have misinterpreted some (or all) of the definition, thats why i am here asking for help. I am not a Math Professional or Math Student but pursue Math for personal interest of theory, so if i have asked very stupid question i do apologize for that.

  2. jcsd
  3. Apr 20, 2008 #2


    User Avatar
    Science Advisor

    Okay, so, since you are talking about m being a member= of n, this is the model for the natural numbers in which 0= empty set, 1= set whose only member is the empty set, 2 is the set whose only members are 1 and 2, etc.

    You mean that B is the set containing the single natural number "n"? But what is S here? I think you meant B itself. Obviously, if B contains only the natural number n, then its least element is n. Oh, I see your difficulty. This definition is strict inequality. Clearly, it is impossible for any member of a set B to be strictly less than every member of B- it can't be strictly less than itself! You need to say "b is the least element of B if and only if it is less than every other member of B". That is [itex]b\prec a[/itex] for every [itex]a\in B[/itex] and [itex]a\ne b[/itex].

  4. Apr 20, 2008 #3
    Thanks for your reply.

    Oops, thats my mistake. Yes , it should be B instead of S.
    That means B does not have a least element as per as the above definition of least element in a strict ordering, since B={n} and n=n .

    Then set of all natural numbers is not well-ordered, because each subset of N is supposed have least element in [tex]\prec[/tex] in order to be called as well-ordered.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook