Initiated seven new collaborative research projects within the Mathematical Structures research programme, that includes researchers and postgraduate students from various universities in South Africa: operator semigroups, measure structures, metric frames, canonical extensions, ranked monoids, sum structures, lower topology.
Supervised and co-supervised nine postgraduate students (two honors, two masters, and five phd).
Represented South Africa at the General Assembly of the International Mathematical Union along with a colleague in Mathematics Education.
In collaboration with colleagues and students, developed and delivered a successful math-music theatrical production for the celebration of the International Year of Basic Sciences for Sustainable Development. The production was supported by NITheCS, ASSAf and DSI.
Developed and delivered four national postgraduate courses online: SOFiA on python, mathematical structures (in collaboration), introductory set theory (in collaboration), category theory.
Executed presidential duties for SAMS: chairing of SAMS council meetings, of the AGM, opening and closure of the SAMS congress, etc. Prepared and delivered presidential address at the AGM (in consultation with the SAMS Council) to give a direction to SAMS activities in the coming years.
Elected as NITheCS associate co-representative, and in this role, served on the NITheCS management committee monthly meetings.
Ran the national research programme in mathematical structures under NITheCS along with three other principal investigators in the research programme.
Two co-authored papers published, one in Journal of Symbolic Logic. Co-authored paper in Order accepted for publication.
Served on the programme committee of the international conference "Topology, algebra and categories in logic" held in Coimbra, Portugal.
Gave two interviews (radio and youtube).
Taught and co-taught and/or convened six modules at Stellenbosch University, including two engineering mathematics modules, one honors module and two third-year modules.
Progress made on existing and new research projects and delivered talks on those.
Carried out duties in the role as mathematical sciences programme coordinator and member of a university research committee.
Carried out refereeing and editorial duties (not listed below).
November-December 2022
Research discussion (9 December) with Dr. Christian Budde: started research project on the category theory of operator semigroups.
Chaired the Annual General Meeting of the South African Mathematical Society (8 December).
Gave a SAMS Congress talk on the noetherian form of sets.
Gave opening and closing speeches at the 65th Congress of the South African Mathematical Society (6-8 December), held at Stellenbosch University.
Gave an opening speech at the special meeting of the Mathematics section of National Graduate Academy (5 December).
Chaired the fourth Council Meeting of the South African Mathematical Society (2 December).
Conducted weekly 6-hour tutorial sessions in November for students in Foundations of Abstract Mathematics I for additional assessment opportunity.
The paper on ordinal number systems fully published in the Journal of Symbolic Logic.
Submitted author comments on the journal proofs of the paper on stack combinatorics (joint work with Helmut Prodinger and Francois van Niekerk). The paper is being published by Springer Order.
Hosted research visit (18-20 November) of Dr. Cerene Rathilal. Started joint work on measure structures.
Submitted a report on the Mathematical Structures Research Programme at NITheCS and delivered a talk at the NITheCS Associates Workshop on the progress of the research programme.
Made progress with Kishan Dayaram on diagram lemmas in the context of noetherian forms.
Fundamano production (4 November) was a success -- full house attendance and well received. See: videos, press release.
September-October 2022
Gave a talk on at the "Topology, Algebra, and Category Theory" international conference (19-22 September) dedicated to the 65th birthday of Themba Dube. The subject of the talk was metric frames.
Supervised original honors projects of Gregor Feierabend and Gideo Joubert.
Gave a semester honors course on Logic.
Taught the English group of Engineering Mathematics 242 in the second semester of 2022.
Chaired the third Council Meeting of the South African Mathematical Society (7 October).
Hosted research visit (20 September - 8 October) of my PhD student, Noluntu Baart, to work on deductive reasoning in intermediate-phase mathematics education.
Hosted research visit (9 October - 9 December) of my PhD student, Kishan Dayaram, to make progress on three joint papers.
Hosted research visit (9-26 October) of Dr. Partha Pratim Ghosh. Joint work on canonical extensions started.
Rehearsed and prepared for the Fundamano production in a team of students. This is a theatrical production bringing mathematics on stage, celebrating the international year for basic sciences.
Drafted a paper based on the research on the category of near-vector spaces (co-authored with my MSc student, Daniella Moore, and the co-supervisor, Dr. Sophie Marques).
Gave a National Graduate Academy course on category theory. Click here for videos and lecture notes.
Gave a South African Theory School course on mathematical structures (jointly with Dr. Cerene Rathilal and Dr. Partha Pratim Ghosh). Click here for videos and lecture notes.
Spoke on "Is Maths Trauma a real thing?" at the radio show Weekend Breakfast with Refiloe Mpakanyane. Click here for the podcast.
July-August 2022
Organised a Research Workshop (5 July) on the occasion of visit (5 July) of Dr. Francois Schulz. Collaboration started on ranked monoids.
Organised a Research Workshop (14 July) on the occasion of the research visit of Prof. Dharmanand Baboolal and Dr. Cerene Rathilal. Collaboration started on metric frames.
Represented South Africa at the General Assembly of the International Mathematical Union (July 3-4, the report of the meeting is available here).
Gave a Foundations of Abstract Mathematics I seminar on arithmetic and proof composition.
Started research on the category of near-vector spaces (joint work with Dr. Sophie Marques and Daniella Moore).
Leading programme renewal discussions in Mathematics in the second semester of 2022.
May-June 2022
The paper on matrix taxonomy was published in Theory and Applications of Categories.
Hosted research visit (1-4 June) of Dr. Charles Msipha to advance progress on sum structures.
Continued research on a noetherian form of sets -- see the updated paper.
Chaired the second Council Meeting of the South African Mathematical Society (26 May).
Prepared an International Year for Basic Sciences for Sustainable Development project, which would later be called Fundamano. The project is listed on the official website of this international initiative. Dr. Charles Msipha and Dr. Sophie Marques are co-founders of the project.
Elected as a NITheCS Associate Representative. Duties include serving on the NITheCS Management Committee (meetings are held monthly).
Served on the programme committee of the international conference "Topology, algebra and categories in logic" held in Coimbra, Portugal.
March-April 2022
Revisited research on a noetherian form of sets (joint work with Dr. Francois van Niekerk).
Organised a Research Workshop on Monoidal Sum Structures at Stellenbosch University (20-25 March) and hosted the visit of Dr. Charles Msipha (Tshwane University of Technology). See the Mathematical Structures Research Programme website for further information. Two research projects dealing with sum structures were initiated at this workshop.
Organised a Research Workshop on Lower Topology at Stellenbosch University (3-10 April) and hosted the visit of Dr. Amartya Goswami and Ms. Micheala Hoenselaar (University of Johannesburg). A research project on lower topology was initiated at this workshop.
Supervised a 3rd year research project by Jean du Plessis (under Foundations of Abstract Mathematics II).
January-February 2022
Serving on the Subcommittee B of the Research Committee of Stellenbosch University for 2022.
Serving on the Programme Committee of the Faculty of Science of Stellenbosch University for 2022.
Setting up Mathematical Structures Research Programme at the National Institute for Theoretical and Computational Sciences, along with Prof. Yorick Hardy, Dr. Partha Pratim Ghosh, and Dr. Cerene Rathilal.
Teaching Engineering Mathematics 214 (together with Dr. Liam Baker, Dr. Ronalda Benjamin, and Dr. Michael Hoefnagel) in the first semester and giving a Foundations of Abstract Mathematics I seminar in Mathematical Reasoning in the first term. Also teaching a third-year module, Topology, in the first semester.
Convening Foundations of Abstract Mathematics I & II (year modules) and Topology (semester module) in 2022.
Started/resumed (co-)supervision of the following postgraduate students: Noluntu Baart (PhD), Roy Ferguson (MSc), Kishan Dayaram (PhD), Paul Hugo (PhD), Brandon Laing (PhD), Daniella Moore (MSc), Ineke van der Berg (PhD).
The paper on ordinal number systems appeared online in the Journal of Symbolic Logic (joint work with Ineke van der Berg).
Assumed the role of the President of the South African Mathematical Society for the term 2022-2023. Chaired the first Council meeting (11 Feb).
Under the research assistantship of Gregor Feierabend, the first prototype of a Haskell implementation of the SOFiA proof assistant was produced. See source code on GitHub or the live software.
The goal of this project is to build a proof assistant based on the SOFiA proof system, where the capital letters in SOFiA stands for Synaptic First Order Assembler (the purpose of the lower-case "i" will be explained further below). The use of terms "synapsis" and "assembler" is a suggestion of Brandon Laing, who wrote an MSc Thesis, "Sketching SOFiA" (2020), where the notion of an assembler was introduced: an assembler is the monoid of words in a given alphabet, seen as a monoidal category. The main result of his MSc Thesis was a characterization of assemblers using intrinsic properties of a monoidal category. An assembler gives a robust theoretical framework which guides the syntactical structure of the SOFiA proof system. The latter has been refined through a series of discussions with Louise Beyers and Gregor Feierabend in 2021, after which the first computer implementation of the SOFiA proof system was produced, based on the Python programming language. You can learn about it here. In January 2021, Gregor Feierabend developed a self-contained Haskell implementation, with user interface and documentation, which can be accessed here.
Overview of the SOFiA Proof System
The SOFiA proof system is an adaptation of the Fitch notation for natural deduction. The main novelty of the SOFiA proof system is the use of variables as statements, which leads to reducing quantified statements to implications. This allows unification of deduction rules for implication with those for the universal and existential quantifiers. The basic deduction rules for the proof system then are:
Making an assumption (no restrictions except that the assumption must be a valid SOFiA expression).
Restating an already stated SOFiA expression.
Recalling a theorem or an axiom, external to the proof.
Equating a stated SOFiA expression with itself.
Synapsis: stepping out of an assumption block (this allows to conclude quantified statements, as well as implications).
Application a SOFiA expression (this allows to conclude from quantified statements as a generalization of the modus ponens rule).
Substitution: substituting SOFiA expressions within each other based on already stated equalities.
These deduction rules do not include rules for disjunction or fallacy. The latter can be implemented as axiom schemes. So at its base, the SOFiA proof system embodies a bit less than intuitionistic logic. This is marked by the appearance of lower-case "i" in "SOFiA". Note however that because in the SOFiA syntax there is no distinction between "objects" and "statements about objects", the SOFiA proof system is not quite the same as the usual proof system of a first-order logic, although in a loose sense SOFiA does have the structure of a first-order language. One of the key differences with standard first-order languages is that in SOFiA one does not introduce additional relational or functional symbols. Instead, one may write any sequence of allowed characters in SOFiA which can be given the intended meaning of a relational or a functional symbol by means of axioms. Possibility for a sound and complete embedding of any first-order logic in SOFiA still needs to be proved and is currently one of the founding themes of PhD research by Brandon Laing.
Developing the Proof Assistant
The current version(s) of the SOFiA proof assistant have the following shortcomings, which are to be addressed in the near future:
The proofs can only be built line-by-line, it is currently not possible for the computer to fill the missing lines. This applies to both the Python and Haskell implementations.
The Python implementation source code is messy and there is currently no documentation.
The Haskell implementation contains bugs.
There Python implementation does not have a user interface.
Python and Haskell implementations come with modules for Boolean Logic and Peano Arithmetic, but they do not yet come with a module for Set Theory.
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?
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.
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?
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.
Matrix properties are a particular type of exactness properties that can be seen as category-theoretic analogues of linear Mal'tsev conditions in Universal Algebra. See this list for relevant papers in this research area.
The study of matrix properties led to the theory of "approximate operations" developed jointly with Dominique Bourn, and a general theory of exactness properties developed jointly with Pierre-Alain Jacqmin.
Work in progress on matrix properties:
Open problem on finding an algorithm for implication of basic matrix properties solved - see the working version of the preprint.
Even for binary matrices, the preorder of implications is quite complex. Some new results on this appear in this work in progress.
Python implementation of the algorithm for deducing implication of (basic) matrix properties can be found here. The program needs to be improved in some future.
Elected as the President of the South African Mathematical Society.
Papers on exactness properties published in Journal of Algebra and Advances in Mathematics.
Invited to give a plenary talk at the BRICS Mathematics Conference.
Secured funding for a national research programme in mathematics.
First computer implementation of the SOFiA proof system developed.
Supervised four postgraduate students (two PhD and two MSc).
Two papers on matrix properties submitted.
Served as the mathematical sciences programme coordinator and on a university research committee.
Taught and/or convened two semester modules and two year modules.
Progress made on existing and new research projects and delivered talks on those.
Carried out duties in the role as mathematical sciences programme coordinator and member of a university research committee.
Carried out refereeing and editorial duties (not listed below).
November-December 2021
Finalized marks for Foundations of Abstract Mathematics I, II and an honors module in Logic.
Resumed research on a noetherian form of sets.
The binary matrix properties paper submitted for publication (corresponding author: M. Hoefnagel) - see the submitted version of the paper here.
The revised version of the paper on matrix taxonomy re-submitted for publication (corresponding author: M. Hoefnagel) - see the new version here.
Talk given at SAMS Congress on the matrix project - see the write-up of the talk here.
At the SAMS AGM held during the congress, I was appointed to serve on the SAMS Council as the President of the South African Mathematical Society for 2022-2023.
Funding awarded for the NITheCS research programme in Mathematics, entitled "Space-like mathematical structures and related topics in algebra, logic and computation", which was expanded to include 20 mathematicians in South Africa.
Mathematical Sciences Programme tasks continued.
September-October 2021
Paper published: linear exactness properties in Journal of Algebra. See the paper on the journal's website here.
Some progress made on the SOFiA project, including implementation of an intuitive command-line proof building interface for sofia.py. Used this tool in the delivery of the Foundations of Abstract Mathematics I seminar in the fourth term.
The binary matrix properties paper finalized from my side.
Worked on the revision of the matrix taxonomy paper. Revision in progress can be found here.
Together with Amartya Goswami, gave a NITheCSmini-school (October 2021) on Elementary Introduction to Category Theory. See this blog for the write-up and links to video-recordings of lectures.
Talk given at SIC on forms vs monoidal categories. See the write-up and the recording of the talk here. See the recordings of all talks here.
Examiners nominated for the MSc Thesis of Paul Hugo, to be finalized by the end of the year.
Developed a NITheCS national programme in Mathematics for 2022, under collaboration with Amartya Goswami, Partha Pratim Ghosh and Yorick Hardy.
July-August 2021
Further progress made on the binary matrix properties paper.
Started writing a book in abstract algebra jointly with Amartya Goswami. You can follow the progress here.
Started work on some tasks related to the Mathematical Sciences Programme.
Teaching Foundations of Abstract Mathematics II in the third term and honor module in Logic in the second semester.
Started sketching ideas for a NITheCS national programme in Mathematics for 2022.
May-June 2021
The paper on linear exactness properties, joint work with Pierre-Alain Jacqmin, was accepted for publication in Journal of Algebra (it is scheduled for publication in October 2021 - follow the link).
Started (co-)supervision of PhD studies of Brandon Laing on SOFiA.
Started supervision of PhD studies of Ineke van der Berg on categorical algebra of algebraic logic.
Started a new research project on applications of forms to physics.
Continued with the teaching of Engineering Mathematics 214 and Set Theory and Topology.
Busy with marking of Foundations of Abstract Mathematics I first term seminar final assignments.
March-April 2021
Started work on matches of digraphs: pioneering joint work with Francois van Niekerk and Jade Viljoen (research grew out from her honors project).
Started work on binary matrix properties: joint work with Michael Hoefnagel, Pierre-Alain Jacqmin and Emil van der Walt (undergraduate student) on the structure of the poset of matrix properties. The project grew out from Emil solving problems that Michael and I suggested to him in the fall of 2021, which naturally evolved from a joint work with Michael and Pierre-Alain.
Made some progress with SOFiA: joint work with Louise Beyers, Gregor Feierabend and Brandon Laing. First python implementation of the SOFiA proof system produced. As a result, its deduction rules were refined.
Started supervision of MSc studies of Daniella Moore on categorical aspects of near-vector spaces (cosupervised by Karin Howell).
Teaching Engineering Mathematics 214 (together with Liam Baker, Ronalda Benjamin, and Michael Hoefnagel) in the first semester and giving a Foundations of Abstract Mathematics I seminar in Mathematical Reasoning in the first term. Also teaching an honors module, Set Theory and Topology, in the first semester.
January-February 2021
The paper on stability of exactness properties under pro-completion, a 7 year old joint work with Pierre-Alain Jacqmin, was published in Advances in Mathematics.
The paper on matrix taxonomy has been submitted for publication.
Revisited research on a noetherian form of sets: together with Francois van Niekerk, we are elaborating the proof of our recent theorem that the category of sets provides a model for the self-dual axiomatic setup for homomorphism theorems proposed in my publication no. 35. Significant progress was made with the corresponding paper, but it still needs to more work.
Serving on the Subcommittee B of the Research Committee of Stellenbosch University for 2021, as well as on the Programme Committee of the Faculty of Science.
