Speaker: Dusko Pavlovic (UMH ICS)

Title: From Data Analysis to Dedekind-MacNeille Completions of Categories

Abstract: Solutions of mathematical problems are well-known to help with practical applications (to the point of being “unreasonably effective”, as Wigner put it). It is less well-known that practical applications sometimes help solving long standing mathematical problems. I will tell a story of this second kind.

The Dedekind-MacNeille completion of a poset is the smallest complete lattice that contains it, or equivalently the largest complete lattice where each element is both a meet and a join of the elements of the poset. Dedekind devised it to reconstruct the reals as a completion the rationals, and MacNeille generalized it to arbitrary posets. When posets are generalized to categories (so that the partial ordering a<b is expanded into the morphisms a->b), then meets and joins become limits and colimits, and the obvious task arises: generalize the Dedekind-MacNeille completion to categories. The task is thus to embed any given category into a category with all small limits and colimits, in such a way that any limits and colimits that already existed are preserved, and that any new objects that are added are both limits and colimits from the original category. This task was formulated already in the 50s, and it was listed as the most important open problem in Lambek’s 1966 “Completions of Categories” (volume #24 of Springer LNM). Stunningly, in 1972, Isbell proved that already the group Z_4, viewed as a one-object category, cannot be embedded into a bicomplete category where each object is both a limit and a colimit of diagrams built from copies of Z_4. But since the inductive process of adjoining limits to a category obviously settles at various bicompletions, and since it is easy to see that some of these bicompletions must be minimal, Isbell’s negative result just expanded the question: What are minimal bicompletions of categories, and which properties make them minimal? The question remained open for more than 40 years, or almost 60, depending how you count. 

In this talk I will sketch the answer at which we arrived in 2015. It emerged as a special case of a matrix bicompletion construction, developed in a data analysis project. In the meantime, the practical applications of the result have expanded, but some of the mathematical repercussions, and most of the algorithmic issues, have not been settled.