Don't just imagine your future at University, experience it first-hand!

Step into the shoes of an undergraduate student and join us for our upcoming on-campus Discover Days in Science, Engineering and Fashion. These days are tailored exclusively for Year 12s who are interested in taking their academic journey to the next level. Find your favourite subject now!

# BSc Computer Science and Mathematics / Course details

Year of entry: 2024

## Course unit details:Mathematical Logic

Unit code MATH33021 20 Level 3 Semester 1 No

### Overview

The course captures the beginning of first order logic and leads up to applications of Mathematical Logic in Algebra and Analysis.

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 Predicate Logic we will set up so called first order languages in which mathematics can be formalized and applied. Hence the informal notion of a ’formula’ will become a mathematical object, amenable to tools and methods from the subject.

For example one can ask if there is a computer, which in principle is able to find all true statements about mathematics (this was a driving force at the beginning of the discipline). It turned out that such a computer cannot exist. The crux here is that this statement has a rigorous mathematical proof, which necessitates the translation of clauses like “true statements about mathematics” and “can be proved” into mathematical statements itself. This part of the course will give a thorough exposition of this translation together with the fundamental theorems saying that the translation is correct (Soundness Theorem) and optimal (Completeness Theorem).

In Model Theory general mathematical structures (like groups, vector spaces or ordered sets) are studied via formulas of first order logic. A formula can be thought of a generalisation of an equation, but now we are also allowing quantifiers. Model Theory provides tools to analyse solution sets of such formulas (called ’definable sets’). Furthermore it classifies mathematical structures according to the properties of their definable sets. This for example connects a priori different looking structures (think of a group and an ordered set) in surprising ways. The course will make first steps in this direction with illustrations in the complex and the real field.

This course has two separate continuations at level 4.

### Pre/co-requisites

Familiarity with rigorous treatment of the basic mathematical language (sets, functions and relations) is indispensable. Simple properties of groups (as for example taught in Groups & Geometry) will be assumed, and will be used mainly in examples. The definition of fields and vector spaces over fields will be helpful in examples, but is not strictly assumed.

Level 4 modules that require Mathematical Logic: This course unit is a pre-requisite for Model Theory (MATH43051) and Set Theory (MATH43021)

### Aims

To provide a concise base of Mathematical Logic, including Set Theory, Predicate Logic and Model Theory.

### Learning outcomes

On successfully completing the course students will be able to:

• State 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 a cardinal beyond the finite case and compute cardinalities of infinite sets in simple examples by using the main theorems about cardinal arithmetic.
• Formalize mathematical statements in first order logic and conversely translate the meaning of first-order sentences by constructing structures satisfying the sentences.
• Explain formal proofs in first order logic and formulate the Soundness Theorem and the Completeness Theorem.
• Prove the existence of structures with given specific properties and compare structures using model theoretic definitions and main theorems (like Skolem-Löwenheim).
• State, recall the proof of, and apply the compactness theorem.
• Explain definability in structures and confirm definability of sets in a given structure in simple cases.
• Formulate categoricity of theories and prove that categorical theories are complete and recognise and describe examples of categorical theories.

### Syllabus

• Set Theory (3 weeks, 9 lectures)
Ordered and partially ordered sets [3 lectures]. Well ordered sets and the well
ordering principle, Zorn’s Lemma [2 lectures]. Ordinal numbers [2 lectures].
Cardinal numbers [2 lectures].

• Predicate Logic (5 weeks, 15 lectures)
Syntax and semantics of Propositional Logic [2 lectures]. Proof system and
completeness of Propositional Logic [2 lectures]. First order languages [2 lectures]. First order structures [2 lectures]. Examples: Groups and partially ordered sets [3 lectures]. Formal proofs [2 lectures]. Soundness and Completeness of Predicate Logic [2 lectures].

• Model theory (3 weeks, 9 lectures)
Homomorphisms, elementary embeddings and the Tarski-Vaught test [2 lectures]. The compactness theorem [1 lecture]. The Skolem Löwenheim theorems [1 lecture]. Definable sets [2 lectures]. Back & Forth [1 lecture]. Categoricity [1 lecture] Outlook: Model theory of the real and the complex field [1 lecture]

### Assessment methods

Method Weight
Written exam 70%
Written assignment (inc essay) 15%
Practical skills assessment 15%

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

A full set of lecture notes will be provided. Further reading may be found in the references of these notes. The following two books are not text books for the course, but will give interested students a good impression what the subject is about.

(1) Goldrei, Derek; Propositional and Predicate Calculus: A Model of Argument; Springer London, 2005.

(2) Cori, René, Lascar, Daniel; Mathematical logic. A course with exercises. Part I. Propositional Calculus, Boolean algebras, predicate calculus. Oxford University Press, Oxford, 2000.

### Study hours

Scheduled activity hours
Lectures 33
Tutorials 22
Independent study hours
Independent study 145

### Teaching staff

Staff member Role
Marcus Tressl Unit coordinator

The independent study hours will normally comprise the following. During each week of the taught part of the semester:

•         You will normally have approximately 60-75 minutes of video content. Normally you would spend approximately 2-2.5 hrs per week studying this content independently
•         You will normally have exercise or problem sheets, on which you might spend approximately 1.5hrs per week
•         There may be other tasks assigned to you on Blackboard, for example short quizzes or short-answer formative exercises
•         In some weeks you may be preparing coursework or revising for mid-semester tests

Together with the timetabled classes, you should be spending approximately 6 hours per week on this course unit.
The remaining independent study time comprises revision for and taking the end-of-semester assessment.

The above times are indicative only and may vary depending on the week and the course unit. More information can be found on the course unit’s Blackboard page.