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.