for academia, mathematics, music, art and philosophy

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, 781812. 

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?


Post a Comment