Consider an sequence of unique values. Each value is composed of a surname and a first name in that order of significance. Based on that, I can define a complete ordering of values in the sequence.

However, I can also usefully define less fine-grained equivalence classes of items that have a "consistent" ordering, but where some values compare as equivalent (and have no particular ordering relative to each other) even though in the "full" ordering they compare as greater and lesser.

For example, sometimes, I may want to search an index for a particular surname, not caring about the first name.

In the most general case, there are finer-grain and coarser-grain but otherwise consistent ways to divide a set of values into equivalence classes and order those classes. There are generally many (mutually incompatible) finer grained orderings for any one coarser-grained ordering. It is possible to have a partitioning that is neither finer-grain nor coarser-grain than another different partitioning.

The trouble is that when I use the terminology of being "consistent", people get confused. A lot of people won't accept that an ordering in which $a=b$ is consistent with (but coarser grained) than one in which $a<b$.

I imagine that there are likely to be official terms to describe these relationships in abstract algebra, but my abstract algebra is pretty limited.

Am I right? If so, which is the relevant field of abstract algebra, and what are the relevant terms?


The concepts you want are those associated with the notion of partial orders, part of Order Theory.

When everything is ordered, you have a totally ordered set (also called linearly ordered set).

When you only worry about, say, last names, if you do not specify any order relations between the people with same last name (neither is greater than or smaller than any other), then you have a partially ordered set. The fact that your total order is "consistent" with the partial order is expressed saying that the total order is a "linear extension" of the partial order.

If you are considering people with the same last name but different first name "equal", then you are dealing with either a preorder, or a (partial or total) order on the set of equivalence classes induced by the preorder.


I would call the relevant maps here order-preserving surjections. Alternately, if instead of using the language of partial orders you want to use the language of preorders, you could say that a preorder $\le$ refines a preorder $\le'$ on the same set if whenever $x \le y$ it is also true that $x \le' y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.