UCL - Some notions of mathematical logic

[MAT1235]

[30h + 15h] 5 credits

This course is taught in the 2d semester.

Teacher(s): Christian Michaux, Cédric Rivière

Language: French

Level: First

Aims
Main themes
Content and teaching methods

Aims

One aims at making explicit the laws of mathematical resoning, when it is presented as a formalised theory. One examines the peculiarities of the languages that are used, the propositions that are taken as starting points, the deduction rules that are usually admitted.
One looks also at the limitations of the formalisation process, e.g. the impossibility to guarantee a definitive rigour. The spirit and the presentation are of the same kind as for any mathematical course : one gives definitions, one constructs chains of propositions, one proves theorems.

Main themes

We start recalling some basic concepts and axioms of set theory : extensionality, union, infinity, natural numbers object, induction, denumerable sets and higher powers.
Then we look at finitary algebraic structures and languages, in the spirit of universal algebra, making use of homomorphisms and the universal property of the algebra of terms to treat in detail such topics as substitution.
Propositional calculus follows, as the study of a particular algebraic structure, with the task of discovering all valid formulas. To reach that goal, one sets up a formal system, proving on one hand that it is sound (all provable formulas are valid) and on the other that it is complete (all valid formulas are provable).
In the next part, one studies predicate calculus, i.e. the general properties of first order structures and languages .
In these languages one has to deal with algebras of terms and algebras of formulas. The interpretation of functional and relational symbols is extended to link derived finitary operations with each term and derived finitary relations with each formula. Again, one is interested in getting all valid formulas, and one develops an axiomatic system for that purpose. Soundness and completeness are proved, the latter in Henkin style.
Concepts are illustrated by looking at familiar algebraic or first order structures, such as groups and ordered fields.
If some time is left, we will look at other notions of set theory, such as the axiom of choice, ordinals, cardinal arithmetic, or we will introduce recursive functions.

Content and teaching methods

Contents :
Set-theoretical preliminaries (basic notions, definition of certaine sets, natural numbers and induction, ordered pairs and cartesian products, relations, functions, maps, denumerability)
Preliminaries : algebraic structures, algebraic languages, interpretations and valuations, universal property of term algebras.
Propositional logic: semantical point of view (algebraic structure of truth values, propositional language, standard interpretation, truth, tautologies) , axiomatic point of view (propositional calculus, consistency and maximality of theories) and link between both points of view ( soundness and completeness).
Predicate logic: semantical point of view (first-order stuctures, interpretations, models, valid formulas), axiomatic point of view (first-order calculus, consistency, closed theories, rich theories, maximality) and links between both points of view (soundness and completeness).
First order theories with equality.

Method: combination of a series of lectures on theoretical aspects and of a series of exercises about examples and applications.