School of Mathematics School of Mathematics
Course 371 - Computability, logic, and set theory 2004-05 (JS & SS Mathematics )
Lecturer: Dr. C. Ó Dúnlaing
Requirements/prerequisites: None

Duration: 21 weeks (54 lectures + tutorials)

Number of lectures per week: 3

Assessment: Regular homeworks and final exam

End-of-year Examination: One 3-hour examination - end of year

Description: Peano Arithmetic - axioms for N. Resolution principle for propositional logic. Complete axiom system for propositional logic. Predicate logic, models, and completeness. Axioms for equality.

Turing machines and partial recursive functions. Peano arithmetic and Goedel numbering. Goedel's first incompleteness theorem. Goedel-Rosser theorem Hilbert-Bernays derivability conditions. Goedel's second incompleteness theorem. Further analysis of Goedel's second theorem. Goedel's First theorem and partial recursive functions.

ZF set theory. Ordinals. Foundation axiom and its relative consistency. Cardinals, the Axiom of choice, and the General Continuum Hypothesis. The constructible universe. Relative consistency of V=L. V=L implies AC. V=L implies GCH.

Additional notes. A considerable advance in nineteenth-century mathematics was the introduction of rigour to suspect areas of analysis. The notion of `real number,' for example, can now be defined in terms of Cauchy sequence or Dedekind cut. Both of these are generally acceptable reductions of the intuitive continuum of real numbers to sets of sets or sequences of rational numbers.

So, if one can formalise the notion of `set' in logically unobjectionable terms, one can be happy with much of advanced mathematics.

However, the development of set-theory uncovered paradoxes such as Russell's: { x \colon x x } both belongs to itself and doesn't. Mathematicians such as Hilbert aspired to formal axiom systems which could be themselves formally proved free of paradox.

Their idea was as follows: since a formal system should be a precisely-defined combinatorial object, the consistency of such a system should be expressible in precise combinatorial terms and hopefully capable of a rigid demonstration - even though the system itself should speak of shadowy notions of infinite cardinality, and so forth.

The most basic problem would have been the formalisation of number theory. Once that was done properly, the consistency of other formal systems would hopefully be translated into theorems about numbers, and hence settled by the theory. What was wanted, therefore, was a mechanical procedure for establishing facts about the natural number system N. One required (a) a complete system of axioms for N, so every fact about N would be a theorem of the system; and (b) a demonstration within this system that the system was consistent, that is, every theorem would hold true for N. The course is largely concerned with progress towards these goals for number theory and then for set theory.

The course begins with Peano's axioms, an axiom system for the natural numbers. This is an introduction to an important formal theory.

It then covers classical first-order logic, introducing a variant of the `Principia' system, introducing semantics through Tarski's definition of satisfaction, and going on to Gödel's Completeness Theorem, which says that every consistent first-order theory has a model (or conversely, if a theory cannot be realised, then one can derive a contradiction in the theory).

The course will then deal with Gödel's negative contributions to Hilbert's program. His first incompleteness theorem, which says that no recursive axiomatisation of number theory covers all true facts about numbers. His second incompleteness theorem, which says that no consistent recursive extension of Peano arithmetic allows a proof of its consistency.

The course then turns to set theory. The Zermelo-Fraenkel theory will be studied. Its axioms are mostly common set-theory, such as extensionality, existence of set unions, and so on.

The most interesting feature of set theory is the Axiom of Choice: one formulation of this axiom is that every surjective function has a right inverse. (The proposition that every injective function has a left inverse is much weaker.) It is used for (and is equivalent to) many other `big existence' theorems, such as the Hahn-Banach Theorem, the existence of (algebraic) bases for vector spaces, comparability of set cardinalities, existence of ultrafilters, Tychonoff's theorem, and so on. A strange construction made possible by the choice axiom is a non-measurable set of real numbers, by expressing the unit interval as a countable disjoint union of equi-measurable sets.

The other problem of set theory was the Continuum problem: do there exist uncountable sets of R whose cardinality is less than that of R? Although not as central as the axiom of choice, this problem obviously begs a solution within set-theory.

Given that the Axiom of choice leads to important or sometimes strange results, one first asks whether it can be deduced from the other axioms, or whether it is independent, and, in the latter case, is it also consistent? We shall answer the second question, but not the first.

We will show the relative consistency of the axiom of choice. That is, although one does not expect a proof of the consistency of set theory (ruled out by Gödel's second theorem), nonetheless one can show that assumption of the choice axiom cannot introduce contradictions that were not already there. This makes the formidable choice axiom much easier to swallow. This result is also due to Gödel. The details are complex, as in most areas of logic, whereas the principle is quite simple, and similar to showing that if groups exist then commutative groups exist. In Gödel's method one would take a model of set theory (much harder to describe than a group) and produce a submodel, `the constructible universe,' in which the axiom of choice holds. It will turn out also that the Continuum hypothesis holds within the constructible universe, so it also is consistent with the other axioms of set theory.

Further developments. The material covered in the course was mostly developed in the 30s. Since 1940 the outstanding development in set-theory was Cohen's forcing method (1963), which time does not allow us to cover. This led to full independence proofs for the Continuum hypothesis and the axiom of choice. A very strange application of forcing showed that the existence of nonmeasurable sets, which follows from the Axiom of Choice, is very close to that axiom.

Another interesting development was in number theory, where a `definitely true and natural' fact about numbers was shown to be independent of Peano arithmetic. Put another way, a certain sequence sn of numbers (strong Ramsey numbers) is obviously computable - indeed, a Turing machine could be produced on demand, which computes any member of the sequence - except that Peano arithmetic isn't sufficiently comprehensive to demonstrate this `obvious' fact.

Another area which the course cannot pursue is the development of mechanical proof-procedures, such as (first-order) resolution, or decision procedures for specific theories, such as Tarski's theory of the real numbers. However, the course should stop just short of these, and you would be able to continue with them if you so wished.

Jun 12, 2004

File translated from TEX by TTH, version 2.70.
On 12 Jun 2004, 21:14.