Mathematical Logic

Requisites

Additional Requirements

Students need to have seen an introduction to Predicate Logic (as for example taught in the last chapter of MATH20302 Introduction to Logic).  Please also see the module's coure material link.

Level 4 modules that require Mathematical Logic: This course unit is a pre-requisite for Model Theory (MATH43051), Set Theory (MATH43021) and Godel's Theorems (MATH43042) in the academic year 2018/19.

Aims

To provide a concise base of mathematical logic, including Set Theory, Model Theory and Computabiility Theory.

Overview

The course captures the beginning of three pillars of mathematical logic: Set Theory, Model Theory and Computability Theory.

In Set Theory we will give a non-axiomatic approach to infinite numbers and how to do basic calculations with them. Historically this is how the subject began, when G. Cantor realised that ordinary arithmetic can be extended to the infinite. We will focus on ordinal and cardinal numbers and start with a brief introduction to ordered sets.

In Model Theory general mathematical structures are studied via formulas of first order logic (as introduced MATH20302-Propositonal Logic). A formula can be thought of a generalisation of an equation, but now we also allowing quantifiers. Model Theory provides tools to analyse solution sets of such formulas (called 'definable sets'). It also classifies structures according to the structure of their definable sets. The course will make first steps in this direction with illustrations in the complex and the real field.

In Computability Theory we will discuss the notion of computable functions and computable sets, their basic properties and how these objects are realised by machines.

All three parts have separate continuations at level 4.

Learning outcomes

On successfully completing the course students will be able to:

- understand the combinatorics of various classes of ordered sets

- understand the concept of the cardinal of a set beyond the finite case and be able to do simple ordinal and cardinality arithmetic

- understand definability in structures, in particular for the real and the complex field

- construct and compare structures using model theoretic tools

- understand how computability is studied in mathematics

- understand the scope of computability

Assessment methods

• Other - 30%
• Written exam - 70%

Assessment Further Information

Other relates to:

- Two hour end of semester examination; weighting within unit 70%

- There will be two in-class tests, weight 15% each.

Syllabus

•  Set Theory

Ordered and partially ordered sets [2 lectures]. Well ordered sets and the well ordering principle, Zorn's Lemma [2 lectures]. Ordinal numbers [2 lectures]. Cardinal numbers [2 lectures].

• Model Theory

The compactness theorem (revision from propositional logic) [1 lecture]. The method of diagrams; Skolem-Lowenheim theorems [3 lectures]. Definable sets [2 lectures]. Back & Forth [2 lectures]. Outlook: Model theory of the real and complex field [1 lecture].

• Computability

Examples and the Church-Turing thesis [1 lecture]. Computable functions [2 lectures]. Recursively enumerable sets [1 lecture]. Outlook: Decision problems [1 lecture].

Recommended reading

Self contained course notes will be provided. A variety of textbooks may be found on the unit's homepge.

Feedback methods

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding.  In-class tests also provide an opportunity for students to receive feedback.  Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.
 

Study hours

• Lectures - 22 hours
• Tutorials - 11 hours
• Independent study hours - 67 hours

Teaching staff