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:

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

Assessment methods

• Other - 20%
• Written exam - 80%

Assessment Further Information

Other relates to:

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

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

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