MATH 0050
Logic
Department of Mathematics
UCL
Lecture Notes
2022-2023
Isidoros Strouthos
7 January 2023
1
,Contents
1 Language 3
1.1 First order predicate language . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Conventional functional first order predicate language . . . . . . . . . . . . . . . . 13
2 Propositional Logic 19
2.1 Semantic aspects of propositional logic . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Syntactic aspects of propositional logic . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Completeness theorem for propositional logic . . . . . . . . . . . . . . . . . . . . 47
3 First Order Predicate Logic 58
3.1 Semantic aspects of first order predicate logic . . . . . . . . . . . . . . . . . . . . 58
3.2 Syntactic aspects of first order predicate logic . . . . . . . . . . . . . . . . . . . . 72
3.3 Completeness theorem for first order predicate logic . . . . . . . . . . . . . . . . . 77
4 Computability 87
4.1 Computable (partial) functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Recursive (partial) functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3 Encoding and the halting problem . . . . . . . . . . . . . . . . . . . . . . . . . . 104
2
,Chapter 1
Language
In order to be able to study the structure of mathematical objects and ideas, we will first provide a
framework in which mathematical objects can be defined and analysed.
1.1 First order predicate language
The symbols which we will use to construct our language consist of:
1) A countably infinite set of variable symbols: {x1 , x2 , x3 · · · } or {w, x, y, z, w0 , x0 , y 0 , z 0 , · · · }.
2) For each non-negative integer n, a countably infinite set of predicate symbols {P1 , P2 , P3 · · · }
or {P, Q, R, P 0 , Q0 , R0 , · · · }, each of which has arity n. If P is a predicate symbol of arity n,
then we call P an n-ary predicate symbol.
3) The symbols ¬, ), 8.
The set of all strings of symbols from the above list is denoted by Lstring .
For example, suppose that x, y, z, x1 , x2 , x3 are variable symbols, P is a 1-ary predicate symbol, and
Q is a 2-ary predicate symbol. Then x, P x, P xy, Qx, Qxy, Qxx, xQy, Qx1 x2 x3 , ¬P x, ) P xQyz,
8x8yQxy, 8x, 8x ) ¬P xQxy, 8x ) P ¬xQxy are all in Lstring .
Let us now consider the subset of Lstring that will be especially useful:
3
,
Logic
Department of Mathematics
UCL
Lecture Notes
2022-2023
Isidoros Strouthos
7 January 2023
1
,Contents
1 Language 3
1.1 First order predicate language . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Conventional functional first order predicate language . . . . . . . . . . . . . . . . 13
2 Propositional Logic 19
2.1 Semantic aspects of propositional logic . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Syntactic aspects of propositional logic . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Completeness theorem for propositional logic . . . . . . . . . . . . . . . . . . . . 47
3 First Order Predicate Logic 58
3.1 Semantic aspects of first order predicate logic . . . . . . . . . . . . . . . . . . . . 58
3.2 Syntactic aspects of first order predicate logic . . . . . . . . . . . . . . . . . . . . 72
3.3 Completeness theorem for first order predicate logic . . . . . . . . . . . . . . . . . 77
4 Computability 87
4.1 Computable (partial) functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Recursive (partial) functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3 Encoding and the halting problem . . . . . . . . . . . . . . . . . . . . . . . . . . 104
2
,Chapter 1
Language
In order to be able to study the structure of mathematical objects and ideas, we will first provide a
framework in which mathematical objects can be defined and analysed.
1.1 First order predicate language
The symbols which we will use to construct our language consist of:
1) A countably infinite set of variable symbols: {x1 , x2 , x3 · · · } or {w, x, y, z, w0 , x0 , y 0 , z 0 , · · · }.
2) For each non-negative integer n, a countably infinite set of predicate symbols {P1 , P2 , P3 · · · }
or {P, Q, R, P 0 , Q0 , R0 , · · · }, each of which has arity n. If P is a predicate symbol of arity n,
then we call P an n-ary predicate symbol.
3) The symbols ¬, ), 8.
The set of all strings of symbols from the above list is denoted by Lstring .
For example, suppose that x, y, z, x1 , x2 , x3 are variable symbols, P is a 1-ary predicate symbol, and
Q is a 2-ary predicate symbol. Then x, P x, P xy, Qx, Qxy, Qxx, xQy, Qx1 x2 x3 , ¬P x, ) P xQyz,
8x8yQxy, 8x, 8x ) ¬P xQxy, 8x ) P ¬xQxy are all in Lstring .
Let us now consider the subset of Lstring that will be especially useful:
3
,
