Noetherian information systems

These are notes for a colloquium talk to be given at NITheCS.

The Snake Lemma from this fragment of a 1980 film ("It's My Turn", starring Jill Clayburgh and Michael Douglas), along with many other similar theorems in abstract algebra, known to be true for a variety different algebraic settings, can all be established in a unified setting of noetherian forms. This post attempts to give a preliminary step towards a possibly ambitious goal of applying noetherian forms outside abstract mathematics. In this light we propose a variation of this notion, a "noetherian information system", which is intended to be more agile in terms of identifying applications.

General Information Systems

By a network we mean a web of devices and directed binary channels between them ( = a graph in the sense of category theory). An information system over a network consisting of just one device and no channels, is a collection of information clusters, where some clusters may be parts of others.

The picture above describes an example of an information system. The device is a cellphone. A cluster is an approximate GPS location of the cellphone. Six clusters are displayed above, marked by A, B, C, D, E, F. The blue clusters represent GPS locations measured at different times on a given day. The orange ones represent GPS locations measured on another day. In general, the idea is that information clusters in an information system are all possible data that the device is theoretically able to capture/process.

There are two ways to interpret the meaning for a cluster E to be part of a cluster C:

• If we think of E as the range of possible locations of the cellphone, then E gives more information about the location of the cellphone than C does. We call this the classical interpretation. In this interpretation, E being part of C gets interpreted as E "implying" C in the sense of classical mathematical logic.
• If we think of each possible location as an attribute of the cellphone, then we can interpret E to be a state of the cellphone in which the cellphone has less attributes than in the state C. We call this the quantum interpretation, since with this interpretation, the information cluster E is seen as a state where the cellphone is simultaneously in all locations within the region E.

The general notion of an information cluster is an abstract one, as is the notion of one cluster being part of another. We only require that "is part of" relation between clusters is reflexive, antisymmetric and transitive.

A transmission from one information system to another maps each cluster in one system to a cluster in another system, so that if among two clusters, one is part of another, then a similar relation will hold for the mapped clusters (this property is called monotonicity of transmission). An example of transmission is calculation of distance range to a pinned location, based on the approximate GPS location of the cellphone.

Here the source of transmission is the information system described earlier. The target is an information system where clusters are closed intervals of positive real numbers. The diagram above shows that the cluster C in the first information system will get mapped to the cluster [s,l] in the second information system (where s and l represent lengths of the displayed vectors). In this diagram, L is the pinned location. Monotonicity of this transmission follows from elementary geometry.

In the example above, note that while D is not part of C, it gets mapped to a part of where C maps to. So, in general, transmission does not reflect the "part of" relation between clusters (while it preserves it, by monotonicity). 

An information system over a general network consists of information systems over individual devices of the network, where each channel f from a device A to a device B determines a transmission of information from the information system over A to the information system over B. Note that a single transmission itself can be seen as an information system, where the network consists of two devices and one channel between them. 

In an information system, given a finite chain of channels

connecting a device U with a device Y, we can consider a transmission from the information system of U to an information system of Y, by composing the transmissions along the chain of channels. We call such transmissions the composite transmissions. This includes the case of an empty chain, i.e., when a chain consists of just one device U and no channels. The resulting composite transmission is then the identity map: it maps every cluster of U to itself. This way, we get a category out of an information system, where objects are devices of the information system and morphisms are composite transmissions. We call it the transmission category. Composition of morphisms in this category is given by further composing composite transmissions. The starting information system then gives rise to a "form" over this category, but we will not go in detail there. Let us just remark that a transmission category can be seen as a subcategory of the category of partially ordered sets. Isomorphisms in the transmission category will be called isotransmissions. These are composite transmissions which admit a two-sided inverse composite transmission. 

Henceforth, we we speak of a "transmission" we refer to a "composite transmission", i.e., a morphism in the transmission category.

Inputs and Outputs

Define a stash of a transmission to be any cluster that maps to the smallest cluster in the target of the transmission (provided such exists), and define a reach to be any cluster such that there is a cluster in the source mapping to it. 

In quantum interpretation, the smallest cluster (when it exists) is given by the least possible attribute set (it must be part of any cluster). Then a stash can be seen as a piece of information that gets concealed (as much as possible) in a transmission. If the smallest cluster is the empty set of attributes, then a stash is a piece of information that does not get transmitted at all. 

In classical interpretation, the smallest cluster is a piece of information that logically implies any other piece of information: so it is the logical contradiction (the falsity). In this interpretation, a stash is a piece of information whose transmission results in contradiction. So once again, we may think of this as information that will not get transmitted. 

In both classical and quantum interpretations, reach is a piece of received information.

An input is a channel that has the following properties:

• Any transmission with the same target as that of the input, whose every reach is a reach of the input, arises as a composite of the input transmission with a transmission to the source of the input. 
• The input transmission maps clusters injectively (i.e., different clusters do not transmit to the same cluster).
• Any cluster that is part of a reach of the input transmission is itself a reach of the input transmission.

An output is a channel that has the following property:

• Any transmission with the same source as the output, whose every non-stash is a non-stash of the output, arises as a composite of the output with a transmission from the target of the output.
• If the output transmission maps a cluster B to part of a clusters A, and all stashes are part of A, then B is part of A as well.
• Any cluster in the target of the output is a reach of the output transmission.

An information system is said to be prenoetherian when the following three conditions hold:

• Any transmission decomposes as an output transmission followed by an isotransmission and followed by an input transmission. 
• For any two inputs there is a third input whose reaches are precisely those clusters which are reaches of both initial inputs.
• For any two outputs there is a third output whose stashes are precisely those clusters which are parts of every single cluster containing all stashes of both initial outputs.

Intuitively, the first of these conditions states that any transmission can be replicated through a dedicated transmission and receiving subdevices, between which information transmits without distortion. The second condition assures existence of a receiving subdevice that can capture the same information that two given receiving subdevices both did. The third condition assures existence of a transmission subdevice that can conceal all that the two given transmission subdevices were able to conceal.

Mathematical Examples

Consider vector spaces as devices. Define a channel from a vector space V to a vector space W to be a linear map from V to W. Declare an information cluster to be a subspace of a vector space and declare one cluster to be part of another when the first subspace lies inside the second one. Transmission of subspaces is given by direct image of a subspace under a linear map. The corresponding category of transmissions is equivalent to the category of projective spaces (the quotient of the category of vector spaces, which identifies two linear maps when they act the same way on subspaces). This information system is prenoetherian thanks to the fact that the category of vector spaces is an abelian category. The required decomposition of a transmission is given by decomposition of a linear map as a quotient map, followed by an isomorphism and followed by subspace inclusion. The isomorphism in this decomposition is guaranteed by Noether's First Isomorphism Theorem.

Vector spaces here can be replaced by many other group-like structures. More generally, semi-abelian categories give rise to a prenoetherian information systems similarly to how abelian categories do -- once again, relying on Noether's First Isomorphism Theorem, as well as a few other important "exactness properties".

It has been recently shown that we can even consider a prenoetherian information system where the transmission category is equivalent to the category of sets. Devices in this example are sets. Channels are functions between sets. An information cluster partitions the set into equivalence classes and either distinguishes one of the classes or not. One cluster is part of another, if each equivalence class in the first is a subset of an equivalence class in the second and the distinguished equivalence class (if there is one) in the first cluster is a subset of the distinguished one in the second cluster.

A channel transmission then acts as suggested in the following example.

Distinguished equivalence classes must map to distinguished classes: so if blue is the distinguished class in the source, then in the target, blue must be the distinguished one as well. If, on the other hand, no class is distinguished in the source cluster, then the target cluster will not have a distinguished class either. The required decomposition of functions here is given again by Noether's First Isomorphism Theorem: any function decomposes as a quotient map, followed by a bijection, and followed by a subset inclusion map.

In these examples, every composite transmission is a channel transmission (which is because in each case our starting network was already a category, and transmissions were chosen functorially). When this happens, the decomposition required can by simplified to a decomposition into an output following by an input. This is thanks to the fact that inputs and outputs are stable under composition with channel isotransmissions.

In order to be able to recover all Noether isomorphism theorems in the transmission category of a prenoetherian information system (as well as many other homorphism theorems, such as homological diagram lemmas of homological algebra, for instance), we need to assume that the clusters admit finite suprema and finite infima (i.e., that information systems above each device are lattices in the sense of order theory) and that each transmission is a left adjoint in a Galois connection -- we call such information system a noetherian information system. We consider below a special case of this scenario, where clusters have arbitrary suprema and transmissions preserve them (these correspond to topological functors, whose applications in general topology have been a center of attention for many years in the research group of Professor Guillaume Brümmer from the University of Cape Town).

Topological Information Systems

An information system over a network consisting of just one device and no channels is complete when any number of clusters can be, in the terminology suggested by the quantum interpretation, superposed to form a new cluster. What we mean by "superposition" is nothing other than "join" in the terminology of order theory (so, "disjunction" in the classical interpretation). Superposition of no clusters should also be possible. In this case, the result is the smallest cluster. 

None of the information systems considered in the first section of this post are topological. 

• The first information system is not topological since clusters there are always circular regions of a plane. It is impossible to superpose two circular regions into another circular region. Note that a superposition of a set S of clusters is formally defined as a cluster J such that every member of S is part of J and moreover, J is part of any other cluster K that has the same property (i.e., that every member of S is part of K). So superposition of two disks should be a disk which contains both, but which is contained in any other disk containing both. Such disk does not exist unless one of the two disks contains the other: on the illustration below, an attempt to superpose two blue disks must produce a disk that wholly lies both in the yellow disk and the red disk, i.e., that lies in the orange region, while at the same time contains both blue disks -- this is not possible.

• Although non-zero finitely many closed intervals can be superposed, infinitely many, in general, cannot be superposed.

• In both cases, empty superposition is not possible.

A transmission is said to be continuous when transmission of information preserves superposition of clusters. In particular, when:

• the smallest cluster is transmitted to the smallest cluster, and
• superposing clusters in the source information system and then transmitting the resulting cluster, is the same as first transmitting the initial clusters and then superposing them in the target information system.

A general information system is topological when all information systems over individual devices are complete and all transmissions are continuous.

It is not difficult to amend our example(s) considered in the first section of this post to get topological information systems. For approximate GPS locations, we can allow any planar region to be a cluster and not just a circular one. For distance ranges, we could allow any set of numbers to be a cluster. The transmission of measuring distance ranges from a pinned location will then be continuous too for general mathematical reasons.

In a topological information system, every transmission can be reversed: the reverse of a transmission f is given by mapping a cluster D in the target of f to the superposition of all clusters that by f are mapped to parts of D. Writing f S for the result of mapping S by f, and writing Df for the result of mapping D by the referse of f, we get the following impressive law:

The middle symbol here is the symbol for logical equivalence. The inequality expresses that the cluster on its right side is part of the cluster on its left side. This is the familiar law of Galois connection in mathematics (written out in a slightly untraditional manner). Intuitively, the reverse transmission recovers largest possible cluster that can get transmitted into a given one.

In our example, reverse transmission of a distance range will result in the following region, which is the region of all locations that are in that distance range from the given location.

The seemingly simple law above has a number of useful mathematical consequences. We describe some of these below:

• Reverse transmission is monotone and it preserves meets of clusters (a meet of a set of clusters is defined as the largest cluster that is part of each cluster).
• Transmission followed by reverse transmission results in expansion of the cluster.
• Reverse transmission followed by transmission results in shrinking of the cluster.
• Transmission, then reverse transmission, and then transmission again, results in the same cluster as by initial transmission. There is a similar property starting with reverse transmission in the place of transmission.

Concluding Remarks

The notion of a noetherian information system from this post is an adaptation of the notion of a noetherian form from 

A. Goswami and Z. Janelidze, Duality in non-abelian algebra IV. Duality for groups and a universal isomorphism theorem, Advances in Mathematics 349, 2019, 781–812. 

Related references, and especially those which led to the development of this concept, can be found in the article above. In particular, it contains the following reference to the paper of Emmy Noether where her isomorphism theorems were first established:

E. Noether, Abstrakter Aufbau der Idealtheorie in algebraischen Zahl- und Funktionenkörpern, Mathematische Annalen 96 (1927), 26–61.

In the following paper, Saunders Mac Lane, suggested that there should be a unified categorical approached to isomorphism and other such theorems based on duality:

S. Mac Lane, Duality for groups, Bull. Am. Math. Soc. 56, 1950, 485–516.

Noetherian forms provide such approach. The example dealing with the category of sets can be generalized to any topos (joint work in progress with Francois van Niekerk). Keeping in mind that the notion of a topos is a notion of a mathematical universe, we see how noetherian information systems have a wide reach in abstract mathematics. This makes one wonder whether they can be found outside of mathematics as well? In particular:

• Is there a useful real-life interpretation of a noetherian information system?
• If yes, does it lead to the ability to usefully model real-life information systems as noetherian information systems? 
• In particular, are there any applications in machine learning or data science?
• Or, is it perhaps possible to use noetherian information systems to usefully model function of a living organism, or maybe, cognitive function of a human being?
• Does the category of Hilbert spaces, which is neither an abelian nor a semi-abelian category, but which plays an important role in quantum mechanics, have a noetherian form?
• Can the physical universe be modelled as a noetherian information system?

Read More

Noetherian Forms

Link to a plenary talk on noetherian forms at a BRICS conference (2021): slides of the talk, recording of the talk.

Link to a talk on noetherian forms at the PALS seminar (2020): written summary, recording of the talk.

Noetherian forms are mathematical structures defined by self-dual axioms, that include all lattices, Janelidze-Marki-Tholen semi-abelian categories and Grandis exact categories. They can be seen as a realization of Saunders Mac Lane's hypothesis from his 1950 paper on Duality for Groups that self-dual axioms can be found to treat isomorphism theorems for non-abelian groups, as this is realized for abelian groups with the notion of an abelian category. Abelian categories are actually given by the overlap of semi-abelian and exact categories.

The term "noetherian" refers to the fact that these forms can seen as a fulfilment of Emmy Noether's program to "disregard the elements and operations in algebraic structures in favor of selected subsets, linked to homomorphisms between structures by the homomorphism and isomorphism theorems" - quote from Colin Maclarty's article.

See this list for relevant papers in this research area.

Work in progress and current conjectures / open questions regarding noetherian forms:

• Noetherian forms found for the category of sets - a paper on this is in preparation. Conjecture: these forms are present already for an arbitrary topos.
• The category of Hilbert spaces and continuous linear maps is an additive category, but not an abelian category. Conjecture: it nevertheless admits a noetherian form. Question: if there is indeed such noetherian form, is it of any use for quantum mechanics / quantum field theory?

Read More

Forms vs monoidal categories

Below is a summary of the talk given at the Séminaire Itinérant de Catégories (8 October 2021), prepared before the talk. The talk is mainly based on Zurab Janelidze's joint work in progress with Francois van Niekerk, as well as his earlier work on forms with former collaborators.

The talk assumes that the listener is familiar with basic ideas and concepts of category theory found in Categories for the Working Mathematician by Saunders Mac Lane (in particular, Chapters I, VII and VIII), as well as with the notions of factorization system and Grothendieck fibration.

1. Biproducts, products, sums and monoidal categories

The goal of this talk is to explain the following diagram:

The notion of an abelian category brings together various important categories of abstract mathematics, such as the categories of modules, which includes the category of vector spaces as well as the category of abelian groups. In an abelian category, the monoidal structure of product and the monoidal structure of sum (coproduct) are isomorphic. Existence of such an isomorphism is in fact what defines a linear category (not difficult to prove). The notion of a biproduct formalizes matching of the notion of a product and the notion of a sum, at a local level. Recall that the biproduct of two objects "X" and "Y" in a category is given by a diagram

where the top line is a sum diagram, the bottom line is a product diagram, and the following equations hold:

The first two equations are well known. The third equation is due to Martti Karvonen, who wrote a paper about it for the Cahiers ("Biproducts without pointedness", 2020), explaining that this equation can replace the well known ones involving zero morphisms of a pointed category, to free the notion of a biproduct from the context of a pointed category. A linear category is a pointed category admitting a biproduct of any of its two objects. Abelian categories are a bit more than linear categories: for example, the category of commutative monoids is linear, but not abelian. Linearity is, however, an important conceptual ingredient of the notion of an abelian category. 

Most categories are not linear. Matching of products and sums is a rare phenomenon. So instead of their matching, one looks for a common generalization of these two constructions, especially that there are many other interesting ways of combining objects which one would also want to include under the generalization. The classical example of a construction of combining objects which is neither a product nor a sum is the construction of a tensor product of two abelian groups. A common generalization of these constructions is of course the notion of a monoidal category.

We have thus far described the fragment of the above diagram enclosed in the region shown below:

2. Algebraic vs geometric nature of a category

We will now describe the fragment of the initial diagram enclosed in the region shown below: 

The notion of a monoid is equivalent to the notion of a single-object category. So we may think of a monoid as a category with "few objects". What is a category with "few morphisms"? A poset! We may think of a poset as a category in which between any two objects there is at most one morphism (in one or the other direction, to encode antisymmetry as well). So the notion of a category seems to naturally split into two more primitive notions: that of a monoid and that of a poset. This split can be seen as a decomposition of the notion of a category into its algebraic nature (monoid) and its geometric nature (poset). A monoidal category can then be seen as a category enforced with additional algebraic structure. What is then a geometric enforcement of the notion of a category? This is where the notion of a form enters the picture.

3. Short exact sequences, subobjects, quotients, and forms

 

Linearity is an important ingredient of the notion of an abelian category. Another important ingredient is exactness: that every morphism decomposes as a cokernel followed by a kernel. The following result is from "Duality in non-abelian algebra II" by Z. Janelidze and T. Weighill (Journal of Homotopy and Related Structures, 2016):

Let us explain the concepts in this corollary:

• A Grandis exact category is a category equipped with an ideal of null morphisms in the sense of C. Ehresmann, such that every morphism admits a decomposition into a cokernel followed by a kernel, relative to the ideal. In the pointed case, this becomes the notion of a Puppe-Mitchell exact category: a pointed category where every morphism decomposes as a cokernel followed by a kernel (both in the usual sense of a pointed category).
• An Isbell bicategory is a category equipped with a proper factorization system. The corresponding "form of quotients" is the fibration of quotients and the "form of subobjects" is the opfibration of subobjects.  

Specializing the result above to a pointed category equipped with a proper factorization system given by a class "E" of epimorphisms and class "M" of monomorphisms, we get the following

Theorem: Such a category is exact (i.e., every morphism decomposes as a cokernel followed by a kernel) if and only if the fibration of "E"-quotients is isomorphic to the opfibration of "M"-subobjects.       

This theorem is analogous to the fact that a pointed category is linear if and only if it has binary sums and products such that the monoidal structure of sum is isomorphic to the monoidal structure of product. In this analogy, the notion of subobject corresponds to the notion of product and the notion of quotient corresponds to the notion of sum. What corresponds to a monoidal structure is a form, by which we simply mean a faithful functor whose fibres are posets. Both, fibrations of quotients and opfibrations of subobjects are forms. A form equips every object of the category with a poset (the fibre at that object), so in view of the previous discussion about algebraic vs geometric nature of a category, a form can be seen as a geometric enforcement of the notion of a category. There are two canonical types of forms, given by subobject forms and quotient forms, just like there are two canonical types of monoidal structures given by products and sums. Their coincidence, in the context of a pointed category equipped with a proper factorization system, gives, by the above theorem, a characterization of exact categories. On the monoidal side, what corresponds to requiring the existence of a proper factorization is the requirement of the existence of all finite products and sums. 

To complete the analogy between the monoidal vs formal situations, we need to answer the following questions:

Question 1. What is geometric/formal analogue of tensor product as a third type of monoidal structure, different from product and sum, but nevertheless an important example of a monoidal structure?

Question 2. What is geometric/formal analogue of the notion of a biproduct?

We leave answering the first question to the end of the talk and answer now the first question. A biproduct is, loosely speaking, something that is both a product and a sum, plus these two must satisfy compatibility conditions. Thus we want something that is both a subobject and a quotient with some compatibility conditions. The answer is: a short exact sequence, i.e., a sequence of morphisms

where the first is a kernel of the second and the second is a cokernel of the first. A linear category can be thought of as a pointed category having sufficiently many biproducts, where "sufficiently many" means that any two objects can be completed to a single biproduct diagram. With some loose analogy, here, an exact category is a pointed category having sufficiently many short exact sequences, where "sufficiently many" means, this time, that any single morphism can be completed to a commutative diagram with two short exact sequences:

We have thus described the following part of the initial diagram:

To complete description of the diagram, we need to describe its bottom part:

This is summarized by the following well known fact: an abelian category is a linear exact category. 

4. A Noetherian Form over the Category of Sets   

A noetherian form is a form satisfying the axioms given in the paper "Duality in non-abelian algebra IV" by A. Goswami and Z. Janelidze (Advances in Mathematics, 2019). These axioms are self-dual in the sense that a form satisfies them if and only if the dual form (i.e., the dual functor) satisfies them. The axioms allow to establish homomorphism theorems for group-like structures, such as the isomorphism theorems and homological diagram lemmas.

The form of subobjects/quotients of an exact category is noetherian. The form of subobjects of a category having finite limits and colimits is noetherian if and only if it is a semi-abelian category in the sense of G. Janelidze, L. Márki, and W. Tholen (J. Pure Appl. Algebra, 2002). Although neither the category of sets, nor its dual, is a semi-abelian category, it still has a noetherian form. This form is neither a subobject form and nor it is a quotient form. Under this form, the fibre of a set is given by the poset of ordered pairs consisting of an equivalence relation and a subset that is a union of equivalence classes. This form is the (an) answer to Question 1. A thorough analysis of this form is being written up in a joint work of Zurab Janelidze and Francois van Niekerk, which is based on the results given in the PhD Thesis of the second named author.

5. Contrasting Features of the Monoid-Form Analogy 

As demonstrated above, there is a striking analogy between the monoidal/formal roots of the notion of an abelian category. This analogy has some interesting contrasting features too:

• A monoidal structure is an internal monoid in the 2-category of categories. A form is not an internal poset in the 2-category of categories.
• Products and sums, once they exist, are unique (up to isomorphism). A category may have several non-isomorphic proper factorization systems.
• Isomorphism between the monoidal structure of product and the monoidal structure of sum forces the category to be pointed. Exact categories need not be pointed categories.

The middle point above could perhaps be remedied by relaxing the notion of a monoidal structure of sum (and accordingly, the dual notion of a monoidal structure of product), replacing it with sum structure in the sense of Z. Janelidze (Cover Relations on Categories, Applied Categorical Structures, 2009): a monoidal structure where the monoidal unit is an initial object and the resulting canonical morphisms into the tensor,

are jointly epimorphic. Isomorphism of a sum structure and a product structure (dual to sum structure) trivially forces pointedness. However, it does not force linearity: this isomorphism holds in every unital category in the sense of D. Bourn. Moreover, a pointed category with products and sums in which the canonical morphism from the coproduct to the product is both a monomorphism and an epimorphism, but not necessarily an isomorphism, will have both the usual sum and the usual product being bisum structures (defined as sum structures which are isomorphic to product structures) without these two being isomorphic to each other. There surely ought to be such a category!

6. Conclusion 

An intriguing analogy between the monoidal roots and the formal roots of the notion of an abelian category leads to a new notion of a "bisum structure", which under this analogy presents itself as the counterpart of a Grandis exact structure. Combining these two notions may give an interesting generalization of the notion of an abelian category, not considered yet in the literature. Relaxing a Grandis exact structure to a noetherian form, these ideas will come close to the ideas of Francois van Niekerk developed in "Biproducts and commutators for noetherian forms" (Theory and Applications of Categories, 2019): there he defines a biproduct in the context of a noetherian form, which is an example of our bisum structure. 

 

Read More