Foundations of mathematics

computer science

obligatory courses

Introducing the basic notions of set theory and logic. Developing the mathematical skills of students, in particular the ability to use abstract mathematical tools and prove theorems.

Propositional logic and its properties. Introduction to predicate logic.

Set-theoretic operations, including infinite ones.

Relations, functions, and their basic properties.

Equivalence relations, the principle of abstraction.

Natural numbers. The principle of induction.

Equipotent sets. Finite and infinite sets. Enumerable and non-enumerable sets.

Cantor's theorem and Cantor-Bernstein theorem.

Partial and total ordering relations. Applications of Kuratowski-Zorn Lemma.

Lower and upper bounds, fixed-point theorems. Applications in program semantics.

Well-ordered and well-founded sets. Structural induction.

The notion of a formal proof. Proof systems for propositional logic, the completeness theorem.

Relational structures and the first-order logic: semantics, completeness.

1. K. Kuratowski, A. Mostowski, Teoria mnogości, Państwowe Wydawnictwo Naukowe, Warszawa 1978.

2. W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogosci w zadaniach, Wydawnictwo Naukowe PWN, Warszawa 1996.

3. H. Rasiowa, Wstęp do matematyki, Państwowe Wydawnictwo Naukowe, Warszawa 1971, 1984, 1998.

4. J. Tiuryn, Wstęp do teorii mnogości i logiki, skrypt UW.

Knowledge:

* Has sufficient knowledge about the algebra of sets.

* Is familiar with the notion of a relation and a function and their basic properties.

* Understands the principle of mathematical induction and properties of equivalence relations.

* Is familar with the notion of cardinality.

* Understands what a partial order is as well as a well-founded set.

* Has the basic knowledge about propositional and first-order logic.

Skills

* Is able to understand a mathematical text and can write a simple proof.

* Can perform operations on sets including operations on infinite families.

* Is able to determine basic properties of functions and relations.

* Can identify equivalence classes.

* Can determine the cardinality of a given set.

* Can determine upper and lower bounds and use induction.

* Can verify if a given formula is valid.

Competences

* Understands the necessity of rigorous precision in mathematical argument.

* Is prepared to autonomously study problems described in a mathematical language.

To pass the course one has to pass the exercises and the exam.

To pass the exercises one has to pass: the homework assignments, the mid-term test, and the internet tests on Moodle. The final decision belongs to the teacher of the exercises group.

The exam is written. Some students may be invited for a supplementary spoken exam.

The fiinal grade will be determined (in the first term) on the basis of the maximum of two values:

1. The score of the exam

2. The weighted average of the mid-term score (30%) and exam score (70%).

The scores from the correction mid-term (if applicable) are not taken into account for the final grade.

In the second term the grade is determined solely on the basis of exam score.

Those who have completed their homework assignments and scored at least 90% at the mid-term can take the zero exam, provided they declared their readiness for the exam no later than January 7. The form (written/spoken) of the zero exam will depend on the number of participants.