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

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