Cardinality of the set of well-orderings on N

[factor]

Homework Statement

How many different ways can one well-order the natural numbers? Different orders are those which are NOT order isomorphic.

Homework Equations

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?

 

[mighty2000]

Hello, as a fellow scientist, I believe your approach is a good start. However, I would suggest considering the concept of partial orders as well. A partial order is a binary relation that is reflexive, antisymmetric and transitive. In other words, it is a relation that satisfies the following properties:

1. Reflexive: for any element a in the set, a is related to itself (aRa)
2. Antisymmetric: if a is related to b and b is related to a, then a = b (aRb and bRa implies a = b)
3. Transitive: if a is related to b and b is related to c, then a is related to c (aRb and bRc implies aRc)

A well-ordering is a partial order that also satisfies the following property:

4. Totality: for any two distinct elements a and b in the set, either a is related to b or b is related to a (aRb or bRa)

Using this definition, we can see that there are many possible ways to well-order the natural numbers. For example, we can start with the standard order (1, 2, 3, 4, ...) and then change the order of any two elements (e.g. 1, 3, 2, 4, ...). This would still satisfy the properties of a well-ordering.

Furthermore, we can also consider different ways to define the relation between elements. For example, instead of using the standard ordering of numbers, we could use a different property, such as the number of prime factors, to determine the order (e.g. 1, 2, 3, 5, 4, 7, ...).

Overall, the number of possible well-orderings on the natural numbers is infinite, as there are infinitely many ways to define the relation between elements. I hope this helps guide your approach to the problem.