20327 Mathematical Logic 1

Credits: 6 advanced credits in Mathematics

Prerequisites: Students must fulfill all English requirements and take bibliographic instruction in the Library.

Required: At least 36 credits in Mathematics

Recommended: Infinitesimal Calculus I, Infinitesimal Calculus II, Linear Algebra I, Set Theory, Algebraic Structures

Authors: Azriel Levy, Daniela Leibowitz, Shmuel Berger

Topics: Propositional Calculus: Syntax – the alphabet and the expressions of the language of propositional calculus, induction and recursion, propositions and their formation trees, unique readability, substitutions; Semantics – structures for propositional calculus, truth tables, models, semantics of substitutions, tautologies and contradictions, tautological implication and equivalence, consistency – truth tables and the compactness theorem, complete sets of connectives; Proof theory – deduction systems, proofs, soundness and completeness. Predicate Calculus: Syntax – alphabets of predicate calculus languages, expressions, terms and formulas, induction and unique readability for terms and formulas, free and bound variables, propositions, substitutions and replacements; Semantics – structures, valuations, truth under different valuations, truth in a structure, logical truth, logical implication and equivalence, tautological implication and equivalence in predicate calculus, semantics of substitutions and replacements; Model theory – isomorphism of structures, elementary equivalence, definability and explicit definability, properties of definable relations, addition and omission of symbols which do not affect the expressive power of a language, first order, second order and monadic calculi, semi definability, categoricity, sub structures and elementary sub-substructures, the Skolem-Löwenheim theorems, non-standard models of number theory, completeness of theories, consistency and the compactness theorem; Proof theory – decidability and semi-decidability, deduction systems – proofs and theorem, completeness in the weak sense, and completeness; Gödel’s completeness theorem, Gödel’s incompleteness theorem.

1A short non-credit seminar may be added to this course. See note under Mathematics seminars.

There is some overlap in the content of this and other courses. For details, see Overlapping Courses.