BSc Mathematics with Placement Year

Year of entry: 2024

Course unit details:
Mathematical Logic

Course unit fact file
Unit code MATH33021
Credit rating 20
Unit level Level 3
Teaching period(s) Semester 1
Available as a free choice unit? 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 first 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 mathematical methods can be 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).


General mathematical structures (like groups, vector spaces or ordered sets) will
be used to exemplify formulas of first order logic. A formula can be thought of a
generalisation of an equation, but now we are also allowing quantifiers. The tools
developed in the course will be used to analyse solution sets of such formulas (called
’definable sets’). Furthermore the methods allow a classification of 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.


After having established the fundamentals of Predicate Logic we will revisit Set
Theory from an axiomatic point of view. We state and discuss Zermelo Fraenkel
Set Theory as well as immediate applications of the Completeness Theorem to Set
Theory.

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.


The course has a continuations at level 4 in the Model Theory module and provides valuable preparation for the modules Category Theory and Computation and
Complexity.
 

Aims

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

Learning outcomes

(1) 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.
(2) Define what is an ordinal and to perform simple operation (like sums and
product) using the main theorems on ordinals and well-ordered sets.
(3) 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.
(4) Enable students to formalize mathematical statements in first order logic and
conversely translate the meaning of first-order sentences by constructing structures satisfying the sentences.
(5) Explain formal proofs in first order logic and formulate the Soundness Theorem and the Completeness Theorem.
(6) Prove the existence of structures with specific properties and compare structures using model theoretic definitions and main theorems (like SkolemLöwenheim).
(7) Formulate, prove and apply the compactness theorem.
(8) Explain definability in structures and confirm definability of sets in a given
structure in simple cases.
(9) Formulate categoricity of theories and prove that categorical theories are complete. Name examples of categorical theories.

Syllabus

• Set Theory (4 weeks, 10 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]. The requirement of formal languages in set
theory. [1 lecture]


• 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, Completeness
and Compactness of Predicate Logic[2 lectures].


• First steps in axiomatice set theory (2 weeks, 6 lectures)
Axioms of set theory [2 lectures] and naïve set theory in this setup. Basic
applications of Predicate Logic to models of set theory [2 lecture]. Outlook:
Independence results [2 lecture].

Assessment methods

Method Weight
Written exam 100%

Feedback methods

Feedback tutorials will provide an opportunity for students’ work to be discussed
and provide feedback on their understanding. Formative in-class tests 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. There will be a discussion board on Piazza, accessible through
BlackBoard.

Recommended reading

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. ISBN : 9781846282294 https://
manchester.primo.exlibrisgroup.com/permalink/44MAN_INST/bofker/
alma992976946311601631


(2) Cori, René, Lascar, Daniel; Mathematical logic. A course with exercises.
Part I. Propositional Calculus, Boolean algebras, predicate calculus. Oxford University Press, Oxford, 2000. xx+338 pp. ISBN: 0-19-850049-1;
0-19-850048-3 http://man-fe.hosted.exlibrisgroup.com/MU_VU1:44MAN_
ALMA_DS21154144760001631
 

Study hours

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

Teaching staff

Staff member Role
Marcus Tressl Unit coordinator
Gareth Jones Unit coordinator

Return to course details