dr hab. inż. Anna Zamojska-Dzienio
Wydział Matematyki i Nauk Informacyjnych
Zakład Analizy i Teorii Osobliwości
pokój 414, Gmach MiNI

Elementy teorii obliczalności i metamatematyki



Przedmiot obieralny, zgłaszany co 2 lata, poprzednie edycje: semestry zimowe 2013/14 i 2015/16. Trzecia edycja: semestr letni 2017/18.

METAMATEMATYKA zajmuje się badaniem własności formalnych teorii matematycznych metodami logiki matematycznej i matematyki. Badane są własności takie jak: niesprzeczność, rozstrzygalność, zupełność, interpretacje i modele jednej teorii w drugiej.

Twierdzenie Gödla o niezupełności (1931 r.): dowolny system formalny zawierający aksjomaty arytmetyki liczb naturalnych, jest albo zupełny albo spójny i nigdy nie posiada obu tych cech jednocześnie.
Innymi słowy: jeśli można dowodzić prawdziwości wszystkich zdań takiego systemu, to wówczas istnieje w nim pewne zdanie prawdziwe P, którego zaprzeczenie ~P również jest prawdziwe, czyli system jest sprzeczny wewnętrznie. Jeżeli system nie jest sprzeczny, to istnieją w nim zdania, których prawdziwości nie da się wywieść z aksjomatów i twierdzeń rozważanego systemu formalnego.

Wynik ten zakończył definitywnie wieloletnie próby zaksjomatyzowania całej matematyki (problemy Hilberta). W szczególności wynika z niego również, że żadnego komputera nie da się zaprogramować tak, by zdołał on rozstrzygnąć wszystkie problemy matematyczne.

INFORMACJA O PRZEDMIOCIE tutaj; REGULAMIN tutaj

Konspekty wykładów, zestawy zadań

Przy opracowywaniu wykładu oprócz literatury podanej w informacji o przedmiocie, wykorzystuję też materiały dostępne na wazniak.mimuw.edu.pl (Logika matematyczna i teoria mnogości; Logika dla informatyków).

  1. Wykład 1.; Zestaw 1.

  2. Wykład 2.; Zestaw 2.

  3. Wykład 3.; Zestaw 4. (zestaw na 23.03. i 6.04.)

  4. Wykład 4.; Zestaw 3. (zestaw na 16.03.)

  5. Wykład 5.; Zestaw 5.

  6. Wykład 6 i 7.; Zestaw 6.

  7. Wykład 8.;

  8. Wykład 9.;

  9. Wykład 10 i 11.; Zestaw 7.

  10. Wykład 12.;

  11. Wykład 13 i 14.; Zestaw 8.

Maszyny Turinga (dla chętnych, na 25. maja)

Strona główna

email: Y.Xxxxxxxx@elka.pw.edu.pl, gdzie Y to pierwsza litera imienia, Xxxxxxxx to pierwszy człon nazwiska