(Set theory:)
The order type is the abstraction of an order (a total order; I shall use just "order" in this writeup, as this how it's normally encountered). Let (A,<) and (B,«) be two ordered sets. We say they have the same order type if there exists an order preserving mapping from A to B:
- f: A→B, and f is one to one and onto B;
- For any x,y∈A, if x<y then f(x)«f(y).
Note how this extends the notion of cardinality from the category Sets to the category Ordered Sets. In particular, if (A,<) and (B,«) have the same order type then A and B have the same cardinality.
Cantor talked about the concept of "order type" -- all sets of a given order type, but in fact this cannot be presented as a set in modern set theory. However, we do have a class corresponding to an order type. More commonly, if we are given representatives of an order type we can use them to make statements about that order type. Such a statement is well defined if the particular choice of representatives make no difference to the truth of the statement.
Finite sets of a given cardinality have only one order type -- that exemplified by {1,2,...,n}. Thus, notions of cardinality and order type coincide in the finite case. The infinite case is more interesting. For example, N={1,2,3,...} (the set of natural numbers) and Z={...,-1,0,1,2,...} (the set of integers) are both countable sets -- they have the same cardinality -- but their order types are different. For instance, N has a first member, while Z has none. Q (the set of rationals) is also countable, but its order type is dense -- again, different from N and Z. An easy exercise is to show that the set Q∩(0,1) (rationals between 0 and 1) has the same order type as all of Q.
Operations on order types
- We can add order types. If (A,<) and (B,«) are disjoint representatives of two order types, we define their sum as the order → on the union A∪B which places elements of A before elements of B: x→y iff either x∈A and y∈B, or x,y∈A and x<y, or x,y∈B and x«y.
- By using the lexicographic order, we can multiply two order types.
- We can define some, but not all, infinite multiples of order types. If we have ordered sets (Aα,<α)α∈I then we can compute an ordered infinite product if the index set I is well ordered. But usually it won't be, so we cannot compute this product in general.
Unlike for cardinals, the operations on order types are not
commutative. For instance, we can add a set of one element
before or
after a set with the order type ω of the natural numbers. Adding before (and calling the single element "0", for convenience), we have a set with the order type 1+ω of {0,1,2,...}; this has the order type ω of the natural numbers (define f(x)=x+1 to see this). Thus 1+ω=ω. However, when adding after, we get the order type of a set {1,2,3,...,x}, which has a last element. Thus ω+1≠1+ω=ω.
On the other hand, addition of order types is associative. This is a common situation in mathematics. It probably shows that despite intuitive expectations to the contrary, associativity is more fundamental and important than commutativity. Go figure.
Problems
We don't have a good concept of comparability of order types (we cannot say "which is larger"). We could try to say one order type is smaller than another if an order type can be added to the first to get the second. Unfortunately, the sum of two copies of the order type of Q is the order type of Q (e.g., note that the rationals <sqrt(2) and the rationals >sqrt(2) both have the order type of Q). And ω and ω* (the order type of {...,-3,-2,-1,0}) remain incomparable. This definition just doesn't have the properties we'd like.
We cannot define ordered infinite products. We cannot give a decent idea of powers of order types. We cannot do any of the things we'd like to do on "numbers".
So order types don't take the place of transfinite "numbers". Instead, Cantor limited himself to order types of well ordered sets. These have much nicer properties. They are the basis for the "ordinal numbers".
Of course, definitions of arithmetic operations on ordinals are easier. But we need to show that they coincide with the wider definitions -- given above -- for arithmetic operations on order types.
Order types remain a useful tool in the mathematician's arsenal. Many (most) interesting orders aren't well ordered. But being able to add and multiply them, even to the limited extent afforded by order types, can be useful.