Contents of this page:
The courses are, however, open to students from other curricula too, and could be interesting to people from AI, Computer Science, Philosophy, and Physics. Consult your own master program advisor about incorporating our courses into your program.
The area of Mathematics called Logic has two dominating themes: Proving and Computing.
A mathematician often works with axioms, from which he proves theorems. This process
is analyzed (in an abstract way) in Logic. One starts by introducing a formal language, in which
mathematical statements can be written down: with variables, logical symbols for "and", "or", "not",
quantifiers "there is" and "for all", and special symbols for specific elements, operations or
relations that may differ from situation to situation.
The "statements" of this formal language can be interpreted in "real" mathematical structures, and
are then "true" or "false"; for example, the statement "2 is a square" is true in R, but false in Q.
A "formal proof" is a structured collection of formal statements, in such a way that it is
immediately clear what the conclusion is, what the premisses are and how each intermediate statement
follows from previously reached conclusions.
The most important theorem (Gödel's "Completeness Theorem"; not to be confused with his
"Incompleteness Theorems") says, that a formal statement occurs as the conclusion of a proof, precisely
when this statement is true in every possible interpretation.
This point of view enables us sometimes to prove, that for certain mathematical statements no proof can exist.
For instance the so-called "Continuum hypothesis" by Cantor, which says that every subset
of R is either countable, or in 1-1 correspondence with R itself. It has been proved that this
statement cannot be proved from the usual set of axioms for mathematics (see the paragraph on
Set Theory below. That doesn't make it false, because its negation cannot be proved
either!
During the Bachelor course "Foundations of Mathematics" you have been made familiar with the concepts of formal language, interpretation and formal proof.
The second theme, computing, is about the question: for which sort of decision problems in
mathematics can one devise an algorithm by which a computer can always give the right answer? To give
an example: suppose a convergent sequence of rational numbers is given to us, together with information
about how fast the sequence converges. We want to determine whether the limit of this sequence is a
real number less than zero or greater than or equal to zero. The computer is allowed to successively
read a next element of the sequence, and compute with all elements obtained so far (as well as with the
rate of convergence). There is no program which always, in finite time, gives the right answer!
Starting from a formal definition of "algorithm", we get to the notion of "computable function": a
computable function from N to N (or from Z to Z) is a function for which there exists such an
algorithm.
An important theorem is about the image of such a computable function. We call a set of
k-tuples of elements of Z algebraic if it is the set of zeroes of a polynomial in k variables
with coefficients from Z. Matyasevic' theorem says: a subset of Z is the image of a computable
function, precisely if it is the projection of an algebraic set of k-tuples (for certain k). This
theorem allows one to show that there can be no algorithm for deciding whether a given polynomial with
integer coefficients, has integer zeroes.
Back to Contents
You have, we assume, followed the Foundations of Mathematics course. This should give you already an
idea of whether Logic is something for you.
Logic seems, generally speaking, to appeal to students with a philosophical bent, as well as to
those who are attracted to topics like abstract algebra.
It is rather abstract in character, and most applications of Logic (in Mathematics or beyond) are
of a theoretical nature. It
is also rather more combinatorial than conceptual: in many instances, Logic deals with the finite and discrete.
Well, just try!
Back to Contents
The most important topics are Model Theory, Recursion Theory, Set Theory and Proof Theory.
Model Theory, to which Chapter 2 of the Foundations course offers an introduction, explores
logical theories from the point of view of their classes of models. An introduction can be accessed
from my teaching page.
As an example of studying logical theories from the point of view of the models, there is the theorem
which says that the class of models of a theory T is closed under directed colimits, precisely
if the theory has a set of axioms of the form "for all x there exists a y", followed by a quantifier-free
formula.
A more sophisticated example concerns quantifier elimination. Suppose that we are
talking about rings; so we have symbols for addition and multiplication, as well as for special
elements 0 and 1. Given a ring R,
we can define certain subsets of R, using only the given symbols and the logical operations.
For example if R is the ring of real numbers, we can define the subset of non-negative real numbers
since this is exactly the set of squares. If R is the ring of integers, the set of non-negative
elements is also definable since by Lagrange's theorem this is the set of sums of four squares.
We say that a ring R has quantifier elimination if every subset which is definable in this way,
can also be defined without quantifiers. Because the formula "x is a square" contains a quantifier
("there exists a y such that x=yy"), the ring of real numbers does not have quantifier elimination.
But the ring C of complex numbers has. This is not a coincidence. The following general theorem holds:
An infinite ring without zero divisors has quantifier elimination, precisely when it is an algebraically
closed field (the right to left implication here is a famous result by Alfred Tarski;
the converse was proved by a.o. the ex-Utrecht logician Lou van den Dries).
Recursion Theory elaborates the "computing" theme sketched above.
Now an abstract computing machine is defined, and a precise meaning is given to the notions of a
program for this machine, and a computation. A computable function is a function f for which
there exists a program P which produces, for every input x, a computation with outcome f(x).
The theory of computable functions leads to some original and, at places, a bit eccentric mathematics.
However it is of paramount importance for Logic, and it occurs in every other branch of the field.
Moreover, the abstract computing machine paradigm, discovered years before the invention of the transistor
which made digital computers possible, is central in theoretical Computer Science. It allows an analysis
of computations in terms of amount of time (computation steps) and space (memory bits) consumed, and from
this a stratification of number-theoretic functions in so-called complexity classes. A famous problem
in this area is the P=NP?-problem, which is still open. Research on this problem has revealed interesting
connections with mainstream mathematics. The problem is on the
Clay Mathematics Institute's list of Millennium Problems, and a solution is rewarded with a million
dollars.
Set Theory is the investigation of the axiom system of Zermelo-Fraenkel, ZF.
This axiom system is accepted by most mathematicians as the foundation of their subject: every mathematical
object can be regarded as a set. When learning set theory, one learns how to use the axioms in order to build
up the mathematical objects as sets, and how to reason about them.
The model theory of ZF is
quite delicate, because Gödel's Incompleteness Theorems imply that one cannot, by using mainstream
mathematical methods, construct models for this theory. An ingenious way out was discovered by Paul Cohen
in the early sixties of the past century, when he found the "forcing method". With the help of this he was
able to show that the Continuum Hypothesis is not a consequence of the Zermelo-Fraenkel axioms.
Gödel's famous Incompleteness Theorems, already alluded to above, are part of the study of
Proof Theory. Roughly, the Incompleteness Theorems say that no consistent set of axioms suffices to
show that ordinary mathematics is free from contradiction.
But Proof Theory has a wider scope. Basically, this subject studies the combinatorial properties
of proof trees. By a celebrated result of Gentzen, such trees can always be calibrated to a specific
normal form. Using this normal form, one can often give a characterization of the functions
which can be defined in a given formal system.
An important topic in proof theory is "ordinal analysis", which aims to classify formal systems by
assigning so-called proof-theoretic ordinal numbers to them.
Another approach in the study of proofs stresses the way a proof tree can be seen as an information
flow system. A proof "acts" on the premises (hypotheses) which can be regarded as input data. This
"proofs as programs" point of view has led to applications, where actual algorithms are being extracted
from formal proof trees.
The teaching of Logic in the Master Mathematical Sciences is organized as follows. Every year in the first
semester (periods 1 and 2) there is a course "Advanced topics in Logic". In this course, two topics will
be treated in some depth. These may come from the list above, but there are other possibilities.
In the fall of 2005, the topics are Gödel Incompleteness and Model Theory.
The idea is, that
the topics will vary from year to year, so by following this course twice, the student gains knowledge of
four parts of Logic.
Apart from this course, in the second semester, a student seminar is organized. A student seminar means that students in turn study a section of material independently, and present it to the others. In the past, student seminars have been held on Intuitionism (see this page in Dutch), Algebraic results in Model Theory (page in Dutch), Proof Theory. In the spring of 2006, a student seminar will be held on Categorical Logic.
After having taken a number of these courses, you can then write a master thesis
under the guidance of one of the teachers.
Back to Contents
The teachers in Logic are Ieke Moerdijk and Jaap van Oosten. At the moment there is one PhD. student in Logic, Bram Arens.
Back to Contents
An important Utrecht specialism is Categorical Logic.
Category theory was invented by Eilenberg and MacLane around 1945. It provides an organization of
mathematical structures in which, rather than sets with elements, the notion of function (also
called map, or morphism) is central.
A category consists of a collection of objects and a collection of morphisms; each morphism "goes"
from one object to another. Morphisms can be composed, and this composition is
associative. Think of: sets and functions, groups and homomorphisms, topological spaces and
continuous maps.
It turns out that many set-theoretic properties can be expressed using only the language of maps and
composition. To give a very simple example: a function f:X->Y is injective precisely if for every two
maps g,h:Z->X it holds that whenever the compositions fg and fh:Z->Y are equal, then g=h.
Categorical logic pursues this point of view. It constructs definitions of set-theoretic concepts
(like the set of natural numbers, or the power set of a set) in the language of objects and maps, and
gives a very general notion of a model of a theory in a category. For example, a model of the theory
of groups in the category of topological spaces is a topological group (a topological space with a group structure
such that the group operations are continuous).
An important type of categories are topoi. A topos is a category in which most constructions
one can perform with sets (like, form the power set), are possible
; it is a "nonstandard universe of sets". However, the logic which governs these universes is
intuitionistic logic, where one is not allowed to use the principle of excluded third in arguments.
An example of a topos is the category of sheaves on a topological space. Another kind of topoi
have been defined using notions from Recursion Theory.
Topos Theory is also studied in theoretical Computer Science. Recently, there has even been
interest in topoi within theoretical physics.
A recent master thesis was about connections between topos theory and classical model theory.
Another recent master thesis is about nonstandard models of arithmetic. Peano Arithmetic is an axiom
system which aims to characterize basic algebraic properties of the natural numbers. However, there
are also nonstandard models of this theory, models in which there exist nonstandard, "infinitely big"
natural numbers.
Now suppose in such a nonstandard model M we consider a nonstandard prime number p. Since M satisfies the
axioms of elementary number theory, in M we can calculate "modulo p", and we get a field. This field has
characteristic 0. A question is then: which fields arise in this way? There are nice results which relate this
to the question which induction axioms are true in M.
Another pertinent question in this area is: how many induction axioms are necessary to prove that there
exist infinitely many primes?
A student who has completed a Master degree in Mathematical Sciences with specialization Logic has many possibilities. Usually, you have the same professional options as other graduates (with different specializations). If you are interested in research, you need not confine yourself to Mathematics departments: also Philosophy and Computer Science departments employ mathematicians and offer Ph.D. studentships for research in Logic. There are even possibilities in Linguistics!
Last but not least, a specialization in Logic may be interesting for students aiming for a career in teaching. I used to have a math teacher who told us, in 11th grade, about Cantor's diagonal method, Russell's paradox, and ordinal numbers, and I found this very exciting.
Back to my teaching page