Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
You are looking at total orders, partial orders, and/or preorders. en.wikipedia.org/wiki/Preorder; en.wikipedia.org/wiki/Partial_order; en.wikipedia.org/wiki/Totally_ordered_set. The "consistency" means that the total order is a "linear extension" of the partial order. It's part of Order Theory (not abstract algebra). en.wikipedia.org/wiki/Order_theory –  Arturo Magidin Dec 18 '10 at 6:37
    
@Arturo - can you make that an answer? I haven't checked yet, but I may want to accept it - hard to do with a comment. –  Steve314 Dec 18 '10 at 6:46
    
Done. –  Arturo Magidin Dec 18 '10 at 6:54
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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