1105140243

rów przez relacje. Omawiamy funkcje logiczne - pokazujemy, że standardowy zestaw spójników logicznych jest zupełny (synteza formuły odbywa się za pomocą tabeli wartości rozważanej funkcji). Następnie omawiamy indeksowane rodziny zbiorów oraz produkty kartezjańskie. W końcu wprowadzamy pojęcie funkcji charakterystycznej zbioru.

5.    Wykład piąty poświęcony jest w całości relacjom równoważności. Pokazujemy w nim, jak startując z liczb naturalnych można zdefiniować liczby całkowite, wymierne i rzeczywiste.

6.    Wykład szósty poświęcony jest częściowym porządkom. Po wprowadzeniu podstawowych pojęć omawiamy porządki na rodzinach funkcji. Celem tego fragmentu rozważań jest przybliżenie czytelnikom notacji / = O(g). Następnie omawiamy liniowe porządki i porządek leksykograficzny na przestrzeni słów. Przechodzimy do prezentacji Lematu Kuratowskiego - Zorna i jego podstawowych konsekwencji. Wprowadzamy Aksjomat Wyboru. Pod koniec tego wykładu omawiamy pojęcie dobrego porządku.

7.    W wykładzie poświęconym Indukcji Matematycznej pokazujemy jej równoważność z dobrym uporządkowaniem zbioru liczb naturalnych, omawiamy definicje rekurencyjne. Przypominamy pojęcie permutacji i wprowadzamy symbol Newtona. Rozważania kończymy zasadą Dirichleta.

8.    W wykładzie ósmym omawiamy pojęcie równoliczności i nierówności mocy. Twierdzenie Cantora - Bernsteina wyprowadzamy za pomocą Lematu Banacha. Omawiamy zbiory przeliczalne i zbiory continuum. Głównym obszarem zainteresowań jest zbiór N U {No, 2^N°}, jednak pod koniec rozdziału wprowadzamy hierarchię liczb dla n G N.

9.    Wykład dziewiąty poświęcony jest relacją ufundowanym, systemom przepisującym oraz drzewom. Tematy te umieszczone są w głównej części książki ze względu na ich liczne zastosowania w informatyce.

10.    W dodatku A znajduje się wprowadzenie do teorii algebr Boole’a. Rozpoczynamy od definicji, a kończymy na słabej wersji twierdzenia Stone’a o reprezentacji. W trakcie rozważań pojawia się pojęcie ciała zbiorów.

11.    W dadatku B wprowadzamy pojęcie kraty i dowodzimy twierdzenie Knastera-Tarskiego o punkcie stałym. Za jego pomocą podajemy alternatywny dowód Lematu Banacha. Następnie omawiamy drzewa, dowodzimy twierdzenie Koniga o istnieniu nieskończonej gałęzi. Na zakończenie wprowadzamy pojęcie tablic semantycznych dla rachunku zdań.

12.    W dodatku C omawiamy system aksjomatów teorii mnogości Zermelo - Fraen-kel’a i zagadnienia związane z niesprzecznością tej teorii.