SylabUZ
| Course name | Logic and Set Theory |
| Course ID | 11.1-WK-MATP-LTM-W-S14_pNadGenJ30JE |
| Faculty | Faculty of Mathematics, Computer Science and Econometrics |
| Field of study | Mathematics |
| Education profile | academic |
| Level of studies | First-cycle studies leading to Bachelor's degree |
| Beginning semester | winter term 2019/2020 |
| Semester | 1 |
| ECTS credits to win | 6 |
| Course type | obligatory |
| Teaching language | polish |
| Author of syllabus |
|
| The class form | Hours per semester (full-time) | Hours per week (full-time) | Hours per semester (part-time) | Hours per week (part-time) | Form of assignment |
| Lecture | 30 | 2 | - | - | Exam |
| Class | 30 | 2 | - | - | Credit with grade |
Familiarize students with structures underlying contemporary mathematics.
Secondary school mathematics.
Lecture
1. Propositional calculus Logical connectives. Boolean valuations. Tautologies. Rules of inference. (3 godz.)
2. Sets Membership relation, set inclusion; equality of sets. Operations on sets: union, intersection, set difference, symmetric difference, complement. De Morgan laws. Cartesian product of two sets. (3h)
3. Quantifiers Definition, basic properties. Operations on arbitrary families of sets. (2h)
4. Binary relations and functions Domain and codomain. Frequently occurring relations. Function as a relation. Indexed families of sets: uions, intersections. Sentential functions – schema of specification, Russel’s paradox. Injections, surjections, bijections; restriction and extension of a function; composition of a function; inverse functions. Images and counterimages. Methods of defining functions. (4h)
5. Mathematical induction Peano axioms . The principle o mathematical induction. Alternative formulations. Recurrent sequences. Counting finite sets; exclusion-inclusion principle. (3h)
6. Relations (cont.) Equivalence relations: Equivalence classes vs partitions. Quotients constructions: rational numbers. Generalized products; generalized relations. (3h)
7. Cardinality of a set
Countable sets: the integers, the rational and algebraic numbers. Cantor–Bernstein theorem. Cantor theorem on power sets. Uncountability of the reals; other sets equinumerous with continuum: e.g. cardinality of a square. Continuum hypothesis. Cardinal numbers (brief information). (7h)
8. Orders
Distinguished elements of partial orders: the greatest and the maximal elements, upper bound etc. Complete lattices – Tarski’s fixed point theorem. Isomorphism of partially ordered sets: realisation of a partial order by inclusion. Preference relations. Dense and continuous linear orders. Well-ordered sets. (3h)
9. Axiom of choice
Hausdorff’s theorem on the existence of a maximal chain. Kuratowski-Zorn lemma; the existence of the Hamel bases. Well-ordering principle; cardinal numbers revisited. (2h)
Class
1. Propositional calculus Computing the logical value of a propositional expression for given values of its logical variables. Checking whether a given propositional expression is a tautology. Equivalent propositions – expressing a proposition in an equivalent form with the use of given connectives. (3h)
2. Sets Algebra of sets: checking whether two algebraic formulas involving sets and operations on sets represent the same set. Simple laws and their proofs. (3h)
3. Quantifiers Writing down theorems using quantifiers and logic symbols. (3h)
4. Relations and functions Checking properties of relations and functions. Finding domain and counterdomain of a function (relation). Compositions of functions. Manipulating with indexed families of sets. Images and counterimages. (3h)
5. Class test (2h)
6. Mathematical induction Examples of reasoning by induction. Functions defined inductively – finding their values and checking properties. (3h)
7. Relations (cont.) Verifying whether a given relation is an equivalence. Applications of equivalence relations to simple algebraic constructions.(3h)
8. Cardinality Comparing the cardinalities of two sets. Examples of countable and uncountable sets (Cantor’s set). (5h)
9. Orders Checking properties of orders. Examples of dense subsets of the reals. Examples of complete lattices. Examples of well-ordered sets different from subsets of natural numbers. Transfinite induction (optionally). (3h)
10. Class test (2h)
Traditional lecturing, solving problems under the supervision of the instructor.
| Outcome description | Outcome symbols | Methods of verification | The class form |
1. Preparation of the students and their active participation is assessed during each class by their instructor.
2. Class tests with problems of diverse difficulty helping to assess whether a student achieved minimal outcomes.
3. Written examination: It consists of around 18 problems. Each problem consists of 2 or 3 statements. To solve a problem, one has only to decide whether the statements are true or false. For some of them, however, explanations are demanded.
Final grade = 0.4 x class grade + 0,6 x exam grade. In order to be allowed to take the exam a student has to have a positive class grade. In order to pass the exam a student has to have a positive exam grade.
1. K. Kuratowski, A.Mostowski, Set theory, North-Holland, 1976.
1. M. Aigner, G. M. Ziegler, Proofs from the BOOK, Springer 2004.
It is recommended to encourage students to use Python when solving exercises.
Modified by dr Robert Dylewski, prof. UZ (last modification: 19-09-2019 13:26)
