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

Wymagania wstępne

• Brak

Zawartość

• Podstawowe zasady analizy algorytmów:
  • poprawność,

• Rachunek zdań i rachunek predykatów.
• Aksjomatyka teorii mnogości, aksjomaty sumy, ekstensjonalności, przecięcia, pary.
• 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 indukcje,
  • zasada minimum,
  • zasada maksimum.
• Konstrukcja liczb całkowitych i wymiernych:
  • działania na liczbach całkowitych
  • Konstrukcja liczb 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.
  • Zbióry liczb całkowitych i wymiernych są przeliczalny.
  • Zbiór liczb rzeczywistych jest nieprzeliczalny.
  • Zbiory $\{0,1{\}}^N$ i $N^N$ nie są przeliczalne. Zbiór $2^{N}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.
• Zbiory liniowo uporządkowane.
  • Pojęcia gęstości i ciągłości.
  • $R$ jest ciągła.
• Zbiory dobrze uporządkowane.
  • Twierdzenie o indukcji.
  • Liczby porządkowe.
  • Zbiory liczb porządkowych.
  • Twierdzenie o definiowaniu przez indukcje pozaskończoną
  • Twierdzenie Zermelo,
  • Dowód lemat Kuratowskiego Zorna
• 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

Moduły

1. Temat (Ćwiczenia)
2. Temat (Ćwiczenia)
3. Temat (Ćwiczenia)
4. Temat (Ćwiczenia)
5. Temat (Ćwiczenia)
6. Temat (Ćwiczenia)
7. Temat (Ćwiczenia)
8. Temat (Ćwiczenia)
9. Temat (Ćwiczenia)
10. Temat (Ćwiczenia)
11. Temat (Ćwiczenia)
12. Temat (Ćwiczenia)
13. Temat (Ćwiczenia)