Logika i teoria mnogości

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Zapoznanie się z podstawowymi pojęciami i narzędziami matematyki. Wprowadzenie fundamentalnych obiektów matematycznych i opis ich własności.

Sylabus

Autorzy

• Marek Zaionc
• Jakub Kozik
• Marcin Kozik

Zawartość

• Rachunek zdań i rachunek predykatów.
• Aksjomatyka teorii mnogości ZFC.
• Iloczyn kartezjański, relacje, relacja równoważności, rozkłady zbiorów.
• Konstrukcja von Neumanna liczb naturalnych:
  • twierdzenie o indukcji,
  • własności liczb,
  • definiowanie przez indukcję,
  • zasada minimum,
  • zasada maksimum.
• Konstrukcja i działania na liczbach całkowitych
• Konstrukcja i działania na liczbach wymiernych.
• Konstrukcja Cantora liczb rzeczywistych:
  • działania i porządek.
• Funkcje, twierdzenie o faktoryzacji:
  • Obrazy i przeciwobrazy zbiorów.
• Teoria mocy:
  • Zbiory przeliczalne i ich własności.
  • Zbiory liczb całkowitych i wymiernych są przeliczalne.
  • Zbiór liczb rzeczywistych jest nieprzeliczalny.
  • Zbiory $\{0,1{\}}^N$ i $N^N$ nie są przeliczalne. Zbiór $2^N\sim R$
  • Twierdzenie Knastera - Tarskiego (dla zbiorów)
  • Lemat Banacha,
  • Twierdzenie Cantora-Bernsteina, (warunki równoważne),
  • Twierdzenie Cantora.
  • Zbiory mocy kontinuum.
• Zbiory uporządkowane.
  • Lemat Kuratowskiego Zorna.
  • Przykłady dowodów przy pomocy lematu Kuratowskiego Zorna.
  • Dowód lemat Kuratowskiego Zorna
• Zbiory liniowo uporządkowane.
  • Pojęcia gęstości i ciągłości.
  • Porządek na $R$ jest ciągły.
• Zbiory dobrze uporządkowane.
  • Twierdzenie o indukcji.
  • Liczby porządkowe.
  • Zbiory liczb porządkowych.
  • Twierdzenie o definiowaniu przez indukcje pozaskończoną
  • Twierdzenie Zermelo,
• Język rachunku predykatów
  • Rezolucja i automatyczne dowodzenie twierdzeń

Literatura

1. H. Rasiowa, Wstęp do matematyki, PWN, Warszawa 1971, 1984, 1998
2. K. Kuratowski, A. Mostowski, Teoria mnogości, PWN, Warszawa, 1978
3. W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogosci w zadaniach, PWN, 1996.

Moduły

1. Po co nam teoria mnogości? Naiwna teoria mnogości, naiwna indukcja, naiwne dowody niewprost. (Ćwiczenia 1)
2. Rachunek zdań. (Ćwiczenia 2)
3. Rachunek predykatów, przykład teorii w rachunku predykatów. (Ćwiczenia 3)
4. Teoria mnogości ZFC. Operacje na zbiorach. (Ćwiczenia 4)
5. Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów. (Ćwiczenia 5)
6. Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha. (Ćwiczenia 6)
7. Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje. (Ćwiczenia 7)
8. Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek (Ćwiczenia 8)
9. Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum. (Ćwiczenia 9)
10. Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości. (Ćwiczenia 10)
11. Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady. (Ćwiczenia 11)
12. Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną. (Ćwiczenia 12)
13. Język rachunku predykatów. Rezolucja i automatyczne dowodzenie twierdzeń. (Ćwiczenia 13)