Lecturers: Raymond Russell and Fergal Toomey
Date: 1998-99
Groups: Optional JS and SS Mathematics, SS Two-subject Moderatorship
Prerequisites: The course will be largely self-contained, but a familiarity with basic algebra (111) and point-set topology (212) would be an advantage.
Duration: 21 weeks
Lectures per week: 3
Examinations: One 3-hour examination
Order theory is a fascinating and very natural subject which affords a unified perspective on many areas in mathematics. It is still an active area of research (as evidenced by the work of the ALAPEDES group on max-plus operators) and the course will cover some recent results as well as the classic work of Birkhoff.
The basic concept in order theory is that of a partial order; it formalises the notion of a hierarchy and it appears everywhere in mathematics. The canonical example of a partial order is the subset relation in a collection of subset of a given set, such as the collection of open sets in a topological space.
Of central importance in order theory are functions from one partially ordered set to another which preserve the order. They are known as isotone functions and their role is entirely analogous to that of continuous functions in topology, or group homomorphisms in group theory. This course will focus largely on Galois connections, also known as adjunctions; these are pairs of isotone functions between two partially ordered sets which are almost inverses of each other. They provide a good illustration of order theoretic methods: it is easy to identify Galois connections, it is easy to prove useful results about them, and, most importantly of all, Galois connections exist in great profusion in mathematics.
Galois connections which are linear with respect to a suitably defined semigroup operation arise naturally in several areas of theoretical computer science and operations research, such as automata theory, the theory of discrete event dynamical systems, and optimisation theory. For example the dynamical behaviour of a multi-processor computing system may be described using a set of linear Galois connections. In this area, the interplay between order-theoretic and algebraic properties leads to powerful results, providing analogues of the classical theorems of linear algebra.
Course structure:
The course falls into two parts of roughly equal length.
The first will be an introduction to the notation and concepts (such as suprema and infima, lattices, join- and meet-homomorphisms, the well-below relation, and Galois connections) of order theory, with many simple motivating examples and counter-examples. The basic results of order theory will be presented, including the main theorems on Galois connections and the important topological properties of partially ordered sets and isotone functions.
In the second part of the course we will introduce Galois connections which are linear, in an appropriate sense, with respect to an operation of scalar multiplication. The basic representation and spectral theorems for these mappings will be presented, along with their implications for finite-state automata, discrete event systems, and optimisation theory.
Books:
Garrett Birkhoff, Lattice theory, AMS Colloquim Publications.
B.A. Davey and H.A. Priestly,
Introduction to Lattices and order, Cambridge University Press.