Ordering

I define an ordering on a set S as a relation < defined on S such that for any a and b that are members of the set if a =\= b then either a < b xor b < a (xor is meant to make it explicit that this is an exclusive or) and such that if a < b and b < c then a < c. You could basically make any ordering you choose to care about for a particular set. We tend to take 3 < 4 but the definition of an ordering would still work just as well if 4 < 3 with all the other appropriate changes made (for instance if 4 < 3 then that would be a fine ordering relation but it would make it damn near impossible to make ordering work with a nice definition of addition) I will define a listing of a set as a injective mapping from the set of objects to the positive integers. If you think about any list you have ever seen you know that you can always number the items on the list 1, 2, 3.... and so on. While many lists don't have this numbering actually done that is not important, here I am simply looking for the quality of what makes something listable. Now for the paradox, the set of real numbers is not listable no matter how you try to list them any list you make will always leave out some real number. You can see this from the cantor diagonalization argument So there exist sets of things which can be ordered but which cannot be listed.
Intuitively it seems that ordering something and listing something are more or less the same. Taking a pile of rocks and putting them in order seems much the same process as taking those rocks and writing them down in order on a piece of paper. In fact it would seem that ordering is an even stronger requirement than listing since if you put the rocks in order along a line then the job of listing the rocks is done for you already. But from the example of the reals we know that this is not in fact the case apparently you can have orderability without having listability. Clearly any finite or even countably infinite set of objects is both orderable and listable, since by definition any countable set can be mapped onto the integers and so we can use the ordering relation on the integers to define one on any countable set. But orderability and listability become different when we move into the realm of sets with the cardinality of the reals. Let us go back and define listable and orderable in a little more detail. Listable means that given a set of objects the set is listable iff there exists an algorithm for reading through the set one element at a time so that you will eventually encounter every element in the set. The definition of orderability also changes slightly. A set is orderable if there exists an algorithm that has basically the same properties as an ordering. If the algorithm is given two numbers the algorithm must be able to tell if one number is less than the other in a finite number of steps.

Here is the fun part an ordering algorithm can be allowed to run for an infinite number of steps if it is given two numbers that are the same. The requirement is only that if the two numbers are not the same number that the algorithm will recognize that in a finite amount of time. Whereas the listing algorithm must conclude in a finite time for all elements in the set no matter what. So if you know something about the chomsky hierarchy that means that in some sense at least things that are orderable are recognizable languages whereas things that are listable are decidable languages. That is the difference between a list and an ordering.