7
$\begingroup$

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.

  • 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.2012-02-27
  • 0
    @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]2012-02-27
  • 0
    [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!2012-02-27
  • 1
    See also http://mathoverflow.net/questions/219741/quotients-of-posets2016-02-11

1 Answers 1