Mathematical Logic

elective courses

Introduction to mathematics 1000-111bWMAa

An introduction to classical topics of mathematical logic with elements of model theory.

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.

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.)

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.

1. The students who score at least 50% on homework assignments will be allowed to take the exam in the first term.

2. Exams held during the session will consist of a written part, including theory and problems (for everyone), and an oral part (see point 3).

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. The number of invitations to the oral exam may significantly increase if the written exam is on-line.

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 15, 2024. 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.

6. Due to the Dean of the Faculty of Mathematics, Informatics, and Mechanics' recommendation regarding frequent ventilation of rooms, lectures (twice for 45 minutes with a fifteen-minute break) will, as far as possible, take place with open windows. Please, ensure that you have warm sweaters or other coverings with you in response to this.