Mathematical Logic 1000-135LOM
1. Elements of propositional logic: syntax and semantics of proposition logic, the compactness theorem, the completeness of a proof system.
2. Structures: isomorphism, substructures, Boolean algebras.
3. Syntax of first-order logic: terms and formulas.
4. Semantics of first-order logic: structures and interpretations.
5. A proof system for first-order logic: formal proofs, the Godel completeness theorem, the compactness theorem.
6. Elements of model theory: ultraproducts, elementary submodels, Lowenheim-Skolem theorem, omitting types theorem.
Type of course
Prerequisites
Course coordinators
Term 2024Z: | Term 2023Z: |
Learning outcomes
The student:
1. is familiar with basic concepts related to the syntax and semantics of propositional logic; knows the Compactness Theorem for propositional logic and can give examples of its applications; is able to prove that every formula is logically equivalent to a DNF and a CNF formula, and to find normal forms for given formulas; is acquainted with a proof system for propositional logic and the Completeness Theorem for that system;
2. knows the definition of a relational structure and definitions of basic operations on structures; is able to give examples illustrating these definitions; is familiar with basic concepts and results related to boolean algebras, including the notions of filter and ultrafilter and the Stone Representation Theorem;
3. is familiar with basic concepts related to the syntax and semantics of first-order logic, including the notions of satisfaction and truth; understands what classes of formulas preserve truth value under specific operations on structures; is familiar with typical examples of logically valid sentences and with prenex normal form; is able to put simple formulas in prenex normal form;
4. understands the concept of an axiomatizable and a finitely axiomatizable class of structures; is able to construct sets of sentences axiomatizing specific classes of structures; is familiar with the notion of a definable set in a structure and is able to write down formulas defining various sets in given structures; knows how to prove the undefinability of sets by means of automorphisms;
5. knows the compactness theorem for first-order logic;
6. is familiar with the concept of ultraproducts, with examples of ultraproducts, and with Łoś's Theorem;
7. is able to prove the non-axiomatizability of structures using the Compactness Theorem or Łoś's Theorem; knows the Frayne-Morel-Scott characterization of axiomatizability;
8. is acquainted with a proof system for first-order logic and the Completeness Theorem for that system;
9. knows the concept of an elementary substructure and the Löwenheim-Skolem Theorem; is able to use the Löwenheim-Skolem Theorem to construct structures of a given cardinality and with specified logical properties.
Assessment criteria
1. Students who score at least 50% on homework assignments will be allowed to take the exam in the first term.
2. The exams held during the session will consist of a written part (for everyone), and an oral part (for some; see 3. below).
3. In special cases, the instructor may propose an oral exam to the student, the result of which can change the grade resulting from the written exam. It should be assumed that the number of invitations to the oral exam will be small, but it may increase significantly if the written exam is online.
4. Students who fall within the top 10% of course participants (in terms of points for homework assignments, activity in classes, and, if applicable, activity in lectures) can apply for a zero-term exam. Applications for the zero-term exam can be submitted starting from January 13, 2025. The zero-term exam will be exclusively oral and will assess both problem-solving skills and knowledge of theory.
5. The grade for the course is determined solely based on the exam.
Bibliography
Z. Adamowicz, P. Zbierski, Logic of Mathematics, Wiley 1997.
J. Barwise, ed., Handbook of Mathematical Logic, North-Holland, Amsterdam 1978.
J.L. Bell, A.B. Slomson, Models and Ultraproducts: An Introduction, North-Holland, Amsterdam 1986.
Herbert B. Enderton, A mathematical introduction to logic, Academic Press, 2000 (2nd ed.)
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Mathematics
- Master's degree, second cycle programme, Mathematics
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: