Coronavirus information for applicants and offer-holders

We understand that prospective students and offer holders may have concerns about the ongoing coronavirus outbreak. The University is following the advice from Universities UK, Public Health England and the Foreign and Commonwealth Office.

Read our latest coronavirus information

BSc Computer Science and Mathematics / Course details

Year of entry: 2020

Course unit details:
Mathematical Logic

Unit code MATH33011
Credit rating 10
Unit level Level 3
Teaching period(s) Semester 1
Offered by Department of Mathematics
Available as a free choice unit? No

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.

Pre/co-requisites

Unit title Unit code Requirement type Description
Introduction to Logic MATH20302 Pre-Requisite Optional

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.

Learning outcomes

On successfully completing the course students will be able to:

  • name the fundamental definitions and theorems of various classes of partially ordered sets (totally ordered, well-ordered, product orders and sums) and answer simple combinatorial questions testing if the definitions were understood,
  • define what is an ordinal and to perform simple operation (like sums and product) using the main theorems on ordinals and well-ordered sets,
  • define what is a cardinal beyond the finite case and to compute cardinalities of infinite sets in easy examples by using the main theorems on cardinal arithmetic,
  • enable students to formalize mathematical statements in first order logic and conversely understand the meaning of first-order sentences by constructing structures satisfying the sentences,
  • explain definability in structures and confirm definability of sets in a given structure in simple cases,
  • prove the existence of structures with specific properties and compare structures using model theoretic definitions and main theorems; in particular students will learn how to apply the compactness theorem,
  • state how computability in mathematics is implemented in a rigorous way for functions from integers to integers,
  • state and prove the negation theorem about recursively enumerable sets.

 

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].

 

 

Assessment methods

Method Weight
Other 20%
Written exam 80%

Other relates to:

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

- There will be two in-class tests, weighting 20% in total.

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.
 

Recommended reading

A full set of lecture notes will be provided. Further reading may be found in the references of these notes

Study hours

Scheduled activity hours
Lectures 22
Tutorials 11
Independent study hours
Independent study 67

Teaching staff

Staff member Role
Marcus Tressl Unit coordinator

Return to course details