# Specializing in Logic in the Master Mathematical Sciences

## Prerequisites for a Logic specialization

If you want to study Logic as part of a Master's program in Mathematics, you need to be admitted to this program; see here for details. Usually, you will have completed a Bachelor in Mathematics. We assume that you have followed at least one introductory course in Logic, such as the course Foundations of Mathematics offered at this Department. You can get an idea of the contents of this course here.
In addition it is helpful if you have done some abstract algebra and topology during your Bachelor.

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.

## What is Logic?

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

## Which are the important topics in Logic?

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.

Back to Contents

## Which courses are available?

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

## Who are the teachers?

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

## Themes for research and theses

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?

Back to Contents

## Further perspectives

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 Contents

Back to my teaching page