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:
Session 1
(20.10.2014):
Organisational matters. Introducing sets.
We completed the material of
Lecture 1
at the beginning of Session 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.
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
.
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.
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.
Session 6
(24.11.2014):
We complete Lecture 4 and its additions on D-infinite sets.
We start and hopefully complete
Lecture 5
.
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.
Session 8
(08.12.2014):
We continue with Propositional Logic (Lecture 7)
We may (likely) start Lecture 8-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.
Session 10
(29.12.2014): We will finish definability from Lectures 8-9 and start with Predicate (First Order ) Logic of Lecture 10.