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

Homework Help: Cardinality of the set of well-orderings on N

  1. Sep 22, 2010 #1
    1. The problem statement, all variables and given/known data
    How many different ways can one well-order the natural numbers? Different orders are those which are NOT order isomorphic.

    2. Relevant equations

    3. The attempt at a solution
    My approach thus far has been to examine a well-ordering on N. Clearly, any well-ordering is one that satisfies that our well ordering P(a,b), returns an element for the pair (a,b) for a,b in N where the value returned is the least element of the pair. So it must be the case that any well-ordering is at the very least a function from NxN into N. We can take it as known (by a previous problem I solved) that the cardinality of the set of functions from NxN into N [ denoted as N^(NxN) ] is the same as the cardinality of (N^N)^N or the cardinality of R. My problem here is that the set of orderings I have are all linear orders. I seem to think that the set of P that I have define well-orderings as well but I'm not sure that I'm even right or if I am correct, how to show that rigorously. Does anyone have any thoughts on this approach I'm taking to the problem?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted