Granice matematyki

Opis

Na Kongresie Matematycznym w 1900 r. David Hilbert przedstawił swój program naprawy matematyki, którego głównym celem miało być sformalizowanie tej dziedziny w ścisłym języku logiki oraz stworzenie ogólnych metod umożliwiających automatyczne stwierdzanie prawdziwości bądź fałszu dowolnego zdania wyrażonego w tym języku. Jego mottem było:

For us there is no ignorabimus, and in my opinion none whatever in natural science. In opposition to the foolish ignorabimus our slogan shall be: Wir müssen wissen — wir werden wissen! ('We must know — we will know!')

Nadchodzące stulecie pokazało, że ten optymizm jest nieuzasadniony, a trzy spośród 23 problemów wskazanych przez Hilberta jako najważniejsze zadania matematyki doczekało się nieoczekiwanych wyników negatywnych. Okazało się m.in., że:

• dla każdego "sensownego" formalnego systemu dowodzenia istnieją prawdziwe zdania, których nie można udowodnić w ramach tego systemu…
• …i mogą to być podstawowe i naturalne pytania; w szczególności, hipotezy continuum nie da się ani udowodnić, ani obalić w ramach standardowej teorii mnogości (1. problem Hilberta),
• absolutna pewność jest nieosiągalna: nie da się dowieść niesprzeczności żadnego systemu formalnego zawierającego arytmetykę liczb naturalnych w ramach tego systemu (2. problem Hilberta)
• istnieją naturalne problemy, dla których nie istnieją żadne rozwiązujące je algorytmy,
• w szczególności, nie istnieje ogólna metoda stwierdzania, czy dane równanie diofantyczne (czyli wielomian wielu zmiennych, dla którego szukamy całkowitych pierwiastków) o całkowitych współczynnikach ma rozwiązanie (10. problem Hilberta).

Pojawienie się komputerów przyniosło matematyce nowe możliwości, ale też nowe wyzwania. Nasila się przekonanie, że złożoność obliczeniowa (nieformalnie - miara trudności problemów dla maszyny Turinga) dobrze wyraża również podatność problemów dla matematycznego poznania, że istnienie wielomianowych algorytmów jest w nierozłączny sposób związane z możliwym stopniem naszego zrozumienia danego problemu i opisania jego rozwiązań. Teoria złożoności obliczeniowej, będąca drugą, "mroczną" stroną algorytmiki, stała się jedną z ważniejszych dziedzin współczesnej matematyki i jest źródłem jednego z najtrudniejszych i najistotniejszych problemów otwartych - niesławnego problemu P?=NP.

Na zajęciach przyjrzymy się "granicom matematyki" i poznamy najważniejsze negatywne wyniki z przecięcia logiki, teorii obliczeń i teorii złożoności.

Program

Na początku chciałabym wprowadzić i umotywować kilka podstawowych pojęć i wyników z logiki, teorii obliczeń i teorii złożoności. Na pewno pojawi się:

• tw. Goedla i tw. Tarskiego o niedefiniowalności prawdy,
• nierozstrzygalność problemu stopu, tw. Rice'a,
• sformułowanie problemu P=?NP i stojące za nim intuicje,
• tw. o hierarchii złożoności czasowej
• tw. Cooka

Później, w zależności od zainteresowań uczestników, spróbujemy zgłębić niektóre z poniższych zagadnień:

• forcing, czyli potężna metoda dowodzenia niezależności,
• dowód tw. Matjasiewicza, czyli negatywna odpowiedź na 10. problem Hilberta,
• powody, dla których problem P=?NP jest tak trudny (najważniejsze wyniki z jego okolic są typu "dana klasa metod nie rozwiąze tego problemu"!); przedyskujemy też kwestię, czy ten problem może okazać się w jakimś sensie niedowodliwy,
• związek pomiędzy spektrami (czyli zbiorami możliwych mocy modeli) formuł logiki pierwszego rzędu a złożonością obliczeniową,
• ważne wyniki negatywne w różnych działach informatyki teoretycznej: algorytmach aproksymacyjnych (tw. PCP), kompresji (złożoność Kołmogorowa) czy teorii uczenia maszynowego.

Chciałabym, żeby zajęcia były możliwie interaktywne; twierdzenia będziemy wspólnie dowodzić po kawałku. Głównym celem będzie przekazanie Wam przekonania, że logika, teoria obliczeń i teoria złożoności są ważne i ciekawe! :)

Wymagania

Ogólne obycie matematyczne, zwłaszcza jeśli chodzi o logikę (możecie np. przejrzeć ten skrypt).

Zadania kwalifikacyjne

Rozwiązania zadań przesyłajcie na moc.liamg|sytlosk#moc.liamg|sytlosk. Chętnie odpowiem też na wszelkie pytania.

1. Zbadaj, czy następujące formuły są tautologiami i czy są spełnialne (p i q to dowolne predykaty):
   1. $\exists x \forall y (p(x) \vee q(y) ) \rightarrow \forall y (p(y) \vee q(y))$
   2. $\exists x (\forall y q(y) \rightarrow p(x)) \rightarrow \exists x \forall y (q(y) \rightarrow p(x))$
2. Dwa zbiory nazywamy równolicznymi, jeśli istnieje między nimi bijekcja, czyli funkcja różnowartościowa i "na". Zbiór równoliczny ze zbiorem liczb naturalnych nazywamy przeliczalnym. (Przykłady i odrobinę intuicji można znaleźć na wikipedii). Pokaż, że:
   1. zbiór liczb wymiernych $\mathbb{Q}$ jest przeliczalny,
   2. zbiór liczb rzeczywistych $\mathbb{R}$ nie jest przeliczalny.
3. Pokaż, że jeśli istnieje różnowartościowa funkcja $f: A \rightarrow B$ oraz różnowartościowa funkcja $g: B \rightarrow A$, to zbiory A i B są równoliczne.
4. Napisz na Maszynę Turinga (być może lepiej wyjaśnione tutaj) program dodający 1 do liczby zapisanej:
   1. w zapisie unarnym
   2. w zapisie binarnym
5. Redukcją z problemu A do B nazywamy obliczalną w czasie wielomianowym funkcję $f:\{0,1\}* \rightarrow \{0,1\}*$ taką, że $x \in A \Leftrightarrow f(x) \in B$ (Intuicyjnie — chcemy instancję jednego problemu przekształcić w instancję drugiego problemu zachowując odpowiedź.) Pokaż, że istnieje redukcja z problemu Clique (problem sprawdzania dla danego grafu G i liczby k, czy w G jest klika rozmiaru co najmniej k) do problemu:
   1. Independent Set (problem sprawdzania dla danego grafu G i liczby k, czy w G jest zbiór niezależny rozmiaru co najmniej k)
   2. Vertex Cover (problem sprawdzania dla danego grafu G i liczby k, czy w G jest pokrycie wierzchołkowe rozmiaru co najwyżej k).