1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set theory - wellorders

  1. Sep 20, 2007 #1
    1. The problem statement, all variables and given/known data

    Show that if every total order of a set x is a well-order, then there is no bijection between x and [tex]x\cup\{ x\}[/tex] = Sx.


    3. The attempt at a solution

    Suppose there was, then you can have a total order on x and an induced total order on Sx. But this induced order on Sx is a total order on x. Something bad's supposed to happen here.
     
  2. jcsd
  3. Sep 22, 2007 #2
    Anyone?
     
  4. Sep 22, 2007 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you know of any examples of total orders that are not well-orders?
     
  5. Sep 23, 2007 #4
    Yes, the usual order on the real numbers.
     
  6. Sep 23, 2007 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Okay, so you've proven that if every total order of a set x is a well-order, then x does not have the same cardinality as R. (right?)
     
  7. Sep 24, 2007 #6
    We can't assume the axiom of infinity on this question (nor do we need to, apparently), so we can't assume that R exists, or even N, for that matter.

    Basically the two conditions are equivalent to the fact that the set x is "finite". This question is actually part of a bigger question asking me to prove the equivalence of 6 statements, and this is the link in the chain that I can't prove.

    I am certain I'm on the right track with the two total orders there, but I can't see a contradiction.
     
  8. Sep 24, 2007 #7
    Here's the whole question. Prove the following are equivalent:

    (a) Every injective function from x to x is surjective.
    (b) There is no proper subset y of x in bijection with x.
    (c) Every surjective function from x to x is injective.
    (d) There is no proper superset y containing x in bijection with x.
    (e) Every total order of x is a well order.
    (f) There is no bjection between x and Sx = xU{x}.
     
  9. Sep 24, 2007 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This was my idea. Certainly, the thing you're trying to prove is an immediate consequence of this assertion.

    The word "finite" and the phrase "well-order" suggest that induction might be useful.



    By the way, is it obvious that every set has a total ordering?
     
  10. Sep 25, 2007 #9
    Every set is in bijection with some cardinal. Every cardinal is an ordinal (under some models). Every ordinal is totally ordered by [tex]\in[/tex], so every set has a total ordering.
     
  11. Sep 25, 2007 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Whoops, I forgot to say 'without the axiom of choice'.


    I was pondering the idea of trying to construct a counterexample; because condition (e) says "Every total order...", and you were assuming one existed, that prompted me to think about the case of a set x without any total orderings. Then, one of two things happen:
    (1) The statement you are trying to prove is false.
    (2) The set x is not bijective with Sx.

    And so, I was mulling the possibility of having an infinite set x that is not bijective with Sx. Clearly this cannot happen if we assume axiom of choice, but I am not so familiar with the case where we reject the AoC, and I'm wondering if this is possible!
     
  12. Sep 26, 2007 #11
    I don't think cardinality can be used as an argument, since Q is the same cardinality as N, but is not well-ordered.

    I'm not familiar with set theory enough to say what you can't do without the axiom of choice. AC seems pretty intuitive to me.

    I do have a side question: if the class of all things is in bijection with the class of all ordinals, then you can order the class of all things. What's wrong here?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Set theory - wellorders
  1. Set theory (Replies: 3)

  2. Set Theory (Replies: 2)

  3. Set theory (Replies: 2)

  4. Set Theory (Replies: 2)

  5. Set Theory (Replies: 5)

Loading...