MATH 0050

Logic

Course Description

In this course, we will aim to introduce a language for (first order predicate) mathematical logic and study the interplay between the notions of 'truth' and 'provability' in the propositional and first order predicate 'versions' of logic. We will then aim to study computability, via register machines, recursive functions and coding, and try to use these concepts to show that first order predicate logic is undecidable.


TOPICS

Language:
Description and construction of a formal language for first order predicate logic.

Propositional logic:
A study of the semantic and syntactic aspects of propositional logic, including the semantic tableaux method, and a description of the completeness theorem for propositional logic and of some of its consequences.

Predicate logic:
A study of the semantic and syntactic aspects of first order predicate logic, including examples of first order languages and theories, and a description of the completeness theorem for first order predicate logic and of some of its consequences.

Computability:
An introduction to recursive partial functions and, via the notion of register machines, to computable partial functions, and a description of the halting problem.

Isidoros Strouthos