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.

My question can be stated quickly:

I would like to see a construction of the coequalizer of two arbitrary Poset morphisms (along with a proof of its correctness, of course).

Thanks!


(The stuff beyond this point is of dubious value; I provide it mostly to show why I've come to regard the question above as a sufficiently non-trivial one, certainly not a trivial extension of the analogous construction for Set. If you don't need convincing of any of this, you won't miss anything if you skip it.)

In general, the coequalizer object for the corresponding set functions cannot necessarily be ordered so as to ensure that the coequalizing map is order-preserving. (In case my reasoning is wrong, I give an example of what I mean at the end of this post). I've come up with "improved" constructions that attempt to remedy the shortcomings of the Set construction when applied to Poset, but proving their correctness involves exposure to lethal doses of tedium, which I'd prefer to avoid.

Googling for the problem of constructing coequalizers in Poset has turned up surprisingly little (which, of course, I attribute to the lethality of tedium). If anyone can point me to one such construction, and more importantly, to a proof of that the resulting coequalizing map is indeed order-preserving, I'd appreciate it.

BTW, in ch. 6 of Arbib & Manes, the authors give a theorem that ensures the admissibility of a map if there's an "optimal lift" for (in this case) its domain. (I post this in case their terminology is sufficiently standard to be informative to some of the readers of this post, since A&M's definition of this concept depends on a fair amount of preliminary groundwork.) If I understand their argument at all, the problem of finding an "optimal lift", in this case at least, doesn't look any easier than the problem of constructing the coequalizer object in the first place. (Perhaps what they have in mind is that one may be able to prove the existence of such an optimal lift without actually having to construct it, but this I would find very unsatisfying.)

For a simple example of a Set coequalizer that cannot be made order-preserving, consider the automorphisms $i \mapsto i$ and $i \mapsto i + 2$ on $\mathbb{Z}$, equipped with its standard order (hence, these are Poset morphisms). Their standard Set coequalizer is the quotient of $\mathbb{Z}$ by the equivalence closure of $\{\;(i, i + 2) \;|\; i \in \mathbb{Z}\;\}$. If $q$ is the canonical projection of $\mathbb{Z}$ onto this quotient, then we have $q(i+1) \neq q(i) = q(i+2), \forall i \in \mathbb{Z}$, which rules out the existence of any order for the quotient that would render $q$ order-preserving.

share|improve this question
1  
I could be missing something simple, since I don’t do category theory, but can’t you just define the same equivalence relation as in Set, use the given partial order to define the obvious preorder (quasiorder) on its equivalence classes, and collapse that to the natural quotient partial order? In your example, for instance, you’d get initially two equivalence classes, $E$ and $O$, on which the induced preorder is $E\precsim O\precsim E$, so you’d end up with the trivial poset. –  Brian M. Scott Feb 27 '12 at 11:23
    
@BrianM.Scott:since I posted my question I thought of the same strategy. I suspected it would be something like this, but was hoping that answers to the question would point me to the standard nomenclature/algorithm/construction, etc. I did find that the construction you describe is sometimes called the "antisymmetric quotient (of a preorder/quasiorder)". Also, as I mentioned in the post, I have reasonably simple algorithm that in effect combines both quotient operations into one. I'm trying to find a proof that it in fact yields a valid poset. This may be $\cdots$ [continued] –  kjo Feb 27 '12 at 13:14
    
[continued] $\cdots$ unreasonably difficult and not sufficiently light-shedding to be worth the effort. Of course, I must also prove that the resulting poset is in fact the desired coequalizer. Thanks for your comment! –  kjo Feb 27 '12 at 13:16

1 Answer 1

Brian M. Scott's comment is more or less a complete answer to the question (any cocone admits a map from the set-theoretic coequalizer with the obvious preorder and also necessarily collapses equivalence classes).

I'd just like to point out that this is an argument for working in the category of preorders instead of the category of posets, since in the former category you no longer need to perform the quotient. Note that the forgetful functor from posets to sets has a left adjoint (take the antichain on a set) but does not have a right adjoint; consequently it preserves limits but can't be expected to preserve colimits. But the forgetful functor from preorders to sets has the same left adjoint as above but also has a right adjoint (make every element of a set less than or equal to every other element), hence it preserves both limits and colimits.

share|improve this answer

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.