Markowe wykłady z matematyki Wstęp do matematyki

We Wstępie do matematyki Czytelnik zaznajamia się z elementami logiki matematycznej oraz podstawami teorii mnogości, a przy okazji poznaje:

• podstawowe schematy wnioskowania,
• zastosowanie algebry Boole’a do budowy sieci logicznych,
• dowód istnienia liczb przestępnych,
• ciekawe paradoksy logiczne,
• funkcje o zdumiewających własnościach,
• twierdzenie Gödla.

Poza głównym tekstem książka zawiera 35-stronicowy szkic Rzut oka na historię matematyki, poświęcony głównie dziejom matematyki nowożytnej.

Książka ,,Wstęp do matematyki” jest ósmym tomem cyklu „Markowe wykłady z matematyki”. Może ona służyć, jako podstawowy podręcznik do kursu Wstęp do matematyki prowadzonego na I roku kierunku matematyka politechnik i uniwersytetów. Początkowe 16 wykładów pokrywa się ze standardowym programem takiego kursu. Zaś ostatnie dwa wykłady wprowadzają w tematykę teorii obliczeń oraz wyjaśniają znaczenia twierdzenia Gödla. Podobnie, jak we wcześniejszych tomach cyklu, książka zawiera krótkie notki biograficzne matematyków występujących w tekście.

Spis treści

Przedmowa xi

I Narzędzia logiczne: reguły wnioskowania 1

1 Rachunek zdań 3

1.1 Zdania, spójniki logiczne i tautologie . . . . . . . . . . . . . . . 3

1.2 Reguły wnioskowania a tautologie . . . . . . . . . . . . . . . . 8

1.3 Reguły wnioskowania i dowody formalne . . . . . . . . . . . . . 10

1.4 Arystoteles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Rachunek kwantyfikatorów 14

2.1 Kwantyfikatory . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Cztery reguły wnioskowania . . . . . . . . . . . . . . . . . . . . 19

2.3 Prawa De Morgana i teoria gier* . . . . . . . . . . . . . . . . . 21

3 Indukcja matematyczna i rozumowania pokrewne 25

3.1 Zasada indukcji matematycznej . . . . . . . . . . . . . . . . . . 25

3.2 Indukcja, analogia i odkrywanie wzorów . . . . . . . . . . . . . 29

4 Twierdzenie i dowód 35

4.1 Twierdzenia, definicje i aksjomaty . . . . . . . . . . . . . . . . 36

4.2 Formy dowodu . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

II Narzędzia matematyczne: zbiory, funkcje i relacje 43

5 Algebra zbiorów 45

5.1 Podstawowe działania na zbiorach i diagramy Venna . . . . . . 45

5.2 Algebra zbiorów bez diagramów Venna . . . . . . . . . . . . . . 48

5.3 Różnica symetryczna, iloczyn kartezjański i zbiór potęgowy . . 50

5.4 De Morgan, Boole i inni Anglicy . . . . . . . . . . . . . . . . . 53

6 Funkcje 55

6.1 Funkcje, obrazy i przeciwobrazy . . . . . . . . . . . . . . . . . . 55

6.2 Składanie funkcji i funkcja odwrotna . . . . . . . . . . . . . . . 59

6.3 Szczególne klasy funkcji . . . . . . . . . . . . . . . . . . . . . . 62

6.4 Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7 Rodziny zbiorów i działania nieskończone 65

7.1 Rodziny indeksowane liczbami naturalnymi . . . . . . . . . . . 65

7.2 Przypadek ogólny . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8 Relacje 70

8.1 Relacje dwuargumentowe . . . . . . . . . . . . . . . . . . . . . 70

8.2 Ogólne pojęcie relacji . . . . . . . . . . . . . . . . . . . . . . . . 72

9 Relacje równoważności 74

9.1 Relacje równoważności i podziały . . . . . . . . . . . . . . . . . 74

9.2 Konstrukcja liczb rzeczywistych . . . . . . . . . . . . . . . . . . 78

9.3 Grupy przekształceń i twierdzenie Lagrange’a* . . . . . . . . . 80

9.4 Dedekind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

10 Relacje porządku 83

10.1 Porządki liniowe i porządki częściowe . . . . . . . . . . . . . . . 83

10.2 Izomorfizm porządków . . . . . . . . . . . . . . . . . . . . . . . 87

10.3 Kraty, algebry Boole’a i układy logiczne* . . . . . . . . . . . . 90

III Nieskończoność 95

11 Przeliczalność 97

11.1 Zbiory przeliczalne i zbiory nieprzeliczalne . . . . . . . . . . . . 97

11.2 Pierwsze zastosowania . . . . . . . . . . . . . . . . . . . . . . . 101

11.3 Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

12 Liczby kardynalne i twierdzenie Cantora 104

12.1 Liczby kardynalne . . . . . . . . . . . . . . . . . . . . . . . . . 104

12.2 Twierdzenie Cantora i paradoksy logiczne . . . . . . . . . . . . 107

13 Twierdzenie Cantora-Bernsteina 111

13.1 Podstawowe zastosowania . . . . . . . . . . . . . . . . . . . . . 111

13.2 Dowód twierdzenia Cantora-Bernsteina* . . . . . . . . . . . . . 114

14 Arytmetyka liczb kardynalnych 116

14.1 Dodawanie i mnożenie liczb kardynalnych . . . . . . . . . . . . 116

14.2 Potęgowanie liczb kardynalnych . . . . . . . . . . . . . . . . . . 118

14.3 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

15 Teoria ZF i liczby porządkowe 123

15.1 Aksjomaty teorii ZF . . . . . . . . . . . . . . . . . . . . . . . . 123

15.2 Aksjomat nieskończoności i liczby porządkowe . . . . . . . . . . 127

15.3 Zermelo, G¨odel i Cohen . . . . . . . . . . . . . . . . . . . . . . 130

16 Aksjomat wyboru i jego konsekwencje 132

16.1 Aksjomat wyboru . . . . . . . . . . . . . . . . . . . . . . . . . . 132

16.2 Twierdzenie Zermeli i hipoteza continuum . . . . . . . . . . . . 134

16.3 Lemat Kuratowskiego – Zorna . . . . . . . . . . . . . . . . . . . 136

16.4 Kontrowersje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

16.5 Sierpiński, Tarski i Kuratowski . . . . . . . . . . . . . . . . . . 142

IV Ograniczenia: niezupełność i nierozstrzygalność 145

17 Granice obliczalności i problem stopu 147

17.1 Obliczalność i rozstrzygalność . . . . . . . . . . . . . . . . . . . 147

17.2 Funkcja Rado i problem stopu . . . . . . . . . . . . . . . . . . . 150

17.3 Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

18 Arytmetyka Peana i twierdzenie G¨odla 154

18.1 Arytmetyka jako system formalny . . . . . . . . . . . . . . . . . 154

18.2 Twierdzenie G¨odla . . . . . . . . . . . . . . . . . . . . . . . . . 157

18.3 Hilbert i Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

Epilog 162

Odpowiedzi i wskazówki 164

Rzut oka na historię matematyki 181

Pierwsze 5 000 lat: Egipt, Babilon i cud grecki 183

Wczesna nowożytność (1500-1800):

narodziny analizy i matematyzacja fizyki 188

Wiek XIX: złoty wiek matematyki czystej 196

Wiek XX: specjalizacja, globalizacja i modernizm 207

Indeks 217