An online database of classes of algebraic structures

Peter Jipsen

Chapman University, CA

ASL 2003 Annual Meeting, June 1-4, 2003

A currently ongoing research project is the construction of a web database of classes of mathematical structures.

The aim of this project is to make basic information about mathematical structures available in a uniform and extendible way, with direct connections to computational tools and decision procedures for these structures.

The problem

Two examples that influenced this project

A look at the current version of the database

Conclusion

The problem

Many classes of mathematical structures have been investigated in the last century.

Even if we restrict to classes related to algebraic logic, there are still over 100 classes that have been defined and analyzed in some detail.

Universal algebra, model theory and category theory have been developed to express general properties and analyze relations between classes of mathematical structures.

But the information known about individual classes of structures is still much greater than what is covered by general results in universal algebra, logic or category theory.

Classes of mathematical structures can be defined in several different ways, e.g. by

1) specifying a list of properties that they must satisfy, often expressed as formulas of (first-order) logic, or

2) specifying a generating class of algebras and a closure operator (e.g. HSP)

It can be nontrivial to determine whether a general result applies to a specific class.

Especially for researchers who are working in other areas, it is often difficult to assess whether a particular class of structures (or a closely related one) has already been examined in detail in a different context.

The aim of this online database of mathematical structures is to address the problem by providing broad coverage of the many classes of structures that have been investigated in the literature.

The aim is not to concentrate only on the major classes, but to include basic information also on specialized less well-known structures.

How can such a database be constructed?

Two examples that influenced this project

Exhibit A: http://www.wikipedia.org a free online encyclopedia

three years in the making (so far)

over 100000 up-to-date entries, including reliable information about general mathematical research topics

designed collaboratively on a Wiki server platform

no copyright; material can be freely copied

very low development cost; surprisingly high quality

Exhibit B: Neil Sloane's Encylopedia of integer sequences

sequences collected by N. Sloane over the past few decades

over 60000 sequences (mostly initial segments) related to mathematical structures

rigid format for entries

some computational tools and search tools for finding related sequences

used by many researchers on a daily basis

new entries submitted by email (moderated)

There are several other databases, e.g. Wolfram's Mathworld, PlanetMath.org,...

These resources are designed for humans to read. They are extensive, high quality, up-to-date, freely available, and getting better all the time.

The current mathematical structures database project is situated somewhere between Sloane's integer sequences (which give some invariants for classes of mathematical structures) and Mathworld or Wikipedia.

An emphasis is on making data easily available to software that computes further mathematical information about the classes.

Several researchers have used computers for calculations on finite algebras, e.g. C. Bergman, J. Berman, S. Burris, S. Comer, R. Freese, E. Kiss, E. Lukacs, R. Maddux, M. Maroti, J.B. Nation, S. Tschantz, M. Valeriote, ...

This database aims to make the results of such calculations easily accessible.

Initially, each class of structures has a webpage in the database containing (some of) the following items:

Name
Abbreviation
Definition (usually several equivalent ones)
Description of the morphisms
Standard examples
Basic results (or references to the literature)
List of relevant properties (with values and references)
Information on free objects, injective, projectives, etc.
List of some (finite) members of the class, possibly with some graphical representations
List of subclasses (or subcategories)
List of superclasses (or supercategories)

Syntactic aspects: A format for specifying axioms (to be extended to theorems and proofs)

Currently based on TeX+XML, to be converted to MathML

Semantic aspects: An XML definition for finite structures (to be extended to automatic structures and finitely presented structures)

Algebraic logic: Linking algebraic and logical viewpoints.

But first: What is XML (eXtensible Markup Language)?

A (tree) structured, human and machine readable, extensible, platform independent data format.

Easy to understand; e.g. many students know it because HTML is a relaxed form of XML.

Well suited for mathematical expressions and structures (e.g. MathML is a developing XML standard)

E.g. here is an XML description of a 3-element poset:

<structure name="Poset_3_4" size="3">
  <element id="0" x="1" y="0"/>
  <element id="1" x="0" y="1"/>
  <element id="2" x="2" y="1"/>
  <relation name="uppercovers" arity="2" type="list">
    <set id="0"> 1 2 </set>
    <set id="1"> </set>
    <set id="2"> </set>
  </relation>
</structure>

Design guidelines for the database:

Natural syntax (modelled on mathematical practice)
Collaborative development style
Accessible algorithms (open architecture)
Interactive diagrams
Interactive diagrams
Extensible
Platform independent
Useable as a teaching/learning tool

For this presentation we will briefly consider the following algebraic structures

Kleene algebras
action algebras
residuated lattices
Boolean semigroups

So how does it look at the moment?

Go to math.chapman.edu/structures

(or search for Mathematical Structures Homepage)

To do:

Standardize the XML format for finite structures, write a DTD.

Design an XML format for declarative mathematical proofs based on the defacto syntax of mathematics (e.g. set theory + TeX).

Provide simple tools for proof checking and proof generation.

A format for finitely presented algebras, partial algebras, multi-sorted algebras.

Better webdesign, MathML support, TeX output.

More graphical representations of algebras (e.g. Cayley graphs).

Add more classes, references and results to the database (without duplicating efforts of other webdatabases).

Conclusion

The database project is still developing, but it is already useful.

There are a number of new ideas implemented in it that are not found in other online resources:

platform independent format for mathematical structures
direct support for simple algorithms
interactive graphical support
collaborative development style.

It represents a form of instant peer-reviewed anonymous publishing.

Motto: Every class of mathematical structures that has been investigated (has some publications) deserves a presence on the web.

As the database becomes more complete, the interesting gaps in it will be more obvious.

This project will not be finished at some stage. If it succeeds, it will continue to evolve and remain up to date.

Think big. --- Some things are surprisingly easy nowadays.

Storage space is not a problems. It's like the wild west all over again.

If you are happily farming on a little plot in New Jersey, watch out, there are other subjects that a claiming the huge midwestern storage plains, and they gain intrinsic status by being able to manage big databases.

I'm not advocating that we produce huge amounts of worthless data --- mathematics has many legitimate reasons for generating lots of useful data. E.g. lists of finite structures can be a good source of conjectures and counterexamples.

I hope you are upset that your favorite category or class of structures is not mentioned or has very little information in the database so far.

This makes it more likely that someone will add it.

It only takes half an hour to make a significant contribution.

So encourage your students to do it.

How often do we find annoying little errors in papers or on webpages?

Here you can fix them immediately.

The database will remain freely accessible. Anyone can get a complete copy.

math.chapman.edu/structures

(or search for Mathematical Structures Homepage, or my homepage on the web)

ASL talk