Meta-ticket: ForgetfulFunctor not working properly

[mjungmath]

We have currently the following bug:

sage: from sage.categories.functor import ForgetfulFunctor
sage: F = ForgetfulFunctor(Rings(), Sets())
sage: F(ZZ)
Integer Ring

The result should rather be:

sage: Set(ZZ)
Set of elements of Integer Ring

so that:

• F(ZZ).category() gives InfiniteEnumeratedSets()
• ... and thus Hom(F(ZZ), ...) will construct morphisms in the correct category
• it uses equality as sets, not as rings

Tickets:

• 34384 Proper ForgetfulFunctor with codomain=Sets() or its full subcategories

• 34390 ForgetfulFunctor: Register coercions

• 34402 Proper ForgetfulFunctor with codomain=Modules(ZZ) via AdditiveAbelianGroupWrapper

• 31241 Forgetful Functors for Manifold Objects

CC: @tscrim @mkoeppe @tobiasdiez @nthiery @simon-king-jena @hivert

Component: categories

Issue created by migration from https://trac.sagemath.org/ticket/31247

[mkoeppe]

comment:55

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

You are implicitly changing the requirements (and hence, the definition) by calling something a bug that IMSO should not be (nor has it previously been considered to be AFAIK).

Read https://github.com/sagemath/sage-prod/blob/develop/src/sage/categories/sets_cat.py#L254

This is not evidence of anything about a general bug for ForgetfulFunctor. That is about this category's implementation of __call__, which is what ForgetfulFunctor does. If F: C -> D, then F(X) is performs D(x). It is up to each category to impose how it wants to perform its __call__, which is an implementation detail.

The comment explains that a category does not have this choice because the coercion system dictates that __call__ passes through its input if it is already in the category.

[tscrim]

comment:56

Replying to @mkoeppe:

Replying to @tscrim:

If I have a new ring structure on Z, lets call it TT, then ZZ == TT would be False. Now if we apply the forgetful functor to them, they would still be false. I am saying this is fine and proper because they are different representations of the same set

I wouldn't say that it's fine and proper; I'd say there is an implementation restriction that stops us from detecting that they are equal. Sage is of course full of such implementation restrictions.

Then the fact that two "equal" things are not equal is not a bug. Hence, the fact that forgetful functor does not necessarily return a new object, which could lead to a different == implementation, is not a bug.

A proper implementation of the forgetful functor will improve this situation: It removes the implementation restriction.

No it does not. If you want == as instances of Set, you should explicitly make your objects instances of Set. It doesn't matter what the category an object belongs to. The implementation is what carries the meaning of ==. Let the category decide what it wants to do with __call__. That is what the forgetful functor does.

[tscrim]

comment:57

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

You are implicitly changing the requirements (and hence, the definition) by calling something a bug that IMSO should not be (nor has it previously been considered to be AFAIK).

Read https://github.com/sagemath/sage-prod/blob/develop/src/sage/categories/sets_cat.py#L254

This is not evidence of anything about a general bug for ForgetfulFunctor. That is about this category's implementation of __call__, which is what ForgetfulFunctor does. If F: C -> D, then F(X) is performs D(x). It is up to each category to impose how it wants to perform its __call__, which is an implementation detail.

The comment explains that a category does not have this choice because the coercion system dictates that __call__ passes through its input if it is already in the category.

Coercion is not involved:

    Category.__call__(self, x, *args, **opts):
        if x in self:
            return x
        return self._call_(x, *args, **opts)

[mkoeppe]

comment:58

Replying to @tscrim:

The comment explains that a category does not have this choice because the coercion system dictates that __call__ passes through its input if it is already in the category.

Coercion is not involved:

    Category.__call__(self, x, *args, **opts):
        if x in self:
            return x
        return self._call_(x, *args, **opts)

The comment is saying that the __call__ method of a category cannot implement the forgetful behavior. Because that would violate the guarantees of the coercion system.

[tscrim]

comment:59

Replying to @mkoeppe:

Replying to @tscrim:

The comment explains that a category does not have this choice because the coercion system dictates that __call__ passes through its input if it is already in the category.

Coercion is not involved:

    Category.__call__(self, x, *args, **opts):
        if x in self:
            return x
        return self._call_(x, *args, **opts)

The comment is saying that the __call__ method of a category cannot implement the forgetful behavior. Because that would violate the guarantees of the coercion system.

The coercion system is not mentioned in the note or in any of the relevant code.

The documentation of Category__call__ even specifies:

        If ``x`` is readily in ``self`` it is returned unchanged.
        Categories wishing to extend this minimal behavior should
        implement :meth:`._call_`.

This is further direct documentation evidence that even categories do not want to change objects of subcategories. This is not a bug.

[mkoeppe]

comment:60

Note it says _call_, not __call__. Categories cannot override the if x in self: return x.

[mkoeppe]

comment:61

Replying to @tscrim:

The comment is saying that the __call__ method of a category cannot implement the forgetful behavior. Because that would violate the guarantees of the coercion system.

The coercion system is not mentioned in the note or in any of the relevant code.

Well, __call__ is in charge of implementing coercion, so it is subject to the guarantees of the coercion system.

[tscrim]

comment:62

Replying to @mkoeppe:

Note it says _call_, not __call__. Categories cannot override the if x in self: return x.

Right, that is my point. The ForgetfulFunctor goes through that for objects. This was clearly the intended behaviour.

[tscrim]

comment:63

Replying to @mkoeppe:

Replying to @tscrim:

The comment is saying that the __call__ method of a category cannot implement the forgetful behavior. Because that would violate the guarantees of the coercion system.

The coercion system is not mentioned in the note or in any of the relevant code.

Well, __call__ is in charge of implementing coercion, so it is subject to the guarantees of the coercion system.

This makes no sense to me. The coercion system, which only operates on elements, makes no requirements on the syntax nor semantics of __call__, much less for things that are not parents (as a way of creating elements).

[mkoeppe]

comment:64

Replying to @tscrim:

Replying to @mkoeppe:

Note it says _call_, not __call__. Categories cannot override the if x in self: return x.

Right, that is my point. The ForgetfulFunctor goes through that for objects. This was clearly the intended behaviour.

No, the ForgetfulFunctor is just not fully implemented.

It does not even have its own _apply_functor method, it is just taking the one from Functor.

And this code is from 2010, whereas the comment in sets_cat.py regarding the lack of "proper forgetful functors" is from 2015.

[mkoeppe]

comment:65

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

The comment is saying that the __call__ method of a category cannot implement the forgetful behavior. Because that would violate the guarantees of the coercion system.

The coercion system is not mentioned in the note or in any of the relevant code.

Well, __call__ is in charge of implementing coercion, so it is subject to the guarantees of the coercion system.

This makes no sense to me. The coercion system, which only operates on elements [...]

To me the "coercion system" includes the functorial constructions for parents etc. It won't be useful to discuss this terminology.

[mkoeppe]

comment:66

Replying to @mkoeppe:

And this code is from 2010, whereas the comment in sets_cat.py regarding the lack of "proper forgetful functors" is from 2015.

I have to take this back, this was very superficial archeology

[mkoeppe]

comment:67

The relevant commit is

commit 2187d6d8a9ab3ef08a83225c24107055ba3d43a4
Author: Florent Hivert <Florent.Hivert@univ-rouen.fr>
Date:   Sat Nov 27 19:39:43 2010 +0100

    #8925: add __call__ to categories Sets() and EnumeratedSets().

[mkoeppe]

comment:68

The ForgetfulFunctor predates that. It is from

commit d43bc53b7e73b54600ed8df563849dc7817d5d41
Author: Simon King <simon.king@nuigalway.ie>
Date:   Fri Apr 30 14:56:16 2010 +0100

    #8807: Implement induced ring homomorphisms. Extend the functor framework, so that functors can be applied to morphisms.

and earlier.

[tscrim]

comment:69

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

The comment is saying that the __call__ method of a category cannot implement the forgetful behavior. Because that would violate the guarantees of the coercion system.

The coercion system is not mentioned in the note or in any of the relevant code.

Well, __call__ is in charge of implementing coercion, so it is subject to the guarantees of the coercion system.

This makes no sense to me. The coercion system, which only operates on elements [...]

To me the "coercion system" includes the functorial constructions for parents etc. It won't be useful to discuss this terminology.

The term "coercion system" has a clear set meaning within Sage. I agree the terminology you use is not important, but it will cause confusion if it conflicts with something else.

That being said, I don't think there are any set rules like the ones you are trying to invoke. All that is required is the output of any functor is some object that is in the category. Just like applying a morphism only requires that the result is an element the parent codomain, not that it needs to have a specific implementation. Sometimes this can cause some headaches, but those are the things the user needs to be wary of.

[mkoeppe]

comment:70

Replying to @tscrim:

I don't think there are any set rules like the ones you are trying to invoke.

Can you clarify - you are disagreeing with the comment in sets_cat.py from Florent's commit? For reference again:

       Using `Sets()(A)` used to implement some sort of forgetful functor
       into the `Sets()` category. This feature has been removed, because
       it was not consistent with the semantic of `Category.__call__`.
       Proper forgetful functors will eventually be implemented, with
       another syntax.

[mkoeppe]

comment:71

And Category.__call__ is unambiguous:

    If `x` is readily in `self` it is returned unchanged.
    Categories wishing to extend this minimal behavior should
    implement `_call_`.

"extending" this minimal behavior means to do more things when x is not in self. (Category._call_ just raises NotImplementedError.)

[tscrim]

comment:72

Replying to @mkoeppe:

Replying to @tscrim:

I don't think there are any set rules like the ones you are trying to invoke.

Can you clarify - you are disagreeing with the comment in sets_cat.py from Florent's commit?

I don't know of any consistency rule you want with the result of ForgetfulFunctor. As far as I know, we don't have any requirements other than F(X) in Sets() returns True, where the codomain of the (forgetful) functor F is Sets().

I agree fully with the first part; it was inconsistent. I don't know what Florent was intending by the word "proper" for the latter part; in particular the semantics on the result. However, I am very wary of changing current allowed behaviors (and definitions) in ways that says we should try to solve impossible problems with huge maintenance burdens in our code base.

[mkoeppe]

comment:73

Replying to @tscrim:

try to solve impossible problems with huge maintenance burdens in our code base.

I have disputed this.

[mkoeppe]

comment:74

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

I don't think there are any set rules like the ones you are trying to invoke.

Can you clarify - you are disagreeing with the comment in sets_cat.py from Florent's commit?

I don't know of any consistency rule you want with the result of ForgetfulFunctor. As far as I know, we don't have any requirements other than F(X) in Sets() returns True

But Category.__call__ (comment:71) explicitly indicates the behavior when X is already in Sets(). That's the other requirement.

[mkoeppe]

comment:75

Replying to @tscrim:

I don't know what Florent was intending by the word "proper" for the latter part

You know, a functor that actually forgets something.

[tscrim]

comment:76

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

I don't think there are any set rules like the ones you are trying to invoke.

Can you clarify - you are disagreeing with the comment in sets_cat.py from Florent's commit?

I don't know of any consistency rule you want with the result of ForgetfulFunctor. As far as I know, we don't have any requirements other than F(X) in Sets() returns True

But Category.__call__ (comment:71) explicitly indicates the behavior when X is already in Sets(). That's the other requirement.

Not for the image of functors; that is only the Category.__call__. For the implementation of ForgetfulFunctor, it was chosen to just do the result of Category.__call__. In fact, the NOTE: in Functor._apply_functor indicates that subclasses are allowed to change the default behavior to suit their needs.

[mkoeppe]

comment:77

Replying to @tscrim:

I don't know of any consistency rule you want with the result of ForgetfulFunctor. As far as I know, we don't have any requirements other than F(X) in Sets() returns True

But Category.__call__ (comment:71) explicitly indicates the behavior when X is already in Sets(). That's the other requirement.

Not for the image of functors; that is only the Category.__call__.

Sorry, I misread what you wrote

[mkoeppe]

comment:78

Replying to @tscrim:

I don't know of any consistency rule you want with the result of ForgetfulFunctor.

I thought I explained it. Because our parents are equipped with a distinguished category (i.e., mathematically they are pair of: (1) an object in the category of objects and (2) a category in the category of categories)), when we apply the ForgetfulFunctor, we need to return a new parent with a new distinguished category (i.e., mathematically, a pair of (1) new object, (2) new category).

Now an actually interesting question is what exactly the new distinguished category should be. It could be just the codomain of the functor, so for ForgetfulFunctor(..., Sets()) it would be Sets(). However, another choice would be a suitable full subcategory of the codomain. This is what I have implemented in #34384.

[mkoeppe]

comment:80

it's time for another time zone to chime in

[simon-king-jena]

comment:81

I didn't have time to carefully read the whole discussion, yet. But concerning the discussion about "equality", here are 2 cents:

2==4/2 is true, when ZZ and QQ are considered as rings, because there is a coercion from ZZ to QQ that is a morphism in the category of rings. IMHO, it makes sense to request that applying the forgetful functor to a coercion morphism (in a smaller category) yields a coercion morphism (in a larger category). Hence, 2==4/2 should be true also in the category of sets (the usual coercion morphism of rings would be applied as a coercion morphism of sets).

The opposite problem is more tricky. I have no concise example, but I could imagine that there are two rings (R,+,*) and (S,+,*) such that there is a meaningful coercion map between abelian groups (R,+) and (S,+) that is not a ring morphism. Hence, if F is the forgetful functor from Rings() to AbelianGroups(), it may very well be possible that there is a in R and b in S such that F(R)(a) == F(S)(b) should evaluate as true (because a,b can be coerced as elements of abelian groups), but a == b should evaluate as false (because there is no coercion of rings).

And that would indeed be difficult to implement.

[mkoeppe]

comment:82

Replying to @simon-king-jena:

2==4/2 is true, when ZZ and QQ are considered as rings, because there is a coercion from ZZ to QQ that is a morphism in the category of rings. IMHO, it makes sense to request that applying the forgetful functor to a coercion morphism (in a smaller category) yields a coercion morphism (in a larger category).

I agree. I've opened #34390 for this

[mkoeppe]

Description changed:

--- 
+++ 
@@ -21,4 +21,6 @@

 Tickets: 
 - #34384 Proper `ForgetfulFunctor` with `codomain=Sets()` or its full subcategories
+- #34390 `ForgetfulFunctor`: Register coercions
 - #31241 Forgetful Functors for Manifold Objects
+

[tscrim]

comment:84

Replying to @simon-king-jena:

I didn't have time to carefully read the whole discussion, yet. But concerning the discussion about "equality", here are 2 cents:

2==4/2 is true, when ZZ and QQ are considered as rings, because there is a coercion from ZZ to QQ that is a morphism in the category of rings.

Of course it is true, but it is about do we require that it must be true for any different representations of the same element in some parent. This is just a very simple example where there can be multiple different ways of writing the same element. In this case, we know what a canonical representation is for fractions. However, this is not true for all objects (e.g., finitely presented groups).

IMHO, it makes sense to request that applying the forgetful functor to a coercion morphism (in a smaller category) yields a coercion morphism (in a larger category). Hence, 2==4/2 should be true also in the category of sets (the usual coercion morphism of rings would be applied as a coercion morphism of sets).

How would you deal with sets that are equal but with different implementations that do not have a conversion (much less a coercion) between them? Following your premise, this would be a bug, which would need to be fixed. To make this even more difficult, you would not want a coercion because the parents have fundamentally different structures. How do we fix this?

What about more abstract parents? Should all three dimensional free modules over a field k be equal since they all could be considered as k³ (in particular, by the method to_vector() in ModulesWithBasis())? How do we even want to decide?

The opposite problem is more tricky. I have no concise example, but I could imagine that there are two rings (R,+,*) and (S,+,*) such that there is a meaningful coercion map between abelian groups (R,+) and (S,+) that is not a ring morphism. Hence, if F is the forgetful functor from Rings() to AbelianGroups(), it may very well be possible that there is a in R and b in S such that F(R)(a) == F(S)(b) should evaluate as true (because a,b can be coerced as elements of abelian groups), but a == b should evaluate as false (because there is no coercion of rings).

And that would indeed be difficult to implement.

I would say nearly impossible resulting in any ticket with a new feature would basically be introducing bugs. This is making the specification of == way too strict.

[tscrim]

comment:85

Replying to @mkoeppe:

Replying to @tscrim:

I don't know of any consistency rule you want with the result of ForgetfulFunctor.

I thought I explained it. Because our parents are equipped with a distinguished category (i.e., mathematically they are pair of: (1) an object in the category of objects and (2) a category in the category of categories)), when we apply the ForgetfulFunctor, we need to return a new parent with a new distinguished category (i.e., mathematically, a pair of (1) new object, (2) new category).

You need to pick your definition of "distinguished" as you are going between "this is an object in this category" and "this category is just considered special to this object" when it suits you. If the category is just special, then no new object needs to be returned because it still is an object in that category.

Now an actually interesting question is what exactly the new distinguished category should be. It could be just the codomain of the functor, so for ForgetfulFunctor(..., Sets()) it would be Sets(). However, another choice would be a suitable full subcategory of the codomain. This is what I have implemented in #34384.

If we do this (which I continue to remain staunchy opposed to), it must be in the codomain C, e.g., Sets, not some full subcategory C'. Otherwise, strictly speaking, you could not build a natural homset to some other object in C \ C'.

[tscrim]

comment:86

Replying to @mkoeppe:

Replying to @tscrim:

I don't know what Florent was intending by the word "proper" for the latter part

You know, a functor that actually forgets something.

Yes, that is what it should do on the morphisms. That is the only bug. Not on the objects.

[tscrim]

comment:87

Replying to @mkoeppe:

Replying to @tscrim:

try to solve impossible problems with huge maintenance burdens in our code base.

I have disputed this.

No, you haven't. You haven't explained why we don't have to implement a new object for every image of every forgetful functor. Or why we don't have to deal with comparisons of elements in each of these new parents. Or why we don't have to make sure that every functor also always returns an object with a distinguished category of the codomain. Or how you will deal with these backwards incompatible changes.

[mkoeppe]

comment:88

Sorry, Travis, "you have to implement everything or you are not allowed to implement anything" is a pretty absurd take.

[mkoeppe]

comment:89

Replying to @tscrim:

Or how you will deal with these backwards incompatible changes.

See comment:67, comment:68. ForgetfulFunctor was broken in 2010, it has not been forgetting anything since. So I don't think there is a need to worry about scary backwards incompatible changes.

[tscrim]

comment:90

I am explaining the maintenance burden you are placing on us by making this change of specification. It's like saying "I don't like how these cars look, so I am going to completely rewrite the traffic laws but not tell you how to comply with them."

[mkoeppe]

comment:91

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

I don't know of any consistency rule you want with the result of ForgetfulFunctor.

I thought I explained it. Because our parents are equipped with a distinguished category (i.e., mathematically they are pair of: (1) an object in the category of objects and (2) a category in the category of categories)), when we apply the ForgetfulFunctor, we need to return a new parent with a new distinguished category (i.e., mathematically, a pair of (1) new object, (2) new category).

You need to pick your definition of "distinguished" as you are going between "this is an object in this category" and "this category is just considered special to this object" when it suits you.

No, Travis, I have been using my terminology consistently. The distinguished category is the one that .category() returns.

[tscrim]

comment:92

Replying to @mkoeppe:

Replying to @tscrim:

Or how you will deal with these backwards incompatible changes.

See comment:67, comment:68. ForgetfulFunctor was broken in 2010, it has not been forgetting anything since. So I don't think there is a need to worry about scary backwards incompatible changes.

But they are not broken when acting on objects. You want to change the specifications to make it into a bug.

[mkoeppe]

comment:93

Our Parents (or any CategoryObjects are not just "objects in a category". They are mathematically a pair (object, category). Otherwise, the method category() could not exist.

[tscrim]

comment:94

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

I don't know of any consistency rule you want with the result of ForgetfulFunctor.

I thought I explained it. Because our parents are equipped with a distinguished category (i.e., mathematically they are pair of: (1) an object in the category of objects and (2) a category in the category of categories)), when we apply the ForgetfulFunctor, we need to return a new parent with a new distinguished category (i.e., mathematically, a pair of (1) new object, (2) new category).

You need to pick your definition of "distinguished" as you are going between "this is an object in this category" and "this category is just considered special to this object" when it suits you.

No, Travis, I have been using my terminology consistently. The distinguished category is the one that .category() returns.

If it is just some category that has special meaning for the defaults for some inputs, then there is no bug here with ForgetfulFunctor(ZZ, codomain=Sets()) returning ZZ. You don't have to remember about the structure that puts it into Rings(). Everything that depends on the category of the object, such as Hom has an input for the user to set the category.

[tscrim]

comment:95

Replying to @mkoeppe:

Our Parents (or any CategoryObjects are not just "objects in a category". They are mathematically a pair (object, category). Otherwise, the method category() could not exist.

Then should every getter method be part of the mathematical definition of the parent? Or every attribute? What makes the category one so special that we need some broad universal rule?

Basically, this leads us right into the absurd. A parent is not modeling this pair.

[mkoeppe]

comment:96

Replying to @tscrim:

Replying to @mkoeppe:

Our Parents (or any CategoryObjects are not just "objects in a category". They are mathematically a pair (object, category). Otherwise, the method category() could not exist.

A parent is not modeling this pair.

What do you mean by that?

[tscrim]

comment:97

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Our Parents (or any CategoryObjects are not just "objects in a category". They are mathematically a pair (object, category). Otherwise, the method category() could not exist.

A parent is not modeling this pair.

What do you mean by that?

A parent is just modeling the set of elements. Nothing more, nothing less. It has some things associated to it, such as having a distinguished category, that tells you things you can do on it. However, it is just meant to be the set.

[mkoeppe]

comment:98

How do you "associate" something with a mathematical set?

[tscrim]

comment:99

Mathematically, you make a new object as a tuple. However, we are not manipulating such objects. Programmatically, we have attributes that allow us to identify together, e.g., Z, (Z, +), (Z, +, *), (Z, +, AdditiveAbelianGroups()), (Z, Q via fraction_field()), etc. to deal with the ambiguity we very often use because context (and "trivialities" or "well-known facts/identifications") makes it clear.

[mkoeppe]

comment:100

So the Parent resolves this ambiguity by storing these "attributes" (including the distinguished category), right?

[tscrim]

comment:101

Yes, that is how I see it.

[mkoeppe]

comment:102

So now a ForgetfulFunctor is sneaking around the corner and applies itself to the Parent. Do I understand right that you are saying that not only it needs to return the same object, but also that object needs to be equipped with the same unchanged "attributes"?

[tscrim]

comment:103

It doesn't have to return the same object, but it can. This is why I have no problem with the change in #34384, but I object to calling it a bug that it does not do it.

[mkoeppe]

comment:104

By object, you now mean Parent, right? That is object "associated" with extra attributes, yes?

[tscrim]

comment:105

Yes, that is correct.