Information for prospective students
On this page, you can find brief and informal descriptions of my research subject, so that you can get an
idea of what I do. I also describe the courses which are offered by the logic group in the math department,
so that you can find out what types of subjects we teach here. Finally, I have some suggested research projects
for graduate students or summer students.
Category theory and Logic
What is category theory?
Category theory is a branch of pure mathematics which is concerned with abstract properties of structures
and mappings between them. Many people regard category theory in the first place as a language for mathematics,
or as a powerful organizational tool. It places strong emphasis on studying the mappings, or morphisms, between
mathematical objects rather than studying these objects in isolation. Thus instead of looking at, say, groups
we consider the category of groups, i.e. the groups and the homomorphisms of groups. Another typical feature of
category theory is that it often uses commutative diagrams to explain, emphasize or proof matters.
Category theory is in part useful because it allows for clean and conceptual statements and descriptions which
bring out the underlying structure.
A traditional example: when studying groups, you learn that a group is a
set with some additional structure on it. Similarly, a ring is a set with additional structure on it, as are
topological spaces, partial orderings, vector spaces, and so on. Category theory describes these situations by
saying that there is a "forgetful functor" from the category of groups (rings, spaces,...) to the category of sets.
What is more, given a set S we may construct the free group on that set; it is characterized up to isomorphism by
a universal property (given a function from S to another group it uniquely factors through the free group via a
group homomorphism). Similarly, one may construct the free ring on a set S, or the vector space with basis S, or
the discrete topological space on the set S, and so on. Each of these free constructions is expressed in categorical
terms by saying that the forgetful functor has a left adjoint.
Apart from being a concise formulation for stating the existence of a free construction, general results about
adjoint functors now allow us to conclude things about these free constructions without having to prove them for
groups, rings, spaces,... separately. For example, a well known general theorem from category theory says that
left adjoints preserve sums and right adjoints preserve products. In the instance of groups, this says that
the product of a family of groups has as its underlying set the product of the underlying sets. It also says
that the free group on the set S+T is the direct sum of the free groups on S and on T. Sometimes it is
said that such categorical results are not really mathematical results.
Well, that is part of the point: category theory tells us
which parts of mathematics are trivial for trivial reasons.
Categories and logic
However, category theory has more to it than this organizational function. It is also studied as a topic in its
own right, much in the same way as one might study, say, ring theory. There are deep and interesting connections
between category theory, topology and logic. Just to give a few pointers: categories serve as models for various kinds
of logic, ranging from equational logic (used to describe algebraic structures), first order logic (the kind studied
in traditional mathematical logic), higher order logic, intuitionistic logic (where we avoid the law of the excluded
middle) and even other kinds such as linear logic.
Conversely, one may think of certain categories (called toposes)
as universes of mathematics: their objects are set-like, and their morphisms are function-like, but the logic which
governs them is not classical. Typically the axiom of choice is not true, the logic is not classical (excluded middle
fails) and there may be more than two, even infinitely many truth-values. In spite of this different logic,
we may still develop mathematics inside such a category. For example, this can be used
to provide settings for non-standard analysis and differential geometry.
Categories and topology
Categories are also closely related to topology. One facet of this relation is the fact that to every space
X we may associate a category Sh(X) of sheaves on X. The category Sh(X) is where topology and logic meet: we can
use it to study X using logical techniques, or we can use spaces to find interesting models of certain logical
theories. For example, sheaf models have been used to give elegant proofs of milestone results in mathematical logic,
such as the independence of the continuum hypothesis.
Homotopy theory is also heavily involved in category theory, in at least two ways. First,
just as in topology one studies not just spaces, continuous maps and homotopies, one also considers higher homotopies:
these are homotopies between homotopies between homotopies... and so on. A similar thing happens in category theory:
instead of just looking at objects and morphisms, one can consider morphisms between morphisms between morphisms... .
Such higher-dimensional structures are called higher categories, and it is not hard to imagine that understanding those
would be very useful for homotopy, and vice versa.
In addition, there is a class of categories called Quillen model categories, which aim at abstracting away from
the stretchable rubber you learned spaces are made of. The result is a setting which allows for many of the constructions
available in homotopy theory, but in a "neutral" category. One of the big advantages is that this gives us
ways of comparing different models of homotopy, by looking at how the resulting model categories relate.
In addition, category theory and logic are heavily used in theoretical computer science
and mathematical physics.
Why study category theory?
Even if you're not planning on doing research directly in these areas,
you will benefit greatly from understanding the basics: it will help you
see the relevant structural features of whatever area you're studying more clearly,
help you ask the right kind of questions and help you understand which results are
a consequence of general structural considerations and which are more specific in nature.
In other words, learning some category theory is an excellent way of mastering some of
valuable skills needed to become a successful researcher in pure mathematics!
Courses
Every year the logic group in Ottawa offers courses in these areas both on the undergraduate and
on the graduate level. In addition to the courses listed below, we sometimes offer directed study
courses or seminars. Here's a list of all the courses we offer,
with an explanation of what you can expect to learn in them.
-
MAT2362: Foundations of Mathematics. This course used to be a pure logic course, but is now a course intended for
all mathematics students. The main purpose is that students aqcuire the skills and tools to safely handle the more
abstract mathematics of the 2nd year. To this end, we study the fundamental structures used in all of mathematics,
such as functions and relations, and we learn various proof techniques. In addition, new concepts, such as the
cardinality of a set, are introduced. For example, you will learn what we really mean when we
say that the set of real numbers is bigger than the set of rational numbers and you will learn how to prove this
famous result, known as Cantor's diagonal argument.
-
MAT3361: Introduction to Mathematical Logic. This is the first serious logic course in the sequence! You will
get a thorough introduction to propositional and predicate logic and their formal proof theory. You will
also learn the notion of a model of a theory, and study two of the cornerstones of mathematical logic, namely
the completeness theorem and the compactness theorem. The former says that any consistent theory has a model;
moreover, this model can be constructed using the syntax of the theory. The compactness theorem tells us that
if we have a collection of axioms and if every finite subcollection of those is consistent, then the whole
collection is consistent. This powerful result has lots of interesting applications in various areas. For
example, it can be used to construct models of non-standard analysis, in which there exist infinitesimally small
elements. Depending on student interest, some other topics will be covered, such as constructive mathematics,
modal logic or formal set theory.
-
MAT4161: Mathematical Logic This course first reviews some of the concepts of mathematical logic, and then
explores several more advanced topics. The highlight of this course is the proof of Goedel's famous result
from 1931, the Incompleteness Theorem. Intuitively, this result says that if you have a formal system which
possesses a certain minimum of expressive power (for example, first order arithmetic will do, but much weaker systems
work as well) then such a system is necessarily incomplete. This means that there exist sentences (called Goedel
sentences) which are neither provable nor refutable in the system. One way of constructing such a sentence is
by encoding in a suitable manner the Liar's paradox, by creating a sentence which says "I am not provable".
-
MAT4162: Topics in Mathematical Logic. The contents of this course vary from year to year, depending on who is
teaching it and on student interest. For example, when I taught this course in the Spring of 2009, we
explored the basics of categorical logic.
- MAT5147: Category Theory and Homological Algebra. This course introduces two very powerful tools
for pure mathematicians. We begin by studying the basic concepts of category theory such as categories,
functors, limits, adjunctions and the Yoneda Lemma. After that, we investigate categories which are of
particular importance to algebra, namely categories of modules, chain complexes and, more generally,
abelian categories. Finally, we explore the fundamental concepts and results of homological algebra:
projective and injective objects, resolutions, homology and cohomology, derived functors,
ext and tor. After this course
you will have the tools and skills to use these in your own research, and the foundation to study more
advanced texts on the subject independently.
-
MAT5161: Mathematical Logic. This is a classic graduate course in traditional mathematical logic,
covering the essentials from all four pillars of mathematical logic, namely model theory, set theory, proof
theory and recursion theory.
-
MAT5162: Mathematical Foundations of Computer Science. How do you prove that a computer program does
never crash? How do you know it will even compile properly? And even if it works the way you want it to,
how efficient is it? Questions like these are the main motivation behind the theory explored in this course.
One of the important case studies is the typed lambda calculus, a logical framework which lies at the basis
of a class of programming languages called functional languages. We study various phenomena in this framework,
ranging from normalization (will computations halt?) and type-checking to various kinds of semantics.
- MAT5361: Topics in Mathematical Logic. The contents of this course vary from year to year. Last time
I taught this course it was a traditional course in recursion theory.
Thesis projects
If you are interested in doing a summer project, an undergraduate thesis, an MSc or a PhD in a topic related
to logic, category theory or mathematical physics, there are plenty of opportunities here in Ottawa.
Our group is one of the main centers of category theory in North America, with three researchers (Prof. Blute,
Prof. Scott and myself) working in the area and several others working in neighbouring areas.
We are always looking for motivated new students and we'd be happy to answer any further questions you may have!
Examples of possible projects
Below I list a few possibilities, with brief descriptions. Also check out
the pages of my colleagues in the
logic group to see what projects they work on!
- Game theory: Game theory (roughly defined as: the study of strategic interactino)
is officially part of applied mathematics: it is widely used in economics, biology, and political science. However,
it also has close ties to logic and computer science. For example, one can understand the process of proving
a logical formula as a game between two players, one of whom tries to establish the truth of the formula and
one who tries to frustrate this process. (The formula is then a tautology iff the first player has a winning strategy.)
On the one hand, games have been used to model various kinds of logic and programming languages; on the other hand
logics have been developed to study the type of reasoning needed to analyse (the behavior of agents in) games.
Currently I'm interested in alternative formulations of games and solution concepts (such as Nash equilibria).
I have various possible projects ranging from the study of particular games to the extension of
new viewpoints to larger classes of games.
If you want to do a research project (UROP, USRA, Work-Study, graduate or simply a research assistantship)
on this come talk to me!
- Abstract computability: the aim of this research programme is to study computability using the
tools of category theory. The central concept is that of a Turing category: this is a category
which supports the bare essentials for developing computability theory.
There is still a lot of work to be done in this area, and so there are many options for projects. For example,
various concepts and results from classical computability theory
are still to be studied in this setting. If you're more interested in the recursion theory side, then it would
be nice to study how several basic results about computable (recursive) and r.e. sets generalize to this
setting. If you like pure category theory or categorical logic better, then you could investigate various
interesting classes of partial map categories; this would support the study of special kinds of Turing categories,
but would also be of independent interest in other branches of computer science.
- Partial combinatory algebras: these are awkward but fascinating structures which are supposed to embody
a notion of computation. PCAs are used in several places in logic and computer science, but unfortunately
we don't have a very good understanding of their structural properties. Investigating new examples, new
constructions or studying possible generalizations would all make for interesting and challenging projects.
- Semigroups, groupoids and toposes: An inverse semigroup is an algebraic structure slightly weaker than
a group. Informally, just as groups describe symmetries of objects, inverse semigroups describe partial, or local,
symmetries. It turns out that there are close connections with the theory of groupoids (categories in which every
morphism is invertible) and with toposes (categories of sheaves). My main interest is in uncovering the
categorical structures and techniques needed to understand certain phenomena in semigroup theory. Some of the
projects here would involve mostly pure category theory, while others would involve a fair bit of topology
and locale theory (pointless topology).