Logic II

10 credits

Syllabus, Bachelor's level, 1MA028

A revised version of the syllabus is available.
Code
1MA028
Education cycle
First cycle
Main field(s) of study and in-depth level
Computer Science G2F, Mathematics G2F
Grading system
Pass with distinction (5), Pass with credit (4), Pass (3), Fail (U)
Finalised by
The Faculty Board of Science and Technology, 15 March 2007
Responsible department
Department of Mathematics
What is a course syllabus?

Entry requirements

Algebra II, Logic and Proof Techniques I

Learning outcomes

In order to pass the course (grade 3) the student should be able to

  • give an account of important concepts and definitions in the area of the course;

  • exemplify and interpret important concepts in specific cases;

  • formulate important results and theorems covered by the course;

  • describe the main features of the proofs of important theorems;

  • express problems from relevant areas of applications in a mathematical form suitable for further analysis;

  • use the theory, methods and techniques of the course to solve mathematical problems;

  • present mathematical arguments to others.

    Higher grades, 4 or 5, require a higher level of proficiency. The student should be able to solve problems of greater complexity, i.e. problems requiring a combination of ideas and methods for their solution, and be able to give a more detailed account of the proofs of important theorems and by examples and counter-examples be able to motivate the scope of various results. Requirements concerning the student's ability to present mathematical arguments and reasoning are greater.

    Content

    Elementary recursion theory: primitive recursive functions and partial recursive functions, properties of recursive and recursively enumerable sets, the s-m-n theorem, the second recursion theorem and a little about the arithmetical hierarchy and relative computability.

    Strength of first order theories. Models for theories, Tarski semantics, the completeness and compactness theorems. Gödel's incompleteness theorems.

    Model theory: isomorphism, substructure, elementary equivalence and elementary substructure, the Löwenheim–Skolem theorems, Ehrenfeucht–Fraisse games, model completeness, complete theories, algebraic applications, non-standard analysis.

    Instruction

    Lectures and problem solving sessions.

    Assessment

    Written and, possibly, oral examination at the end of the course. Moreover, compulsory assignments may be given during the course.