# 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ödels completeness theorem, Gödels 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.