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ść,

Literatura

1. Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
2. Algorytmy i struktury danych, L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.

• 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 2N ~ 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. Własności. · Zbiory liczb porządkowych. · Twierdzenie o definiowaniu przez indukcje pozaskończoną. Twierdzenie Zermelo. Lemat Kuratowskiego Zorna. · Rezolucja i automatyczne dowodzenie twierdzeń

Literatura · H. Rasiowa, Wstęp do matematyki, PWN, Warszawa 1971, 1984, 1998 · K. Kuratowski, A. Mostowski, Teoria mnogości, PWN, Warszawa, 1978