Sets and Logic, WS 2014/5, Slides of Monday Lecture

Sets and Logic, WS 2014/5

Slides of Monday Lecture

Lecturer: J.A. Makowsky


The slides have units called Lecture N (N=1,2,...)
There are 13 Sessions covering the material.

Last updated : This page: 29.12.2014

Last updated slides

The world of sets

Lecture 1: 27.10. 2014,
Lecture 2: 03.11. 2014,
Lecture 3: 24.11. 2014 (minor corrections),
Lecture 4: NEW: 01.12. 2014
(order of slides changed, added 3 slides on infinite cartesian products, added 2 slides on D-infinite vs infinite sets, added 2 slides on "countable unions of countable sets")
Lecture 5: 06.12. 2014 (colored pages beyond official course material)
This completes the slides on SETS. Minor improvements still possible.

Propositional Logic

Revised Lectures 8-13 not yet posted.
Lecture 6: 06.12. 2014 (some links to be added, colored pages beyond official course material)
Lecture 7: 06.12. 2014 (new with colored pages beyond official course material, some history of propositional calculus, and a page on "Why attend lectures").
Lecture 8-9: 21.12. 2014

Predicate Logic aka First Order Logic FOL

Lecture 10: 29.12. 2014
Lecture 11: 21.12. 2014 (still in preparation)
Lecture 12: 21.12. 2014 (still in preparation)
Lecture 13: 21.12. 2014 (still in preparation)

Here is the detailed report of what I covered:

  1. Session 1 (20.10.2014):
    Organisational matters. Introducing sets.
    We completed the material of
    Lecture 1 at the beginning of Session 2.
  2. Session 2 (27.10.2014):
    Ordered pairs, Cartesian products, Relations, Functions.
    Side effects of the various definitions of ordered pairs.
    We completed the material of
    Lecture 2 at the beginning of Session 3.
  3. Session 3 (03.11.2014):
    Transitive closure of a binary relation (from the end of Lecture 2).
    We started the material of
    Lecture 3.
    Introducing infinite sets. The postulates of replacement and of the existence of sets closed under set constructors.
    The of words over a finite alphabet. Unary words as natural numbers. Induction principle for sets of words. Peano Axioms.
    Examples of inductive definitions. I will add proofs for slide 19. We skipped slides 24-25.
    Important example (slides 26-29): Polynomial expressions as strings vs polynomial functions as real functions.
    Inductive definitions and proofs by inductions.
    We covered Slides 1-29 of
    Lecture 3.
  4. Session 4 (10.11.2014):
    We finished with
    Lecture 3 as posted on 10.11.2014.
    More on inductive defintions. General framework. Recursion Theorem.
    Four slides (19-21, 37) were added to
    Lecture 3 on November 10, 2014. Slide 22 was modified.
    We started
    Lecture 4 and got till slide 14.
    When do two sets have the same number of elements? Equipotence of sets.
  5. Session 5 (17.11.2014):
    We continue with
    Lecture 4. A new version of these slides after slide 14 were posted on 17.11.2014.
  6. Session 6 (24.11.2014):
    We complete Lecture 4 and its additions on D-infinite sets.

    We start and hopefully complete Lecture 5.

  7. Session 7 (01.12.2014):
    We discuss briefly another addition to Lecture 4: The proof of the Theorem: "Countable unions of countable sets are countable" needs the Axiom of Choice. We add it as a postulate, which means we can use it, but with our postulates so far we cannot proof it.
    We start with Propositional Logic (Lecture 6). We define Syntax and Semantics of Propositional Logic, and discuss truth tables.
    We may (unlikely) start Lecture 7.
  8. Session 8 (08.12.2014):
    We continue with Propositional Logic (Lecture 7)
    We may (likely) start Lecture 8-9.
  9. Session 9 (21.12.2014):
    We continue Lecture 8-9 starting from the revised slides. This session deals with Proof Systems. We hope to finish the material on Propositional Logic. Material on yellow-green background is skipped (for the exam) but still useful and important. Homework (even on yellow-green) may show up in actual homework or exams if it fits.
    We finished proof systems, and started definability.
  10. Session 10 (29.12.2014): We will finish definability from Lectures 8-9 and start with Predicate (First Order ) Logic of Lecture 10.