🚀 go-pugleaf

gudeman@cs.arizona.edu (David Gudeman) writes:

>In article  <1991Apr22.153149.8082@newcastle.ac.uk> Chris Holt writes:
>]What would be nice would be something of the form
>]
>]Sort S <=
>]    where
>]    S : sequence of D
>]    D : domain
>]    <= : partial_order (D x D -> boolean)
>]        where
>]        partial_order : transitive & reflexive & antisymmetric

>I know that is the standard solution, but I wonder if a better
>solution wouldn't be a function $ord : D -> Int$ that maps domain
>objects into arbitrary integers with the property that if $d1 < d2$
>by the partial order, then $ord(d1) < ord(d2)$.  ($d1 < d2$ means that
>$d1 <= d2$ and $d1 =/= d2$.)

There is no such function mapping character strings to integers.  Note
that "a" < "aa" < "aaa" < ...infinitely many strings... < "b".  No subset
of the integers has this property.  See any set theory book for a
discussion of transfinite ordinals.

Hans
boehm@xerox.com