Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: mathematics

Topic: order theory terminology

Max New (Apr 12 2023 at 18:01):

Does anyone know a word for this concept in order theory? I have a monotone function $f : P \to Q$ and it is not just surjective but for any $q \leq q'$ in $Q$ there exists $p \leq p'$ in $P$ such that $f(p) = q$ and $f(p') = q'$. It's not the same as being a full functor because the $p$ depends on both $q$ and $q'$.

Max New (Apr 12 2023 at 18:04):

In fact my example is not full: there are cases where $f(p) \leq f(p')$ but not $p \leq p'$

Amar Hadzihasanovic (Apr 12 2023 at 19:28):

This is equivalent to saying that

• $f$ is surjective, and
• $f$ maps lower sets to lower sets.

Indeed, take $q \leq q'$, by surjectiveness there exists $p'$ with $q' = f(p')$, and since the image of the lower set of $p'$ is the lower set of $f(p')$, there must exist $p \leq p'$ such that $f(p) = q$.

I would simply call the second condition being a closed map, since lower sets are the closed sets for the Alexandrov topology on the poset.

Max New (Apr 13 2023 at 14:30):

Nice! Now that I've seen your formulation it also looks like a fibration condition? I.e., if $q \leq f(p')$ then there exists $p \leq p'$ with $f(p) = q$

Max New (Apr 13 2023 at 14:33):

But I don't think my example is a fibration so something must be wrong

Mike Shulman (Apr 13 2023 at 15:45):

I don't think Max's condition implies that $f$ maps lower sets to lower sets. If I read it correctly, not just $p$ but also $p'$ can depend on both $q$ and $q'$.

Max New (Apr 13 2023 at 16:51):

I guess in category theory terminology this would be saying that the induced functor on the arrow categories is essentially surjective?

Graham Manuell (Apr 13 2023 at 17:38):

I believe these are precisely the descent morphisms in the category of posets -- that is the pullback-stable quotient maps. See here for more details.

Amar Hadzihasanovic (Apr 13 2023 at 18:08):

Mike Shulman said:

I don't think Max's condition implies that $f$ maps lower sets to lower sets. If I read it correctly, not just $p$ but also $p'$ can depend on both $q$ and $q'$.

Oh, that's true.

Tomáš Jakl (Apr 14 2023 at 06:42):

Max New said:

Does anyone know a word for this concept in order theory? I have a monotone function $f : P \to Q$ and it is not just surjective but for any $q \leq q'$ in $Q$ there exists $p \leq p'$ in $P$ such that $f(p) = q$ and $f(p') = q'$. It's not the same as being a full functor because the $p$ depends on both $q$ and $q'$.

This looks like something modal logicians and people studying (traditional) Kripke semantics of intuitionistic logic would know and have a name for.

dusko (Apr 14 2023 at 18:09):

Max New said:

Does anyone know a word for this concept in order theory? I have a monotone function $f : P \to Q$ and it is not just surjective but for any $q \leq q'$ in $Q$ there exists $p \leq p'$ in $P$ such that $f(p) = q$ and $f(p') = q'$. It's not the same as being a full functor because the $p$ depends on both $q$ and $q'$.

it seems natural to call it order-surjective. and then $g:Q\to R$ would be order-injective if for any $x\leq x'$ and $y\leq y'$ in $Q$ holds that whenever $g(x)=g(y)$ and $g(x')=g(y')$ then $x=y$ and $x'=y'$. hmm.

call $f:P\to Q$ preorder-surjective if $f:P_f\to Q$ is order-surjective, where $P_f$ is the preorder with the underlying set $P$ but obtained as the transitive closure of $P$ under $x\sim y \iff f(x)=f(y)$. then the preorder-surjective and order-injective maps form a factorization system.

i am sure someone somewhere must have used it. to decompose a monotone day...

but it gets interesting to lift to categories. is there a universal way to make an arbitrary functor conservative by adding unique isomorphisms to the domain category?

Mike Shulman (Apr 14 2023 at 18:11):

dusko said:

is there a universal way to make an arbitrary functor conservative by adding unique isomorphisms to the domain category?

I believe the class of conservative functors is the right class of a factorization system on $\rm Cat$, whose left class is the "iterated localizations" obtained by repeatedly adding formal inverses to morphisms. So in particular you can factor an arbitrary functor as an iterated localization followed by a conservative functor. Is that what you have in mind?

Jonas Frey (Apr 14 2023 at 18:18):

Graham Manuell said:

I believe these are precisely the descent morphisms in the category of posets -- that is the pullback-stable quotient maps. See here for more details.

Nice! Yes, it's Proposition 2.5 in the paper you cite.

dusko (Apr 14 2023 at 18:19):

[sorry, this is the answer to mike shulman.]

no. there is the obvious lifting of order-surjections to categories. i am asking how to extend them to a factorization system.

we just saw that order surjectons on posets become epis of a factorization system if we force them to be conservative.

in other words: if the monics are essentially surjective faithful functors, who are the epis?

Mike Shulman (Apr 14 2023 at 18:26):

Why is that "in other words"?

dusko (Apr 21 2023 at 01:29):

Mike Shulman said:

Why is that "in other words"?

sorry i hadn't seen this.

i think the categorical version of the above factorization would be something like $F:{\cal A}\twoheadrightarrow {\cal F} \hookrightarrow {\cal B}$ where $\cal F$ has the same objects like $\cal B$ but only those arrows that arise as composites of arrows $Fa$ from $\cal A$. i didn't check any of this with a pencil (i hope none of my students are on this list) but i think the functors which "cover" in the sense that every morphism in the codomain category is a composite of the images (like the rationals "cover" the reals) and the functors which are faithful and essentially surjective are orthogonal.

it probably isn't very nice to have these "covers" defined as closures of the images --- but it does have the same flavor like the posets: you view the functor as the square formed by the object part, the arrow part, and the domain-codomain projections, and the epi factor kees the object part of the functor and the "surjection", whereas the mono factor is the identity on objects and the inclusion on morphisms... i don't know whether it's interesting but that answers why having faithful and essentially surjective functors as monics is "in other words" for having surjections on morphisms as epis... (too many words)

Mike Shulman (Apr 21 2023 at 04:52):

dusko said:

i think the functors which "cover" in the sense that every morphism in the codomain category is a composite of the images (like the rationals "cover" the reals) and the functors which are faithful and essentially surjective are orthogonal.

I don't see why that would be the case.

dusko (Apr 21 2023 at 05:08):

Mike Shulman said:

dusko said:

i think the functors which "cover" in the sense that every morphism in the codomain category is a composite of the images (like the rationals "cover" the reals) and the functors which are faithful and essentially surjective are orthogonal.

I don't see why that would be the case.

i don't see why you don't see that. can you explain how you tried to see it and failed?

Mike Shulman (Apr 21 2023 at 16:16):

You didn't give any argument for it. The burden of proof is on the person making a claim.

John Baez (Apr 21 2023 at 19:19):

If Dirac heard someone say "I don't see why that would be the case", he would just nod in recognition of this statement of fact.

dusko (Apr 27 2023 at 02:28):

Mike Shulman said:

You didn't give any argument for it. The burden of proof is on the person making a claim.

hmm. "burden of proof" is meant to prevent unfounded accusations, not for math. math can probably only exist if everyone tries to maximize and not minimize the burden of proof that they carry. if one side is not interested in a proof, then they can just repeat that they don't understand it ad nauseam. we all get that from students once in a while, don't we :)

Mike Shulman (Apr 27 2023 at 04:46):

I didn't mean to refer to the formal legal terminology. I just meant that someone making a claim shouldn't expect me to believe it unless they've given an argument for it.

Mike Shulman (Apr 27 2023 at 04:47):

I'm not saying I don't understand your proof; I'm saying you didn't even give a proof.

dusko (Apr 27 2023 at 05:55):

Mike Shulman said:

I'm not saying I don't understand your proof; I'm saying you didn't even give a proof.

i didn't mean to give a proof. i didn't give a proof that i am not a chatbot either. i claimed that something was a factorization system. if you are interested in it, you check it. if you get stuck then i check it again. if you are not interested then why ask?

what we did prove together is that chatlists are for chatting :)

Morgan Rogers (he/him) (Apr 27 2023 at 07:14):

@dusko Regarding orthogonality, the functor from the walking arrow to the naturals (as a one-object category) picking out 1 is a counterexample, having both properties but not being an equivalence. It doesn't seem unfair to me to be disappointed that the few minutes of thinking I had to do to come up with that example was not done by you - I think this is what Mike was referring to regarding the "burden of proof".

Matteo Capucci (he/him) (Apr 27 2023 at 14:10):

Max New said:

Does anyone know a word for this concept in order theory? I have a monotone function $f : P \to Q$ and it is not just surjective but for any $q \leq q'$ in $Q$ there exists $p \leq p'$ in $P$ such that $f(p) = q$ and $f(p') = q'$. It's not the same as being a full functor because the $p$ depends on both $q$ and $q'$.

This smells like a a surjective-on-objects [[cofunctor]] :thinking:

dusko (Apr 27 2023 at 21:05):

Morgan Rogers (he/him) said:

dusko Regarding orthogonality, the functor from the walking arrow to the naturals (as a one-object category) picking out 1 is a counterexample, having both properties but not being an equivalence. It doesn't seem unfair to me to be disappointed that the few minutes of thinking I had to do to come up with that example was not done by you - I think this is what Mike was referring to regarding the "burden of proof".

i am not sure what you are saying. i will explain the factorization one more time, and then go back to work.

in general, any two factorization systems where epis of one are orthogonal to the monics of the other give a factorization on the arrow category. e.g., the factorization on the arrow category obtained from (Iso, All) and (All, Iso) is the free factorization. now note that a functor on an internal category is a pair of morphisms (the object part and the arrow part). they are more structured than the morphisms of arrow categories, but they can be factorized in a similar way, starting from two factorization systems, one for the object part, one for the arrow part.

this conversation started from a family of functors between posets (aka the monotone maps) where the arrow part is a surjection. if you take (All, Iso) on the object part, you get a factorization system on monotone maps. it lifts to a factorization system on functors in general if the "surjection" on the arrow part is saturated under compositions of arrows. it remains an epi in a similar way like dense maps are epis on spaces.

i don't know whether these things are useful for anything in sight, but they can be fun for puzzling. unfortunately, people sometimes take puzzling personally, like most other things they do. that leads to misunderstandings that are hard to dispel by typing on a keyboard, and it sucks them in. we should really try to not get sucked in and take math personally.

Amar Hadzihasanovic (Apr 28 2023 at 05:01):

@dusko if I understand your argument, you are saying that

• there is an OFS on graphs given by (surjective on edges, injective on edges and bijective on vertices), and induced by the pair of OFSs on Set (surjective, injective) and (all, iso) by applying them to the edge and vertex part separately

• to get an OFS (in the appropriate 2-categorical sense) on categories, we can relax the two sides by taking "surjective after saturation with composites" instead of surjective on the arrow side, and e.g. "essential surjectiveness" instead of "surjective" on the object side...

But still I don't see how the class "injective on edges and bijective on objects" should become "faithful and ess. surjective", as that doesn't "categorify" the "injective on objects" part; and indeed @Morgan Rogers (he/him) has a counterexample where you don't have injectiveness on objects, not even in a weak sense.

Perhaps taking pseudomonic (faithful + full on isomorphisms) & essentially surjective functors works as a right class?

Morgan Rogers (he/him) (Apr 28 2023 at 07:42):

That seems like it would have been a good answer for when Mike said he didn't "see why that would be the case"!

The problem with the argument is that the intermediate arrow in the factorization need not be a category, and freely turning it into one (saturating under composition) breaks the orthogonality. Which is a shame, to be honest - composition breaks so many nice properties that epimorphisms can otherwise have!

Morgan Rogers (he/him) (Apr 28 2023 at 07:45):

(My last message seems to have only sent this morning rather than last night due to connection problems)

dusko (Jul 02 2023 at 10:47):

Amar Hadzihasanovic said:

dusko if I understand your argument, you are saying that

• there is an OFS on graphs given by (surjective on edges, injective on edges and bijective on vertices), and induced by the pair of OFSs on Set (surjective, injective) and (all, iso) by applying them to the edge and vertex part separately

• to get an OFS (in the appropriate 2-categorical sense) on categories, we can relax the two sides by taking "surjective after saturation with composites" instead of surjective on the arrow side, and e.g. "essential surjectiveness" instead of "surjective" on the object side...

But still I don't see how the class "injective on edges and bijective on objects" should become "faithful and ess. surjective", as that doesn't "categorify" the "injective on objects" part; and indeed Morgan Rogers (he/him) has a counterexample where you don't have injectiveness on objects, not even in a weak sense.

Perhaps taking pseudomonic (faithful + full on isomorphisms) & essentially surjective functors works as a right class?

Amar Hadzihasanovic (sorry that i am responding after like 100 days. everything was happening at the same time in the meantime...)

in general, if we have factorization systems $(E_1,M_1)$ and $(E_2,M_2)$ where $E_1 \bot M_2$ in a category $\cal C$ then we have a factorization system in the arrow category $\cal C/C$, where we factorize the domain map by the first factorization system and the codomain map by the second. now look at the functors between internal categories in $\cal C$. they are also some commutative squares, plus the closure property induced by the functoriality of the arrow part. so any pair of factorization systems as above will induce a factorization of functors, where the epi component of the arrow part is just dense, and needs to be saturated under composition.

i am not sure whether i my memory of the original factorization is still valid (and would have to stare at it now because it is late) --- but i think the factorization that i was talking about could be obtained by instantiating the above general story to $(Iso,All)$ and $(Sur,Inj)$.