Zagadnienia z teorii - wst¸ do logiki i teorii
ep
mnogości
1. Zasada indukcji matematycznej.
2. Aksjomatyka Peano liczb naturalnych (poj¸ pierwotne, sformulowanie
ecia
aksjomatów).
3. Spójniki logiczne (nazwy, oznaczenia oraz definicje z użyciem tabeli wartości
logicznych).
4. Definicja tautologii rachunku zdań, najważniejsze tautologie, przykladowe
dowody.
5. Warunek konieczny, warunek dostateczny, implikacja odwrotna, prawo
kontrapozycji i jego zastosowania.
6. Równość zbiorów (zasada ekstensjonalności).
7. Poj¸ funkcji zdaniowej, przyklady.
ecie
8. Definicja zawierania mi¸ zbiorami, wlasnoÅ›ci inkluzji.
edzy
9. Definicja dzialań na zbiorach (suma, przekrój i różnica dwóch zbiorów),
dopelnienie zbioru.
10. Podstawowe wlasności dzialań na zbiorach, przykladowe dowody.
11. Zbiór pot¸ para uporz¸ adkowanych. Pro-
egowy, adkowana, równość par uporz¸
dukt kartezjański dwóch zbiorów.
12. Kwantyfikatory ogólny i szczególowy, wartość logiczna zdania z kwanty-
fikatorem.
13. Prawa rachunku kwantyfikatorów, przykladowe dowody.
14. Rodzina indeksowana zbiorów. Suma i iloczyn uogólniony indeksowanej
rodziny zbiorów  definicje i wlasności, przykladowe dowody.
15. Definicja funkcji, jej dziedziny i zbioru wartości. Przyklady ciagów zdefi-
¸
niowanych rekurencyjnie.
16. Definicja iniekcji, suriekcji, bijekcji. Superpozycja funkcji, funkcja odwrotna
 definicje.
1
17. Zachowanie iniekcji i suriekcji przez superpozycj¸  twierdzenie z dowo-
e
dem.
18. L¸ superpozycji  dowód.
aczność
19. Definicja obrazu i przeciwobrazu zbioru wzgl¸ funkcji.
edem
20. Wlasności obrazów i przeciwobrazów  przykladowe dowody.
21. Uogólniony iloczyn kartezjański - definicja, szczególne przypadki.
22. Definicja relacji dwuargumentowej. Rodzaje relacji na zbiorze  definicje.
23. Definicja relacji równoważności  przyklady.
24. Definicja klasy abstrakcji, wlasności klas abstrakcji (dowód).
25. Definicja podzialu zbioru. Zasada abstrakcji. Istnienie relacji równoważności,
której zbiór ilorazowy jest danym podzialem.
26. Zastosowanie zasady abstrakcji do konstrukcji liczb calkowitych i wymiernych.
27. Definicja cz¸Å›ciowego porz¸  przyklady. Definicja liniowego porz¸
e adku adku
 przyklady.
28. Elementy najmniejszy, minimalny, najwi¸ maksymalny oraz zwiazki
ekszy, ¸
mi¸ nimi. Diagramy Hassego  przyklady.
edzy
29. Porz¸ produktowy i porz¸ leksykograficzny na X × Y , gdy na X i
adek adek
Y dane s¸ cz¸Å›ciowe (liniowe) porz¸
a e adki.
30. Równoliczność zbiorów  definicja. Zbiory skończone. Wlasności równoliczności
 podać twierdzenia oraz przykladowe dowody.
31. Przyklady nieskończonych zbiorów równolicznych. Uzasadnić równoliczność
N <" N × N oraz (a, b) <" (c, d).
32. Twierdzenie Cantora (o zbiorze pot¸
egowym), dowód.
33. Zbiory przeliczalne  definicja i przyklady, charakteryzacja zbiorów przeliczal-
nych.
34. WlasnoÅ›ci zbiorów przeliczalnych, jedn¸ udowodnić.
a
35. Przyklady zbiorów nieprzeliczalnych, uzasadnić, że dowolny przedzial [a, b]
(dla a < b) jest zbiorem nieprzeliczalnym.
36. Moc zbioru, definicja nierównoÅ›ci mi¸ mocami zbiorów. Podać twierdze-
edzy
nie charakteryzuj¸ |A| d" |B|.
ace
37. WlasnoÅ›ci nierównoÅ›ci mi¸ mocami zbiorów  podać twierdzenie.
edzy
38. Twierdzenie Cantora-Bernsteina, idea dowodu.
39. Aksjomat wyboru. Lemat Kuratowskiego-Zorna.
2