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

Research Interests of 2+ Year Level 2022 Mathematics Teaching Staff at Stellenbosch University

The content of this post is author's adaption of photos and information sourced from open internet.

Liam Baker

Broad research interest: number theory

Year of first publication: 2016

Bruce Bartlett

Broad research interests: topology, geometry, category theory

Year of first publication: 2011

Dirk Basson

Broad research interests: number theory, algebra

Year of first publication: 2017

Ronalda Benjamin

Broad research interests: analysis, topology, algebra

Year of first publication: 2016

Gareth Boxall

 

Broad research interests: logic, number theory, analysis

Year of first publication: 2011

James Gray

Broad research interests: category theory, algebra

Year of first publication: 2010

Retha Heymann

Broad research interest: analysis

Year of first publication: 2014

Michael Hoefnagel

Broad research interests: category theory, algebra

Year of first publication: 2019 

Karin-Therese Howell

Broad research interest: algebra

Year of first publication: 2010 

Zurab Janelidze

Broad research interests: category theory, algebra, set theory, logic, combinatorics

Year of first publication: 2003

Francois van Niekerk

Broad research interests: order theory, category theory, algebra

Year of first publication: 2019

Sophie Marques

Broad research interests: algebra, number theory

Year of first publication: 2019

Sonja Mouton

Broad research interests: analysis, algebra

Year of first publication: 1996

Dimbinaina Ralaivaosaona

Broad research interests: combinatorics, number theory, probability theory

Year of first publication: 2012

Leon van Wyk

Broad research interest: algebra

Year of first publication: 1988

Marcel Wild

Broad research interest: order theory, combinatorics, computer science, information theory, algebra, probability theory, analysis, game theory 

Year of first publication: 1989

Read More

The poset of matrix properties

Below are the notes for the talk above, given at the Algebra, Geometry, Topology & Applications seminar.

1. Bird's-Eye View of Exactness Properties 

One of the active areas of research in Categorical Algebra is the study of various properties of categories expressed using limits and colimits. Such properties are usually referred to as exactness properties. This terminology comes from the fact that, historically, the first such properties emerged in the study of exact sequences in the sense of Homological Algebra. The matrix properties in the title of this post are particular types of exactness properties, which can be encoded using integer matrices. Before explaining what they are, let us first recall the notions of limit and colimit.

Given a diagram of objects and arrows (objects are certain mathematical structures and arrows are morphisms between them), a limit (of the diagram) is a way to encode the information about the diagram in a single object; it is a terminal (commutative) cone over the diagram. The notion of a colimit is defined by "reversing arrows" in the definition of a limit.

Examples of limits and colimits abound in mathematics:

• Various complex topological spaces are colimits of diagrams of simpler spaces.
• Higher dimensional vector spaces are limits of lower dimensional spaces.
• Cartesian products of mathematical structures (e.g., sets, groups, topological spaces with the Tykhonov topology) are instances of limits.
• Every set is a colimit of singleton sets. A singleton set itself is a limit of the empty diagram.
• Starting with a unit interval, combining limits and colimits we can build spaces such as the sphere, the torus and the Klein bottle (among many others).
• The monoid of words decomposes as a colimit of multiple copies of the additive monoid of natural numbers. 
• Taking the quotient of a mathematical structure (e.g., of a set by an equivalence relation, or of a group by a normal subgroup), is an example of a colimit.
• Intersection of subsets of a set and inverse image of a subset along a function are examples of limits.
• Profinite structures (e.g., profinite groups) are special types of limits of finite structures.
• Addition and multiplication of natural numbers are examples of colimits and limits.
• etc.

Each of these examples require a suitable category, in which it is specified what objects are, what morphisms are between objects (arrows), and how we compose them (which we need for expressing commutativity). The following two points are worth noting:

• For a given diagram, its limit (as well as colimit), when the latter exists, is unique, but only up to isomorphism.
• Every limit is a colimit in the dual category (a category obtained from a given one by reversing the direction of arrows).

From a concrete perspective, which looks at mathematical structures through the lenses of their elements, limits and colimits are tools for constructing local objects in a given universe of mathematical structures. From a more abstract perspective, limits and colimits are tools for analyzing global properties of universes of structures. Here is a striking analogy: in real life, addition and multiplication of natural numbers are means for accumulating quantity; in number theory, they are means for studying the natural number system. This is not a mere analogy, as addition and multiplication of natural numbers are instances of colimits and limits in the category where objects are natural numbers and a morphism from, e.g., 2 to 5, is a function from the set {0,1} to the set {0,1,2,3,4}.

Picking up on the previous analogy, as much as the study of the natural number system employs analysis of properties of multiplication and addition, the study of a category employs analysis of properties of limits and colimits. It turns out that properties which involve limits or colimits only, are much easier to study, than properties which involve both limits and colimits. This is in fact true in number theory as well, where purely from the additive point of view, the natural number system is nothing other than the monoid of words of a singleton alphabet, i.e., it is a free monoid over a singleton, and from the multiplicative point of view, it is a free commutative monoid over a countable set (namely, the set of prime numbers via the prime number decomposition). However, unlike in number theory, we are not studying here a single category, but all of them, which brings in properties that are not necessarily true in every category. Determining implications between those properties can be a nontrivial task, even if the properties are expressed in terms of limits or colimits alone.

2. Matrix Properties

In an n-dimensional cube, mark some vertices with a blue marker, and mark one of them with red. Then, consider a property of a mathematical structure X which states that for every representation of the cube in the n-th power of X, and for every substructure S of the n-th power of X, if the blue vertices fall in S, then so must the red vertices.   

This becomes a property of a category, if we ask the property to hold for every object X in the category (to formulate the categorical property, one would use "generalized elements" in the place of "elements"). Such property can be represented using a matrix of 0's and 1's, where each column of the matrix is a column-vector of coordinates of blue vertices, provided we choose the red vertex to be the point with all coordinates equal to 0. Hence the name matrix property. For the rotating figure above, the matrix will be:

    Points: C D F B H I P

   Axis AI: 0 0 0 0 0 1 1

   Axis AB: 0 0 0 1 1 0 1

   Axis AD: 0 1 1 0 1 0 1

   Axis AC: 1 0 1 0 1 0 1

Now, representing the cube in the n-th power of X amounts to choosing elements of X that will be called 0 and 1. In this case n = 4 and the property states that for arbitrary choice of 0 and 1 in X, if all columns of the matrix above belong to some substructure of X, then so does the column of zeros. We give here two examples of categories having this specific matrix property:

• The category of groups. If X is a group, then we can express A as e.g. A = C - F + D.
• The category of lattices. If X is a lattice, then we can express A as e.g. A = (C /\ D) \/ (D /\ B) \/ (B /\ C).

The same property turns out to hold in the dual category of the category of sets, as well as in the dual of the category of topological spaces, and many other categories.

In the figure above, if we delete the points B, H, I, P, we will obtain a matrix property that defines Mal'tsev categories, among which are many categories of group-like structures as well as the dual of any topos. On the other hand, if we delete the points F, H, I, P, then we will obtain a matrix property that defines majority categories. Majority categories play a similar role for lattice-like structures as Mal'tsev categories do for group-like structures. Many theorems for groups and other similar structures can be proved in Mal'tsev categories. Similarly, many theorems for lattice-like structures can be proved in majority categories. The dual of the category of topological spaces happens to be a majority category, but not a Mal'tsev one.

The matrix property defining Mal'tsev categories implies the property given by the matrix above, simply because one matrix can be obtain from the other by deleting some columns. This is intuitively clear: if fewer blue vertices guarantee the red, then a surplus of blue vertices will still do the same. The majority property implies the property above for the same reason. However, in general, implications of matrix properties are not given by merely addition of columns. These implications are context sensitive (for which class of categories do we want the implication to hold?) and in the context of algebraic categories, where matrix properties become a special type of linear Mal'tsev conditions, we do not know yet an algorithm for deciding them. Very recently, we found an algorithm for deciding implications of matrix properties in the context of categories having finite limits. This context is the context for definitions of Mal'tsev category, majority category, as well as many others that have been studied in Categorical Algebra since 1990's, and hence it is a natural habitat of matrix properties. The algorithm settles a problem that has been open since a general notion of a matrix property was first proposed in my MSc Thesis in 2004.

3. The Algorithm

The algorithm for deciding implications of matrix properties has a geometric description. To explain it, we first need to define a notion of a reduction of a matrix. We will say that a matrix L is a reduction of a matrix M when L can be obtained from M by a succession of the following transformations:

• Expansion: when a new dimension is added to the cube (in any position), but the colored vertices do not change their position.

• Collapse: when one of the dimensions of the cube is collapsed and the colored vertices are projected along the collapsing dimension.

• Tilt: when given two dimensions in the cube, such that all colored vertices are on the same end of the first dimension, colored vertices on one side of the second dimension slide along the edges of the first dimension.

• Inside-out turn: when all colored vertices change their position on the edge of a given dimension. 

If the structure of blue vertices of a reduction L of M can be embedded in N, then we can add to N a blue vertex at the relative position of the red vertex in L. The algorithm says that M will imply N provided after a series of increments of blue vertices in N using reductions of M, the red vertex of N will get colored blue. 

The only time this algorithm will fail to detect matrix implication is when M has the following reduction

   1 0 

   0 1

and N has the following reduction

        1

In these two cases, the matrices M and N do imply each other and moreover, they imply all other (nonempty) matrix properties. Categories having these properties are preorders -- this is the trivial case.

A similar algorithm works if we want to establish that a conjunction of a family of matrix properties implies another matrix property, except that then the reductions L which are used to increment N can each time be reductions of a different matrix in the family.

4. Computer-Generated Results

The algorithm allowed us to use computer programming for computing various fragments of the poset of matrix properties of categories having finite limits. The image below displays the poset of non-trivial 3-dimensional matrix properties (excluding the matrix property that holds for all categories -- the anti-trivial case). In this image, shaded cells represent the entry 1 in the matrix, while unshaded ones represent the entry 0.

All of the implications above can actually follow from deletion of columns except the very bottom one. We leave it as an exercise to establish the bottom implication using the algorithm described above. The poset of (non-trivial and non-anti-trivial) 4-dimensional matrix properties is much larger. There are altogether 442 non-equivalent 4-dimensional matrix properties, with the following distribution, where the numbers on the horizontal axis count blue vertices on the 4-dimensional cube:

It is difficult to display all 442 of the 4-dimensional matrix properties on one picture, so will limit the number of columns (blue vertices) to 6:

The highlighted matrices represented exactness properties already encountered in literature (in most cases, in the case of algebraic categories). Read from bottom to top, left to right, they are:

• Mal'tsev + majority ("arithmetical"),
• Mal'tsev + 4-near-unanimity,
• majority,
• 4-minority,
• refinement of Mal'tsev with directly decomposable congruences,
• minority,
• Mal'tsev,
• 3-edge,
• 4-ary near unanimity,
• 4-edge,
• refinement of directly decomposable congruence classes,
• refinement of the egg-box property,
• refinement of normal local projections.

5. Some Theorems and Concluding Remarks

The algorithm is useful not only for using the computer to generate fragments of the infinite poset of exactness properties, but also for proving theorems about exactness properties that help one understand the structure of this poset. Some of these theorems were inspired by the computer-generated pictures. Here we briefly review some of the theorems that we managed to establish thus far.

Theorem. The infinite poset of matrix properties given by diagonal matrices is as described in the figure below. 

Diagonal matrices are those where the only non-zero entries lie on the main diagonal, but the red vertex need not have all coordinates equal to 0. In the figure below, m represents the dimension of the diagonal matrix and k represents the number of non-zero coordinates of the red vertex.

Theorem. The conjunction of Mal'tsev and majority properties (i.e., the "arithmetical" case) implies any other non-trivial matrix property.

Theorem. Each matrix property is either implied by the majority matrix or implies the Mal'tsev property (but not both).

Theorem. Among matrix properties that are not anti-trivial, there are no maximal matrix properties.

We conclude with a few important remarks:

• In this post, we limited our attention to binary matrix properties, i.e., when the entries in the matrix are either 0 or 1. The theorems above are valid only in the binary case. The geometric interpretation of matrix properties using n-dimensional cubes is also only valid in the binary case.
• The algorithm for deciding implications of matrix properties was established in [HJJ]. The pictures of some fragments of the poset of matrix properties are also from [HJJ].
• The theorems above are from [HJJvdW].
• Matrix properties were first introduced in [J] (see [HJJ] for additional references).
• Majority categories were first introduced in [H], by an application of the "matrix method" for translating universal-algebraic properties into exactness properties described in [J].
• The notion of a Mal'tsev category, defined in the context of categories having finite limits, first appeared in [CPP].
• This post is an extension of another post, which gives a shorter and a complementary account of the results discussed here.
• The geometric interpretation of the algorithm presented in this post is an original contribution of the post. A paper will be written up on it, hopefully some time soon.
• Moving diagrams were designed on Geogebra, recorded using Wondershare UniConverter, and turned into gif files using ezgif.
• Python implementation of the algorithm can be found here. The software is called "mclex".
• The fourth author of [HJJvdW] was a first-year student at Stellenbosch University, when he joined the research project.

References

[CPP] A. Carboni, M.C. Pedicchio, and N. Pirovano, Internal graphs and internal groupoids in Mal’cev categories, Canadian Math. Soc. Conference proceedings 13, 1992, 97-109.

[H] M. Hoefnagel, Majority categories, Theory and Applications of Categories 34, 249-268, 2019.

[HJJ] M. Hoefnagel, P.-A. Jacqmin, and Z. Janelidze, The matrix taxonomy of finitely complete categories, submitted for publication, 2021.

[HJJvdW] M. Hoefnagel, P.-A. Jacqmin, Z. Janelidze, and E. van der Walt, On binary matrix properties, submitted for publication, 2021.

[J] Z. Janelidze, Matrices of terms and relations in categories, MSc Thesis, Tbilisi State University, 2004.

Read More

Imagination (opus 1011)

The video shows two dancers, a man and a woman. The woman exists in the imagination of the man. Perhaps it is someone he knew, loved, cared for... Ballet-style gentle dance of the woman is contrasted with a free-style rough dance of the man. This symbolizes the unattainability of the imagination. Half-way in the video the man is shown collapsed on the floor. This scene is intended to reveal that the man has actually been suffering from the unattainability of his imagination. He longs for the woman, who remains to be only a fragment of his imagination throughout the video. Towards the end of the video, the woman dances to a light and playful music. The video ends with the man walking away from the camera. He momentarily stops, looks back, and then confidently makes a few more steps in the direction he was heading, away from the camera, till the video concludes. The man has resolved the problem: the joy of her existence, even if only in his imagination, must overcome the suffering. 

Read More

Monotony (opus 1128)

The Merriam-Webster Dictionary defines the word "monotony" as "tedious sameness". For a creative soul, monotony is on par with torture. This piece conveys the struggles of the soul that has been trapped in monotony and is looking for ways to break free from it. The video shows a man performing various free style dance moves as an expression of the struggles. Behind him is a wall on which, in the first part of the video, projects a movie of clouds moving through the sky. This is a symbolism of one's creative aspirations before one becomes a prisoner of monotony. In the second part of the video, the projection changes to showing the dancer in action, from multiple angles. This symbolizes that after a while of monotony, the aspirations dissolve into excessive awareness of one's own self. At this stage, an illusion of having broken free from monotony may arise, which is symbolized by the scene with the chair. The chair is the illusion of freedom, illustrated by the dancer performing various dance moves over and around the chair. During the scene with the chair, the music is cheerful. This scene transitions into a scene leading to the finale, where the chair is gone and the mood of the music drops low signifying the sad realization that the feeling of having broken free from monotony was only an illusion. Right at the very end, the scene shows the dancer up close. A moment after the music has stopped, the dancer abruptly turns his head around as part of what seems to be another dance move, which ends the video. It leaves the viewer uncertain whether monotony has been overcome or not; the intention here is to urge the viewer to contemplate on their own monotony and ask the question whether it has been overcome or not?

Read More

A Gap in Mathematics Education

The process of creation of mathematics has the following hierarchically dependent components:

• Coming up with a concept.
• Coming up with a question dealing with a relationship between concepts (this includes formulating a hypothesis, as well as finding an example or a counterexample of a concept/phenomenon).
• Answering a question dealing with a relationship between concepts (this includes proving theorems as well as solving problems without being given the recipe for solution).
• Applying the answer to a question dealing with a relationship between concepts to answer another such question (this includes solving problems by applying a given recipe for solution).

Modern mathematics education (both at the school and at the university levels) focuses mainly on the last two points. What is regarded as a low quality mathematics education would focus only on the last point. For a more whole mathematics education, the first two points must receive as much attention as the last two points do. 

It is not difficult to implement the first two points in the practice of mathematics teaching. Here is an example of the structure of a class that focuses on the second and the third points:

1. The teacher proposes one or two concepts that the pupils are familiar with (perhaps, by taking suggestions from the class). 
2. The teacher then asks the pupils to explain the concepts, helping the pupils in the explanation, when necessary. 
3. Then, the teachers asks the pupils to think of a question that would combine the named concepts. The teacher helps in this process.
4. After this, the teacher and the pupils engage in answering the question together. 
5. If the question is too hard to answer, it should be concretized to a simpler question. If the question is too easy to answer, it should be abstracted to a more difficult question.

Concepts arise in mathematics as a necessity to help one express a general phenomenon. Incorporation of the first point in a classroom can be achieved by explaining this necessity for the concepts that the pupils are already familiar with, or by taking pupils on a journey that would help them identify such a necessity and will result in (re)discovering a mathematical concept. Teaching concepts by first showing examples and then asking the pupil to develop a concept that fits those examples is another, perhaps simpler, way. The activities which ask a pupil to identify a pattern in a sequence of numbers or figures is in some sense of this type. However, these activities are sold as activities that fall under the third point, as the pupil is being convinced that the question must have one definite answer.

Read More

Metaphysics of Human Function based on a Mathematical Structure

work in progress

I propose here a theory of human function, which I have been developing based on introspection. In this theory, human function is represented in terms of exchange of information of four agents, which I call the spirit, the mind, the soul and the body. Although these are surely familiar terms, having a variety of scientific, pseudo-scientific, religious, philosophical and other usage, I do not assume any insight derived from such usage. The essence of each of these agents will be revealed through the roles that they play in human function. Matching of this essence with any of the existing definitions of these entities is unintentional and may well be coincidental.

The four agents are organizes in the following directed graph:

We call it the Human Function Scheme (HFS for short). The arrows represent directions of information flow from one agent to another.

Postulate 1. Human function is marked by internal information processing within each of the four agents as well as exchange of information along the arrows of HFS. 

Postulate 2. When a human being is engaged in a particular activity, information flows between the agents in consistent cyclic patterns. Change of activity may change these patterns. 

Postulate 3. These cyclic patterns are made of three fundamental ones - the three cycles of HFS.

The cycles referred to in Postulate 3 are:

Whatever we claim to perceive consciously, is information processed in the Spirit. There are two arrows going into Spirit. Information flowing from Body to Spirit is the sensory ingredient of human's conscious perception. Information flowing from Soul to Spirit is the non-sensory ingredient human's conscious perception, such as thoughts, logical essence, etc. Rigorous research is needed to be able to develop a more refined distinction between these two ingredients of our conscious perception. We will hitherto distinguish them using the terms concrete perception (for Body to Spirit) and abstract perception (for Soul to Spirit). 

The arrow going out of Spirit is the channel through which our conscious impacts human function. We call information flowing along this arrow Will. The rest of the arrows have names too: subconscious perception (for Body to Mind), abstraction (for Mind to Soul), concretization (for Soul to Body).

There terms are somewhat suggestive of the role that the arrows of HFS play in human function. A better understanding of this role will be achieved when describing different types of human function in the context of HFS. 
 

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

Abstract Structures in Mathematics and Music

These are notes for my online discussion with Georgian Student Parliament on Tuesday 7 December, 2021, organized by Nina Tsatsanashvili. All photos in this post are from Wikipedia. 

If you look up the word "structure" on the Google Dictionary, you will find the following definition: the arrangement of and relations between the parts or elements of something complex. When the "parts or elements" are subject to specific interpretation, we have at hand an "abstract structure". For example, consider a painting, which can be seen as an arrangement of colors. For instance, Leonardo da Vinci's Mona Lisa:

This is not an abstract structure, since its constituents are specific colors that can be found on a specific poplar wood panel that currently resides in a gallery of the Louvre Museum in Paris. In contrast, Ludwig van Beethoven's Für Elise is an abstract structure, since the sounds that make up this musical piece are dependent on the interpretation of musical performer of the piece, as well as the instrument on which the piece is performed.

In this sense, abstract mathematics is similar to composition in music: in both cases one builds structures that are inherently abstract. The analogy goes further: a musical performer can be compared to an engineer, for instance, who produces concrete structures by means of concrete interpretations of the abstract mathematical structures.

 

In fact, the analogy goes even further than that. A completed piece of work in music, that is, a musical composition, is analogous to a "mathematical theory". A mathematical theory is an exploration of one or several special types of mathematical structures and their interrelation, similarly how in a musical composition one explores one or several types of musical structures and their interrelation. In both cases, abstract structures often organize into more abstract forms. 

As an example of a form of abstract structure in mathematics, consider the following diagram:

This diagram displays two mathematical structures, given by Fig. A and Fig. B. Each of them are abstract structures in the sense that the points and the arrows in each structure are subject to interpretation. The two structures have a similar form: they are both made out of points and arrows. Such structures in mathematics are called directed graphs. A mathematical theory that explores various different types of graphs and their interrelation is called graph theory. Graph theory, however, is not only about directed graphs. Other mathematical structures are also part of the theory, such as natural numbers, for instance. They arise by counting various different phenomena dealing with graphs: for example, by counting how many trajectories connect one point of the graph with another. 

Similarly, in a single musical composition, there is one (or several) main forms of musical structure, whose different manifestations are being explored, along with their interrelations, in the composition. What is the main form of musical structure in Für Elise?

     

Read More

A surprising story of how a computer was taught to prove some theorems in finitely complete categories

Notes for the talk given at the 2021 Congress of South African Mathematical Society on 29 November. 

1. Finitely complete categories

A finitely complete category is a category that has finite products and equalizers (and hence, all finite limits). Not every category is finitely complete, but most categories of mathematical structures are. 

There is a representation theorem for finitely complete categories (Yoneda embedding), which allows to present any category as a full subcategory of a (larger) category of presheaves of sets, which is closed under all limits that exist in the category. This means that a lot of times, proving a theorem in a finitely complete category involving finite limits, reduces to proving the same theorem in the category of sets. 

For instance, the fact that the product of objects is commutative, up to a canonical isomorphism, can be deduced from the fact that the same is true for the cartesian product of sets. Or, the fact that the composite of two monomorphisms is a monomorphism can be deduced from the fact that composite of two injective functions is injective.

2. Mal'tsev conditions

What would we want to prove in a finitely complete category that is not easily true in the category of sets? 

A lot of Mal'tsev conditions encountered in universal algebra can be reformulated as properties expressible in any category. Historically first Mal'tsev condition, stating that there is a ternary term "p" satisfying the following identities, is such.

The "x"-s here represent variables of the algebraic theory of a variety of universal algebras. The condition above states that it is possible to express an operator "p" using basic operators of the theory, such that the identities become theorems of the algebraic theory (once the "x"-s are universally quantified); equivalently, these identities hold in every universal algebra of the variety. 

Such term "p" can be found in varieties of group-like structures, where we can set:

An abstract finitely complete category, however, possesses no algebraic theory and so it becomes impossible to talk about the term "p" (at least, not quite, see this paper from 2008, by D. Bourn and myself). Nevertheless, it is possible to reformulate the property of the existence of "p" as a property of the category of algebras in the variety. And there are many other Mal'tsev conditions which can be so reformulated!

3. Matrix properties

What we may be interested in, then, is when does one such reformulated Mal'tsev condition imply another, in any finitely complete category? 

The reformulated Mal'tsev conditions that we consider can be described by matrices of integers that appear as subscripts of the corresponding system of term identities. For instance, in the case of the system considered above, the matrix would be

Note that we can disregard the RHS of the equalities in the system if we agree to always use the subscript "0" for the variable there. 

To describe the corresponding condition on a category, we first need the following notion:

Such notion can be produced for every matrix M of integers, of arbitrary dimensions. The number of rows of the matrix determines the arity of the "internal binary relation" for which "strict M-closedness" will be defined. 

The condition on a finitely complete category corresponding to a matrix M states that every internal relation in it (of suitable arity) is strictly M-closed. In the case of the matrix M considered above, this is the familiar property that defines a Mal'tsev category as a finitely complete category in which every internal relation is difunctional, considered here:

To prove that one matrix property implies another in any finitely complete category, we would have to begin with an internal relation R for which we want to establish a property N, and build from R, using finite limits, another internal relation S for which we would apply a property M to conclude that R has the property N. Thanks to the representation theorem above, this reduces to doing the same inside the category of sets. However, it does not really simplify the task: finding the construction of a suitable relation S to get the desired property of R may be tricky.

4. Michael's work

A surprising insight comes from Michael Hoefnagel's work on "majority categories". These are categories defined by the matrix    

The corresponding term can be found in varieties of lattice-like structures, where

In attempting to show that protoarithmetical categories in the sense of D. Bourn are not the same as Mal'tsev majority categories, he discovered that the duals of the categories of relations (on sets) are able to detect implications of matrix properties (see this paper of his). This leads to formulating an algorithm, that we implemented on a computer, for deciding implications of matrix properties. 

The story of how exactly one arrives to the algorithm is an interesting one in its own right. It actually builds on ideas contained in this paper of Thomas Weighill, which is another interesting story that comes out of an observation of how the Mal'tsev property (corresponding to the first matrix considered above) relates to a separation axiom in topology.

5. The algorithm

Here we cut short all of these interesting stories and instead, present the algorithm directly, on a concrete example. 

As we will explain below, the following table gives a proof of the fact that a Mal'tsev majority category has the matrix property of "arithmetical varieties".

The first row of this table states the theorem. The purple matrix is the Mal'tsev matrix. The orange matrix is the majority matrix. The blue matrix is the matrix corresponding to the property of arithmeticity. The theorem is thus that the first two matrix properties together imply the third. According to our algorithm, the following procedure allows to confirm this implication. 

We want to introduce new columns to the blue matrix until we get a column of 0's. To do that, consider the orange matrix in the second row. Each row in this matrix is obtained from the orange matrix in the first row by renaming its entries (the renaming rule may be different across different rows). The corresponding renaming of entries in the invisible column of 0's of the orange matrix in the first row, results in the blue column in the second row. Each row of the blue column thus shows to what was 0 renamed in the corresponding row of the orange matrix (in the second row of the table). Furthermore, every column of the orange matrix in the second row of the table must be a column of the blue matrix in the first table. Similarly, the in the third row of the table we finally obtain the blue column of 0's. This time, we rely on the purple matrix rather than the orange one. Just like the orange one, that purple matrix has every row obtained from a row of the purple matrix in the first row of the table by renaming of its entries, while every column of the purple matrix is one of the previous blue columns (including the one obtained in the previous step).

That the successful execution of the procedure above can confirm the theorem was already known, at least implicitly, from this paper of mine, which is one of the first two papers on matrix properties. What is new is that we now know that a theorem stating implication of matrix properties will be true if and only if it can be established using the algorithm. Thus, in the language of mathematical logic, we had soundness and now we have established completeness.

6. Computer enters the scene

Execution of the algorithm above may not be easy at all. Although the process is always finite, there may be a significant amount of steps we need to take, before we reach the destination. By hand, this task may take a very long time. In fact, it may take a long time even using a computer. Nevertheless, the computer can do better. The following computer-generated image shows all implications between equivalence classes of matrix properties given by "binary matrices" having four rows and up to seven columns, where black spots represent entry 1 and white ones represent entry 0:

We leave it as an exercise to find the Mal'tsev and majority matrices in this diagram (note that matrix properties are invariant under permutation of columns in the representing matrix). 

Interestingly, the poset above (which grows from left to right) appears to have the smallest element -- the left-most matrix. This matrix is in fact the one corresponding to the property of arithmeticity. As Emil van der Walt (grandson of Andries van der Walt) proved in his first year of undergraduate studies, this matrix property implies every other binary matrix property. It has been furthermore shown that every binary matrix property either implies the Mal'tsev one, or is implied by the majority property.

7. Concluding remarks

Let me conclude by adding to the title: not only was a computer taught to prove some theorems in finitely complete categories, but the computer also helped us to identify new theorems that we, humans, were able to prove (and which would be impossible for the computer to prove using the algorithm, since they deal with an infinite number of matrices).

The results described in this talk are taken from two recent papers, the first by Michael Hoefnagel, Pierre-Alain Jacqmin and myself, and the second, by the three of us and Emil van der Walt. The work on these papers is complete and links to them will be placed here once they are published. You can see the arXiv preprint of one of them (note however that a slightly revised version of this preprint is still to be posted). The work on both of these papers was carried out in 2020-2021, and started with a visit of Pierre-Alain Jacqmin to Stellenbosch in January 2020.

Read More