Logika matematyczna - Mathematical logic

Logika matematyczna to nauka o logice w matematyce . Główne podobszary obejmują modelu teorii , teoria dowodu , teorii mnogości i teorii rekursji . Badania nad logiką matematyczną zwykle dotyczą właściwości matematycznych formalnych systemów logiki, takich jak ich moc ekspresyjna lub dedukcyjna. Może jednak również obejmować wykorzystanie logiki do scharakteryzowania prawidłowego rozumowania matematycznego lub ustanowienia podstaw matematyki .

Od samego początku logika matematyczna zarówno przyczyniła się, jak i była motywowana badaniem podstaw matematyki. Badania te rozpoczęły się pod koniec XIX wieku wraz z opracowaniem ram aksjomatycznych dla geometrii , arytmetyki i analizy . Na początku 20 wieku został ukształtowany przez David Hilbert „s programu w celu udowodnienia zgodności fundamentalnych teorii. Wyniki Kurta Gödla , Gerharda Gentzena i innych zapewniły częściowe rozwiązanie programu i wyjaśniły kwestie związane z udowodnieniem spójności. Prace nad teorią mnogości wykazały, że prawie każdą zwykłą matematykę można sformalizować w kategoriach zbiorów, chociaż istnieją pewne twierdzenia, których nie można udowodnić w powszechnych systemach aksjomatów teorii mnogości. Współczesna praca nad podstawami matematyki często koncentruje się na ustaleniu, które części matematyki można sformalizować w poszczególnych systemach formalnych (jak w matematyce odwrotnej ), zamiast próbować znaleźć teorie, w których można rozwijać całą matematykę.

Podpola i zakres

Handbook of Mathematical Logic w 1977 roku sprawia, że ostry podział współczesnej logiki matematycznej w czterech obszarach:

  1. teoria mnogości
  2. teoria modeli
  3. teoria rekurencji i
  4. teoria dowodu i matematyka konstruktywna (traktowane jako części jednego obszaru).

Każdy obszar ma inny cel, chociaż wiele technik i wyników jest wspólnych dla wielu obszarów. Granice między tymi dziedzinami oraz linie oddzielające logikę matematyczną od innych dziedzin matematyki nie zawsze są ostre. Twierdzenie Gödla jest nie tylko kamieniem milowym w teorii rekurencji i teorii dowodu, ale także doprowadziło do twierdzenia Löba w logice modalnej. Metoda forsowania stosowana jest w teorii mnogości, teorii modeli i teorii rekurencji, a także w badaniach matematyki intuicjonistycznej.

Matematyczna dziedzina teorii kategorii wykorzystuje wiele formalnych metod aksjomatycznych i obejmuje badanie logiki kategorycznej , ale teoria kategorii nie jest zwykle uważana za poddziedzinę logiki matematycznej. Ze względu na jej zastosowanie w różnych dziedzinach matematyki matematycy, w tym Saunders Mac Lane , zaproponowali teorię kategorii jako podstawowy system matematyki, niezależny od teorii mnogości. Podstawy te wykorzystują toposy , które przypominają uogólnione modele teorii mnogości, które mogą wykorzystywać logikę klasyczną lub nieklasyczną.

Historia

Logika matematyczna pojawiła się w połowie XIX wieku jako poddziedzina matematyki, odzwierciedlająca zbieg dwóch tradycji: formalnej logiki filozoficznej i matematyki. „Logika matematyczna, zwana także 'logistyką', 'logiką symboliczną', ' algebrą logiki ', a ostatnio po prostu 'logiką formalną', jest zbiorem teorii logicznych opracowanych w ciągu ostatniego [XIX] wieku za pomocą sztucznej notacji i rygorystycznej metody dedukcyjnej." Przed tym pojawieniem się logikę studiowano za pomocą retoryki , kalkulacji , sylogizmu i filozofii . W pierwszej połowie XX wieku nastąpiła eksplozja fundamentalnych wyników, której towarzyszyła ożywiona debata na temat podstaw matematyki.

Wczesna historia

Teorie logiki rozwinęły się w wielu kulturach historycznych, w tym w Chinach , Indiach , Grecji i świecie islamu . Greckie metody, w szczególności logika Arystotelesa (lub logika terminów) w Organonie , przez tysiąclecia znalazły szerokie zastosowanie i akceptację w zachodniej nauce i matematyce. W stoicy , zwłaszcza Chrysippus rozpoczął rozwój kwantyfikatorów logicznych . W XVIII-wiecznej Europie próby ujęcia operacji logiki formalnej w sposób symboliczny lub algebraiczny podejmowali matematycy filozoficzni, w tym Leibniz i Lambert , ale ich prace pozostały odizolowane i mało znane.

19 wiek

W połowie XIX wieku George Boole, a następnie Augustus De Morgan przedstawili systematyczne matematyczne podejście do logiki. Ich praca, oparta na pracach algebraistów, takich jak George Peacock , rozszerzyła tradycyjną arystotelesowską doktrynę logiki na wystarczające ramy do badania podstaw matematyki . Charles Sanders Peirce później oparł się na pracy Boole'a, aby opracować logiczny system relacji i kwantyfikatorów, który opublikował w kilku pracach od 1870 do 1885.

Gottlob Frege przedstawił niezależny rozwój logiki za pomocą kwantyfikatorów w swoim Begriffsschrift , opublikowanym w 1879 roku, dziele powszechnie uważanym za punkt zwrotny w historii logiki. Dzieło Fregego pozostało jednak niejasne, dopóki Bertrand Russell nie zaczął go promować na przełomie wieków. Notacja dwuwymiarowa, którą opracował Frege, nigdy nie została powszechnie przyjęta i nie jest stosowana we współczesnych tekstach.

W latach 1890-1905 Ernst Schröder opublikował w trzech tomach Vorlesungen über die Algebra der Logik . Praca ta podsumowała i rozszerzyła pracę Boole'a, De Morgana i Peirce'a i była wszechstronnym odniesieniem do logiki symbolicznej, jak rozumiano ją pod koniec XIX wieku.

Teorie fundamentalne

Obawy, że matematyka nie została zbudowana na właściwych podstawach, doprowadziły do ​​rozwoju systemów aksjomatycznych dla podstawowych dziedzin matematyki, takich jak arytmetyka, analiza i geometria.

W logice termin arytmetyka odnosi się do teorii liczb naturalnych . Giuseppe Peano opublikował zestaw aksjomatów dla arytmetyki, które zaczęły nosić jego imię ( aksjomaty Peano ), używając odmiany logicznego systemu Boole'a i Schrödera, ale dodając kwantyfikatory. Peano nie wiedział w tym czasie o pracy Frege'a. Mniej więcej w tym samym czasie Richard Dedekind wykazał, że liczby naturalne charakteryzują się unikalnymi właściwościami indukcyjnymi . Dedekind zaproponował inną charakterystykę, której brakowało formalno-logicznego charakteru aksjomatów Peano. Praca Dedekinda wykazała jednak twierdzenia niedostępne w systemie Peano, w tym jednoznaczność zbioru liczb naturalnych (aż do izomorfizmu) oraz rekurencyjne definicje dodawania i mnożenia z funkcji następnika i indukcji matematycznej.

W połowie XIX wieku ujawniono błędy w aksjomatach Euklidesa dotyczących geometrii. Oprócz niezależności równoległego postulatu , ustanowionego przez Nikołaja Łobaczewskiego w 1826 r., matematycy odkryli, że pewne twierdzenia przyjęte przez Euklidesa za oczywiste nie były w rzeczywistości udowodnione z jego aksjomatów. Wśród nich jest twierdzenie, że prosta zawiera co najmniej dwa punkty, lub że okręgi o tym samym promieniu, których środki są oddzielone tym promieniem, muszą się przecinać. Hilbert opracował kompletny zestaw aksjomatów dla geometrii , bazując na wcześniejszych pracach Pascha. Sukces w aksjomatyzowaniu geometrii zmotywował Hilberta do poszukiwania pełnych aksjomatyzacji innych dziedzin matematyki, takich jak liczby naturalne i prosta rzeczywista . Okazało się, że jest to główny obszar badań w pierwszej połowie XX wieku.

Wiek XIX przyniósł wielkie postępy w teorii analizy rzeczywistej , w tym w teoriach zbieżności funkcji i szeregach Fouriera . Matematycy, tacy jak Karl Weierstrass, zaczęli konstruować funkcje rozciągające intuicję, takie jak nigdzie nieróżnicowalne funkcje ciągłe . Wcześniejsze koncepcje funkcji jako reguły do ​​obliczeń lub gładkiego wykresu nie były już wystarczające. Weierstrass zaczął opowiadać się za arytmetyzacją analizy , która dążyła do aksjomatyzowania analizy za pomocą właściwości liczb naturalnych. Nowoczesna (ε, δ)-definicja funkcji granicznych i ciągłych została już opracowana przez Bolzano w 1817 roku, ale pozostała stosunkowo nieznana. Cauchy w 1821 zdefiniował ciągłość w kategoriach nieskończenie małych (patrz Cours d'Analyse, s. 34). W 1858 r. Dedekind zaproponował definicję liczb rzeczywistych w postaci cięć Dedekinda liczb wymiernych, definicję wciąż stosowaną we współczesnych tekstach.

Georg Cantor rozwinął podstawowe koncepcje teorii zbiorów nieskończonych. Jego wczesne wyniki rozwinęły teorię kardynalności i dowiodły, że liczby rzeczywiste i naturalne mają różne kardynalność. W ciągu następnych dwudziestu lat Cantor rozwinął teorię liczb nadskończonych w serii publikacji. W 1891 opublikował nowy dowód niepoliczalnoœci liczb rzeczywistych, który wprowadził argument przekątny i użył tej metody do udowodnienia twierdzenia Cantora, że żaden zbiór nie może mieć takiej samej kardynalności jak jego zbiór mocy . Cantor wierzył, że każdy zestaw można dobrze uporządkować , ale nie był w stanie przedstawić dowodu na ten wynik, pozostawiając go jako otwarty problem w 1895 roku.

XX wiek

W pierwszych dziesięcioleciach XX wieku głównymi obszarami badań były teoria mnogości i logika formalna. Odkrycie paradoksów w nieformalnej teorii mnogości spowodowało, że niektórzy zaczęli się zastanawiać, czy sama matematyka jest niespójna, i szukać dowodów na spójność.

W 1900 Hilbert przedstawił słynną listę 23 problemów na następne stulecie. Pierwsze dwa z nich miały rozwiązać hipotezę kontinuum i udowodnić, odpowiednio, spójność elementarnej arytmetyki; dziesiątym było stworzenie metody, która mogłaby decydować, czy wielowymiarowe równanie wielomianowe na liczbach całkowitych ma rozwiązanie. Późniejsze prace mające na celu rozwiązanie tych problemów ukształtowały kierunek logiki matematycznej, podobnie jak próba rozwiązania problemu Entscheidungsproblemu Hilberta, podjęta w 1928 roku. Problem ten wymagał procedury, która decydowałaby, na podstawie sformalizowanego zdania matematycznego, czy zdanie jest prawdziwe, czy fałszywe.

Teoria mnogości i paradoksy

Ernst Zermelo dał dowód na to, że każdy zestaw można dobrze zamówić , czego nie udało się uzyskać Georgowi Cantorowi . Aby uzyskać dowód, Zermelo wprowadził aksjomat wyboru , który wywołał gorącą debatę i badania wśród matematyków i pionierów teorii mnogości. Natychmiastowa krytyka metody skłoniła Zermelo do opublikowania drugiej prezentacji swojego wyniku, bezpośrednio odnoszącej się do krytyki jego dowodu. Ten artykuł doprowadził do powszechnej akceptacji aksjomatu wyboru w społeczności matematycznej.

Sceptycyzm wobec aksjomatu wyboru został wzmocniony przez niedawno odkryte paradoksy w naiwnej teorii mnogości . Cesare Burali-Forti jako pierwszy stwierdził paradoks: paradoks Burali-Forti pokazuje, że zbiór wszystkich liczb porządkowych nie może tworzyć zbioru. Wkrótce potem Bertrand Russell odkrył paradoks Russella w 1901 roku, a Jules Richard odkrył paradoks Richarda .

Zermelo dostarczył pierwszego zestawu aksjomatów dla teorii mnogości. Te aksjomaty, wraz z dodatkowym aksjomatem zastąpienia zaproponowanym przez Abrahama Fraenkla , są obecnie nazywane teorią mnogości Zermelo-Fraenkla (ZF). Aksjomaty Zermelo zawierały zasadę ograniczenia wielkości, aby uniknąć paradoksu Russella.

W 1910 roku ukazał się pierwszy tom Principia Mathematica Russella i Alfreda North Whiteheadów . Ta przełomowa praca rozwinęła teorię funkcji i kardynalności w całkowicie formalnych ramach teorii typów , które Russell i Whitehead opracowali w celu uniknięcia paradoksów. Principia Mathematica jest uważana za jedną z najbardziej wpływowych prac XX wieku, chociaż ramy teorii typów nie okazały się popularne jako podstawowa teoria matematyki.

Fraenkel dowiódł, że aksjomat wyboru nie może być udowodniony z aksjomatów teorii mnogości Zermelo z urelementami . Późniejsze prace Paula Cohena pokazały, że dodawanie urelementów nie jest potrzebne, a aksjomat wyboru jest niedowodliwy w ZF. Dowód Cohena rozwinął metodę forsowania , która jest obecnie ważnym narzędziem do ustalania wyników niezależności w teorii mnogości.

Logika symboliczna

Leopold Löwenheim i Thoralf Skolem uzyskali twierdzenie Löwenheima-Skolema , które mówi, że logika pierwszego rzędu nie może kontrolować kardynalności struktur nieskończonych. Skolem zdał sobie sprawę, że twierdzenie to będzie miało zastosowanie do formalizacji pierwszego rzędu teorii mnogości, i że implikuje, że każda taka formalizacja ma model przeliczalny . Ten sprzeczny z intuicją fakt stał się znany jako paradoks Skolema .

W swojej pracy doktorskiej Kurt Gödel udowodnił twierdzenie o zupełności , które ustala zgodność składni i semantyki w logice pierwszego rzędu. Gödel użył twierdzenia o zupełności do udowodnienia twierdzenia o zwartości , wykazując skończoną naturę logicznej konsekwencji pierwszego rzędu . Wyniki te pomogły ustalić logikę pierwszego rzędu jako dominującą logikę stosowaną przez matematyków.

W 1931 Gödel opublikował On Formally Undecidable Propositions of Principia Mathematica and Related Systems , który dowiódł niekompletności (w innym znaczeniu tego słowa) wszystkich wystarczająco mocnych, skutecznych teorii pierwszego rzędu. Wynik ten, znany jako twierdzenie o niezupełności Gödla , ustanawia poważne ograniczenia aksjomatycznych podstaw matematyki, uderzając mocno w program Hilberta. Pokazał niemożność dostarczenia dowodu spójności arytmetyki w ramach jakiejkolwiek formalnej teorii arytmetyki. Hilbert jednak przez pewien czas nie uznawał znaczenia twierdzenia o niezupełności.

Twierdzenie Gödla pokazuje, że dowód niesprzeczności jakiegokolwiek wystarczająco silnego, efektywnego systemu aksjomatów nie może być uzyskany w samym systemie, jeśli jest on niesprzeczny, ani w żadnym słabszym systemie. Pozostawia to otwartą możliwość dowodu spójności, którego nie można sformalizować w ramach rozważanego przez nich systemu. Gentzen udowodnił zgodność arytmetyki za pomocą systemu skończonego wraz z zasadą indukcji pozaskończonej . Wyniki Gentzena wprowadziły idee eliminacji cięcia i liczby porządkowe teorii dowodu , które stały się kluczowymi narzędziami w teorii dowodu. Gödel podał inny dowód niesprzeczności, który redukuje spójność arytmetyki klasycznej do arytmetyki intuicjonistycznej w wyższych typach.

Pierwszy podręcznik logiki symbolicznej dla laika został napisany przez Lewisa Carrolla, autora Alicji w Krainie Czarów, w 1896 roku.

Początki pozostałych gałęzi

Alfred Tarski opracował podstawy teorii modeli .

Od 1935 roku grupa wybitnych matematyków współpracowała pod pseudonimem Nicolas Bourbaki, aby opublikować Éléments de mathématique , serię encyklopedycznych tekstów matematycznych. Teksty te, pisane w stylu surowym i aksjomatycznym, kładły nacisk na rygorystyczną prezentację i podstawy mnogościowe. Terminologia ukuta w tych tekstach, taka jak słowa bijection , injection i surjection oraz podstawy teorii mnogości , których używały teksty, były szeroko stosowane w matematyce.

Badanie obliczalności stało się znane jako teoria rekurencji lub teoria obliczalności , ponieważ wczesne formalizacje Gödla i Kleene opierały się na rekurencyjnych definicjach funkcji. Kiedy te definicje zostały pokazane jako równoważne z formalizacją Turinga z udziałem maszyn Turinga , stało się jasne, że odkryto nową koncepcję – funkcję obliczalną – i że ta definicja była wystarczająco solidna, aby dopuścić liczne niezależne charakteryzacje. W swojej pracy nad twierdzeniami o niezupełności w 1931 r. Gödelowi brakowało rygorystycznej koncepcji skutecznego systemu formalnego; od razu zdał sobie sprawę, że nowe definicje obliczalności mogą być użyte do tego celu, co pozwala mu na ogólne sformułowanie twierdzeń o niezupełności, które mogą być implikowane tylko w oryginalnej pracy.

Liczne wyniki w teorii rekurencji uzyskali w latach 40. XX wieku Stephen Cole Kleene i Emil Leon Post . Kleene wprowadził koncepcje względnej obliczalności, zapowiedziane przez Turinga, oraz hierarchię arytmetyczną . Kleene później uogólnił teorię rekurencji na funkcjonały wyższego rzędu. Kleene i Georg Kreisel badali formalne wersje matematyki intuicjonistycznej, szczególnie w kontekście teorii dowodu.

Formalne systemy logiczne

W swej istocie logika matematyczna zajmuje się pojęciami matematycznymi wyrażonymi za pomocą formalnych systemów logicznych . Systemy te, choć różnią się wieloma szczegółami, mają wspólną właściwość rozpatrywania tylko wyrażeń w ustalonym języku formalnym. Systemy logiki zdań i logiki pierwszego rzędu są obecnie najszerzej badane ze względu na ich stosowalność do podstaw matematyki oraz ze względu na ich pożądane własności w zakresie teorii dowodu. Badane są również silniejsze logiki klasyczne, takie jak logika drugiego rzędu lub logika nieskończoności, a także logiki nieklasyczne, takie jak logika intuicjonistyczna .

Logika pierwszego rzędu

Logika pierwszego rzędu to szczególny formalny system logiki . Jego składnia obejmuje wyłącznie wyrażenia skończone jako dobrze uformowane formuły , podczas gdy jego semantyka charakteryzuje się ograniczeniem wszystkich kwantyfikatorów do ustalonej dziedziny dyskursu .

Wczesne wyniki logiki formalnej ustaliły ograniczenia logiki pierwszego rzędu. Twierdzenie Löwenheima-Skolema (1919) wykazało, że jeśli zbiór zdań w policzalnym języku pierwszego rzędu ma nieskończony model, to ma co najmniej jeden model każdej nieskończonej kardynalności. To pokazuje, że zbiór aksjomatów pierwszego rzędu nie jest w stanie scharakteryzować liczb naturalnych, liczb rzeczywistych lub jakiejkolwiek innej struktury nieskończonej aż do izomorfizmu . Ponieważ celem wczesnych badań fundamentalnych było stworzenie teorii aksjomatycznych dla wszystkich części matematyki, to ograniczenie było szczególnie wyraźne.

Twierdzenie Gödla o zupełności ustaliło równoważność między semantycznymi i syntaktycznymi definicjami logicznej konsekwencji w logice pierwszego rzędu. Pokazuje, że jeśli dane zdanie jest prawdziwe w każdym modelu, który spełnia określony zbiór aksjomatów, to musi istnieć skończona dedukcja tego zdania z aksjomatów. Twierdzenie zwartość pierwszy pojawił się jako lematu w dowód Gödla twierdzenia kompletności i zajęło wiele lat przed logicy uchwycić jego znaczenie i zaczął stosować go rutynowo. Mówi, że zbiór zdań ma model wtedy i tylko wtedy, gdy każdy skończony podzbiór ma model, czyli innymi słowy, że niespójny zbiór formuł musi mieć skończony niespójny podzbiór. Twierdzenia o zupełności i zwartości pozwalają na zaawansowaną analizę konsekwencji logicznych w logice pierwszego rzędu oraz rozwój teorii modeli i są kluczowym powodem znaczenia logiki pierwszego rzędu w matematyce.

Twierdzenia Gödla o niezupełności ustanawiają dodatkowe ograniczenia aksjomatyzacji pierwszego rzędu. Te pierwsze niekompletność twierdzenie stwierdza, że dla każdego spójne, skutecznie podane (zdefiniowanych poniżej) układ logiczny, który jest zdolny do interpretowania arytmetyki, istnieje wskazanie, że jest prawdziwe (w tym sensie, że zachodzi dla liczb naturalnych), ale nie można udowodnić w ciągu że logiczne systemu (co rzeczywiście może zawieść w niektórych niestandardowych modelach arytmetyki, które mogą być zgodne z systemem logicznym). Na przykład w każdym systemie logicznym zdolnym do wyrażenia aksjomatów Peano , zdanie Gödla obowiązuje dla liczb naturalnych, ale nie może być udowodnione.

Tutaj mówi się, że system logiczny jest skutecznie dany, jeśli możliwe jest rozstrzygnięcie, przy danej formule w języku systemu, czy formuła jest aksjomatem, a taki, który może wyrażać aksjomaty Peano, nazywany jest „wystarczająco silnym”. W przypadku zastosowania do logiki pierwszego rzędu, pierwsze twierdzenie o niezupełności implikuje, że każda wystarczająco silna, spójna, efektywna teoria pierwszego rzędu ma modele, które nie są elementarnie równoważne , silniejsze ograniczenie niż to ustalone przez twierdzenie Löwenheima-Skolema. Te drugie niekompletność twierdzenie stwierdza, że nie ma wystarczająco silny, spójny, skuteczny system aksjomatów arytmetyki mogą udowodnić swoją własną konsystencję, który został zinterpretowany, aby pokazać, że Program Hilberta nie może być osiągnięty.

Inne logiki klasyczne

Bada się wiele logik poza logiką pierwszego rzędu. Należą do nich logiki nieskończoności , które pozwalają formułom dostarczać nieskończonej ilości informacji, oraz logiki wyższego rzędu , które zawierają część teorii mnogości bezpośrednio w swojej semantyce.

Najlepiej zbadaną logiką nieskończoności jest . W tej logice kwantyfikatory mogą być zagnieżdżone tylko do skończonych głębokości, jak w logice pierwszego rzędu, ale formuły mogą zawierać w sobie skończone lub przeliczalnie nieskończone koniunkcje i alternatywy. Tak więc na przykład można powiedzieć, że obiekt jest liczbą całkowitą, używając formuły takiej jak

Logiki wyższego rzędu pozwalają na kwantyfikację nie tylko elementów domeny dyskursu , ale podzbiorów domeny dyskursu, zbiorów takich podzbiorów i innych obiektów wyższego typu. Semantyka jest zdefiniowana w taki sposób, że zamiast oddzielnej domeny dla każdego kwantyfikatora wyższego typu, który ma się mieścić, kwantyfikatory obejmują wszystkie obiekty odpowiedniego typu. Logiki badane przed rozwojem logiki pierwszego rzędu, na przykład logika Fregego, miały podobne aspekty mnogościowe. Chociaż logiki wyższego rzędu są bardziej wyraziste, pozwalając na pełną aksjomatyzację struktur, takich jak liczby naturalne, nie spełniają analogii twierdzeń o zupełności i zwartości z logiki pierwszego rzędu, a zatem są mniej podatne na analizę dowodową.

Innym rodzajem logiki są logiczne stałoprzecinkową s, które pozwalajądefinicje indukcyjne, jak ktoś pisze dlafunkcji pierwotnie rekurencyjnych.

Można formalnie zdefiniować rozszerzenie logiki pierwszego rzędu — pojęcie, które obejmuje wszystkie logiki w tej sekcji, ponieważ zachowują się one jak logika pierwszego rzędu w pewnych podstawowych aspektach, ale nie obejmuje wszystkich logik w ogóle, np. nie obejmuje intuicjonizmu, logika modalna lub rozmyta .

Twierdzenie Lindströma implikuje, że jedynym rozszerzeniem logiki pierwszego rzędu spełniającym zarówno twierdzenie o zwartości, jak i w dół twierdzenie Löwenheima-Skolema jest logika pierwszego rzędu.

Logika nieklasyczna i modalna

Logiki modalne zawierają dodatkowe operatory modalne, takie jak operator, który stwierdza, że ​​konkretna formuła jest nie tylko prawdziwa, ale z konieczności prawdziwa. Chociaż logika modalna nie jest często wykorzystywana do aksjomatyzacji matematyki, była wykorzystywana do badania właściwości dowodliwości pierwszego rzędu i wymuszania teorii mnogości.

Logika intuicjonistyczna została opracowana przez Heytinga w celu zbadania programu intuicjonizmu Brouwera, w którym sam Brouwer unikał formalizacji. Logika intuicjonistyczna konkretnie nie obejmuje prawa wyłączonego środka , które stanowi, że każde zdanie jest albo prawdziwe, albo jego zaprzeczenie jest prawdziwe. Praca Kleene'a z teorią dowodu logiki intuicjonistycznej pokazała, że ​​z dowodów intuicjonistycznych można odzyskać konstruktywne informacje. Na przykład każda funkcja całkowita, którą można udowodnić w arytmetyce intuicjonistycznej, jest obliczalna ; nie jest to prawdą w klasycznych teoriach arytmetycznych, takich jak arytmetyka Peano .

Logika algebraiczna

Logika algebraiczna wykorzystuje metody algebry abstrakcyjnej do badania semantyki logik formalnych. Podstawowym przykładem jest użycie algebr Boole'a do reprezentowania wartości prawdziwości w klasycznej logice zdań oraz użycie algebr Heytinga do reprezentowania wartości prawdziwości w intuicjonistycznej logice zdań. Silniejsze logiki, takie jak logika pierwszego rzędu i logika wyższego rzędu, są badane przy użyciu bardziej skomplikowanych struktur algebraicznych, takich jak algebry cylindryczne .

Teoria mnogości

Teoria mnogości to nauka o zbiorach , które są abstrakcyjnymi zbiorami obiektów. Wiele podstawowych pojęć, takich jak liczby porządkowe i kardynalne, zostało opracowanych nieformalnie przez Cantora przed rozwinięciem formalnych aksjomatyzacji teorii mnogości. Pierwsze takie dzana w związku z Zermelo został rozszerzony lekko się Zermelo-Fraenkel teorii zbiorów (ZF), który jest najczęściej używany podstawowy teorią matematyki.

Zaproponowano inne formalizacje teorii mnogości, w tym teorię mnogości von Neumanna-Bernaysa-Gödla (NBG), teorię mnogości Morse'a-Kelleya (MK) i New Foundations (NF). Spośród nich ZF, NBG i MK są podobne w opisie skumulowanej hierarchii zbiorów. Nowe Fundacje mają inne podejście; dopuszcza obiekty takie jak zbiór wszystkich zbiorów kosztem ograniczeń jego aksjomatów istnienia zbioru. System teorii mnogości Kripkego-Platka jest ściśle związany z uogólnioną teorią rekurencji.

Dwa słynne stwierdzenia w teorii mnogości to aksjomat wyboru i hipoteza continuum . Aksjomat wyboru, po raz pierwszy sformułowany przez Zermelo, okazał się niezależny od ZF przez Fraenkela, ale stał się powszechnie akceptowany przez matematyków. Stwierdza, że ​​przy danej kolekcji niepustych zestawów istnieje jeden zestaw C, który zawiera dokładnie jeden element z każdego zestawu w kolekcji. Mówi się, że zestaw C „wybiera” jeden element z każdego zestawu w kolekcji. Chociaż możliwość dokonania takiego wyboru jest przez niektórych uważana za oczywistą, ponieważ każdy zbiór w zbiorze jest niepusty, brak ogólnej, konkretnej reguły, według której można dokonać wyboru, czyni aksjomat niekonstruktywnym. Stefan Banach i Alfred Tarski pokazali, że aksjomat wyboru może posłużyć do rozłożenia bryły kuli na skończoną liczbę kawałków, które następnie można przestawić, bez skalowania, w dwie bryły o oryginalnej wielkości. Twierdzenie to, znane jako paradoks Banacha–Tarskiego , jest jednym z wielu sprzecznych z intuicją wyników aksjomatu wyboru.

Hipoteza continuum, po raz pierwszy zaproponowana jako przypuszczenie przez Cantora, została wymieniona przez Davida Hilberta jako jeden z jego 23 problemów w 1900 roku. Gödel wykazał, że hipotezy continuum nie można obalić z aksjomatów teorii mnogości Zermelo-Fraenkla (z aksjomatem lub bez niego). wyboru), poprzez rozwijanie dającego się skonstruować uniwersum teorii mnogości, w którym hipoteza continuum musi być słuszna. W 1963 Paul Cohen wykazał, że hipotezy continuum nie można udowodnić na podstawie aksjomatów teorii mnogości Zermelo-Fraenkla. Ten wynik niezależności nie rozstrzygnął jednak całkowicie kwestii Hilberta, ponieważ możliwe jest, że nowe aksjomaty teorii mnogości mogą rozwiązać tę hipotezę. Ostatnie prace w tym kierunku prowadził W. Hugh Woodin , chociaż ich znaczenie nie jest jeszcze jasne.

Współczesne badania nad teorią mnogości obejmują badanie wielkich kardynałów i determinacji . Wielcy kardynałowie to liczby kardynalne o szczególnych właściwościach tak silnych, że istnienia takich kardynałów nie można udowodnić w ZFC. Istnienie najmniejszego dużego kardynała, zwykle badanego, niedostępnego kardynała , już sugeruje spójność ZFC. Pomimo tego, że wielcy kardynałowie mają niezwykle wysoką kardynalność , ich istnienie ma wiele konsekwencji dla struktury linii rzeczywistej. Determinacja odnosi się do możliwego istnienia strategii wygrywających w niektórych grach dwuosobowych (mówi się, że gry są zdeterminowane ). Istnienie tych strategii implikuje strukturalne właściwości linii rzeczywistej i innych polskich przestrzeni .

Teoria modeli

Teoria modeli bada modele różnych teorii formalnych. Tutaj teoria jest zbiorem formuł w określonej logice formalnej i sygnaturze , podczas gdy model jest strukturą, która daje konkretną interpretację teorii. Teoria modeli jest ściśle powiązana z uniwersalną algebrą i geometrią algebraiczną , chociaż metody teorii modeli koncentrują się bardziej na rozważaniach logicznych niż na tych dziedzinach.

Zbiór wszystkich modeli określonej teorii nazywamy klasą elementarną ; Klasyczna teoria modeli ma na celu określenie właściwości modeli w określonej klasie elementarnej lub ustalenie, czy pewne klasy struktur tworzą klasy elementarne.

Metodę eliminacji kwantyfikatora można wykorzystać do wykazania, że ​​zbiory definiowalne w poszczególnych teoriach nie mogą być zbyt skomplikowane. Tarski ustalił eliminację kwantyfikatora dla ciał rzeczywistych domkniętych , wynik, który pokazuje również teorię ciała liczb rzeczywistych, jest rozstrzygalny . Zauważył również, że jego metody w równym stopniu stosują się do algebraicznie domkniętych ciał o dowolnej charakterystyce. Nowoczesna poddziedzina rozwijająca się z tego dotyczy struktur o-minimalnych .

Twierdzenie Morleya o kategoryczności , udowodnione przez Michaela D. Morleya , mówi, że jeśli teoria pierwszego rzędu w języku policzalnym jest kategoryczna w jakiejś niepoliczalnej kardynalności, tj. wszystkie modele tej kardynalności są izomorficzne, to jest kategoryczna we wszystkich niepoliczalnych kardynalnościach.

Trywialną konsekwencją hipotezy continuum jest to, że kompletna teoria z mniej niż continuum wieloma nieizomorficznymi przeliczalnymi modelami może mieć tylko przeliczalnie wiele. Przypuszczenie Vaughta , nazwane na cześć Roberta Lawsona Vaughta , mówi, że jest to prawdą nawet niezależnie od hipotezy kontinuum. Ustalono wiele szczególnych przypadków tego przypuszczenia.

Teoria rekurencji

Teoria rekurencji , zwana również teorią obliczalności , bada właściwości funkcji obliczalnych i stopni Turinga , które dzielą funkcje nieobliczalne na zbiory o tym samym poziomie nieobliczalności. Teoria rekurencji obejmuje również badanie uogólnionej obliczalności i definiowalności. Teoria rekurencji wyrosła z prac Rózsy Péter , Alonzo Churcha i Alana Turinga z lat 30. XX wieku,aw latach 40. XX w.została ona znacznie rozszerzona przez Kleene i Posta .

Klasyczna teoria rekurencji skupia się na obliczalności funkcji od liczb naturalnych do liczb naturalnych. Podstawowe wyniki ustanawiają solidną, kanoniczną klasę funkcji obliczalnych z licznymi niezależnymi, równoważnymi charakterystykami przy użyciu maszyn Turinga , rachunku λ i innych systemów. Bardziej zaawansowane wyniki dotyczą struktury stopni Turinga i siatki zbiorów rekurencyjnie przeliczalnych .

Uogólniona teoria rekurencji rozszerza idee teorii rekurencji na obliczenia, które niekoniecznie są już skończone. Obejmuje badanie obliczalności w wyższych typach, a także takie obszary, jak teoria hiperarytmetyczna i teoria α-rekurencji .

Współczesne badania w teorii rekurencji obejmują badania zastosowań, takich jak losowość algorytmiczna , teoria modeli obliczeniowych i matematyka odwrotna , a także nowe wyniki w czystej teorii rekurencji.

Algorytmicznie nierozwiązywalne problemy

Ważna poddziedzina teorii rekurencji bada nierozwiązywalność algorytmiczną; problem decyzyjny lub problemem funkcja jest algorytmicznie nierozwiązywalny , jeśli nie ma możliwości obliczalny algorytm, który zwraca poprawną odpowiedź dla wszystkich wejść prawnych do problemu. Pierwsze wyniki dotyczące nierozwiązywalności, uzyskane niezależnie przez Churcha i Turinga w 1936 roku, wykazały, że problem Entscheidungs jest nierozwiązywalny algorytmicznie. Turing udowodnił to, ustalając nierozwiązywalność problemu zatrzymania , wynik o dalekosiężnych implikacjach zarówno w teorii rekurencji, jak i informatyce.

Istnieje wiele znanych przykładów nierozstrzygalnych problemów ze zwykłej matematyki. Problemem słowo grup Wykazano algorytm rozwiązać w Piotr Nowikowa 1955 i niezależnie W. Boone 1959 roku zajęty bobrowy problem, opracowany przez Tibor zegarków w 1962, jest kolejnym znanym przykładem.

Dziesiąty problem Hilberta dotyczył algorytmu określającego, czy wielowymiarowe równanie wielomianowe ze współczynnikami całkowitymi ma rozwiązanie w liczbach całkowitych. Częściowy postęp dokonali Julia Robinson , Martin Davis i Hilary Putnam . Algorytmiczna nierozwiązywalność problemu została udowodniona przez Jurija Matiyasevicha w 1970 roku.

Teoria dowodu i konstruktywna matematyka

Teoria dowodu to nauka o dowodach formalnych w różnych logicznych systemach dedukcji. Dowody te są reprezentowane jako formalne obiekty matematyczne, co ułatwia ich analizę za pomocą technik matematycznych. Powszechnie rozważanych jest kilka systemów dedukcji, w tym systemy dedukcji w stylu Hilberta , systemy dedukcji naturalnej oraz rachunek sekwencyjny opracowany przez Gentzena.

Badanie matematyki konstruktywnej w kontekście logiki matematycznej obejmuje badanie systemów w logice nieklasycznej, takiej jak logika intuicjonistyczna, a także badanie systemów predykatywnych . Wczesnym zwolennikiem predykatyzmu był Hermann Weyl , który wykazał, że możliwe jest rozwinięcie dużej części analizy rzeczywistej przy użyciu wyłącznie metod predykatywnych.

Ponieważ dowody są całkowicie skończone, podczas gdy prawda w strukturze nie jest, często w pracach z matematyką konstruktywną podkreśla się dowodliwość. Szczególnie interesująca jest relacja między dowodliwością w systemach klasycznych (lub niekonstruktywnych) a dowodliwością w systemach intuicjonistycznych (lub konstruktywnych). Wyniki, takie jak negatywne tłumaczenie Gödla-Gentzena, pokazują, że możliwe jest osadzenie (lub przetłumaczenie ) logiki klasycznej w logikę intuicjonistyczną, co pozwala na przeniesienie niektórych właściwości dotyczących dowodów intuicjonistycznych z powrotem do dowodów klasycznych.

Ostatnie osiągnięcia w teorii dowodu obejmują badania nad eksploracją dowodów autorstwa Ulricha Kohlenbacha oraz badania nad liczbami porządkowymi teorii dowodu przez Michaela Rathjena .

Aplikacje

„Logika matematyczna została z powodzeniem zastosowana nie tylko do matematyki i jej podstaw ( G. Frege , B. Russell , D. Hilbert , P. Bernays , H. Scholz , R. Carnap , S. Lesniewski , T. Skolem ), ale także fizyki (R. Carnap, A. Dittrich, B. Russell, CE Shannon , AN Whitehead , H. Reichenbach , P. Fevrier), biologii ( JH Woodger , A. Tarski ), psychologii ( FB Fitch , CG Hempel ) prawo i moralność ( K. Menger , U. Klug, P. Oppenheim), ekonomię ( J. Neumann , O. Morgenstern ), kwestie praktyczne ( EC Berkeley , E. Stamm), a nawet metafizykę (J. [Jan] Salamucha, H. Scholz, JM Bochenski ) Jej zastosowania do historii logiki okazały się niezwykle owocne ( J. Łukasiewicz , H. Scholz, B. Mates , A. Becker, E. Moody , J. Salamucha, K. Duerr, Z. Jordan, P. Boehner , JM Bochenski, S. [Stanisław] T. Schayer, D. Ingalls )." „Poczyniono również wnioski do teologii (F. Drewnowski, J. Salamucha, I. Thomas).”

Związki z informatyką

Badanie teorii obliczalności w informatyce jest ściśle związane z badaniem obliczalności w logice matematycznej. Jest jednak różnica w nacisku. Informatycy często koncentrują się na konkretnych językach programowania i wykonalnej obliczalności , podczas gdy badacze logiki matematycznej często koncentrują się na obliczalności jako koncepcji teoretycznej i na nieobliczalności.

Teoria semantyki języków programowania jest powiązana z teorią modeli , podobnie jak weryfikacja programów (w szczególności sprawdzanie modeli ). Korespondencja Curry-Howard między dowodami i programów dotyczy teoria dowodu , zwłaszcza intuicjonistycznej logiki . Rachunki formalne, takie jak rachunek lambda i logika kombinatoryczna, są obecnie badane jako wyidealizowane języki programowania .

Informatyka wnosi również wkład do matematyki, opracowując techniki automatycznego sprawdzania, a nawet znajdowania dowodów, takie jak automatyczne dowodzenie twierdzeń i programowanie logiczne .

Opisowa teoria złożoności wiąże logikę ze złożonością obliczeniową . Pierwszym znaczącym rezultatem w tej dziedzinie, twierdzeniem Fagina (1974), było ustalenie, że NP jest właśnie zbiorem języków wyrażalnym przez zdania egzystencjalnej logiki drugiego rzędu .

Podstawy matematyki

W XIX wieku matematycy zdali sobie sprawę z luk logicznych i niespójności w swojej dziedzinie. Wykazano, że aksjomaty Euklidesa dotyczące geometrii, których nauczano od wieków jako przykład metody aksjomatycznej, były niekompletne. Użycie nieskończenie małych i sama definicja funkcji zostały zakwestionowane w analizie, ponieważ odkryto patologiczne przykłady, takie jak nigdzie różniczkowalna funkcja ciągła Weierstrassa .

Badanie Cantora nad arbitralnymi zbiorami nieskończonymi również spotkało się z krytyką. Leopold Kronecker stwierdził, że „Bóg stworzył liczby całkowite; wszystko inne jest dziełem człowieka”, popierając powrót do badań nad skończonymi, konkretnymi obiektami w matematyce. Chociaż argument Kroneckera był kontynuowany przez konstruktywistów w XX wieku, społeczność matematyczna jako całość odrzuciła je. David Hilbert opowiadał się za badaniem nieskończoności, mówiąc: „Nikt nie wyrzuci nas z Raju, który stworzył Cantor”.

Matematycy zaczęli szukać systemów aksjomatów, które można by wykorzystać do sformalizowania dużych części matematyki. Oprócz usunięcia niejednoznaczności z wcześniej naiwnych terminów, takich jak funkcja, oczekiwano, że ta aksjomatyzacja pozwoli na udowodnienie spójności. W XIX wieku główną metodą dowodzenia niesprzeczności zbioru aksjomatów było dostarczenie jej modelu. Tak więc, na przykład, geometrię nieeuklidesową można udowodnić, definiując punkt jako punkt na nieruchomej sferze, a linię jako wielkie koło na sferze. Powstała struktura, model geometrii eliptycznej , spełnia aksjomaty geometrii płaskiej z wyjątkiem postulatu równoległego.

Wraz z rozwojem logiki formalnej Hilbert pytał, czy byłoby możliwe udowodnienie, że system aksjomatów jest niesprzeczny, analizując strukturę możliwych dowodów w systemie i pokazując poprzez tę analizę, że nie można udowodnić sprzeczności. Pomysł ten doprowadził do badania teorii dowodu . Ponadto Hilbert zaproponował, aby analiza była całkowicie konkretna, używając terminu finitarnego w odniesieniu do metod, na które by zezwolił, ale nie precyzując ich. Na projekt ten, znany jako program Hilberta , poważnie wpłynęły twierdzenia Gödla o niezupełności, które pokazują, że spójności formalnych teorii arytmetyki nie można ustalić za pomocą metod formalizowalnych w tych teoriach. Gentzen wykazał, że możliwe jest przedstawienie dowodu zgodności arytmetyki w systemie skończonym wzbogaconym o aksjomaty indukcji pozaskończonej , a opracowane przez niego techniki były przełomowe w teorii dowodu.

Drugi wątek w historii podstaw matematyki to logika nieklasyczna i matematyka konstruktywna . Nauka matematyki konstruktywnej obejmuje wiele różnych programów o różnych definicjach konstruktywnych . Na końcu, dowody w teorii mnogości ZF, które nie używają aksjomatu wyboru, są przez wielu matematyków nazywane konstruktywnymi. Bardziej ograniczone wersje konstruktywizmu ograniczają się do liczb naturalnych , funkcji teorii liczb i zbiorów liczb naturalnych (które mogą być używane do reprezentowania liczb rzeczywistych, co ułatwia studiowanie analizy matematycznej ). Powszechną ideą jest to, że konkretny sposób obliczania wartości funkcji musi być znany, zanim można będzie powiedzieć, że sama funkcja istnieje.

Na początku XX wieku Luitzen Egbertus Jan Brouwer założył intuicjonizm jako część filozofii matematyki . Filozofia ta, początkowo słabo rozumiana, głosiła, że ​​aby matematyczne zdanie było prawdziwe dla matematyka, osoba ta musi być w stanie przeczuć to zdanie, nie tylko uwierzyć w jego prawdziwość, ale także zrozumieć przyczynę jego prawdziwości. Konsekwencją tej definicji prawdy było odrzucenie prawa wyłączonego środka , ponieważ istnieją twierdzenia, które według Brouwera nie mogły być uznane za prawdziwe, podczas gdy ich negacje również nie mogły być uznane za prawdziwe. Filozofia Brouwera była wpływowa i była przyczyną gorzkich sporów między wybitnymi matematykami. Później Kleene i Kreisel studiowali sformalizowane wersje logiki intuicjonistycznej (Brouwer odrzucił formalizację i przedstawił swoją pracę w niesformalizowanym języku naturalnym). Wraz z pojawieniem się interpretacji BHK i modeli Kripkego intuicjonizm stał się łatwiejszy do pogodzenia z klasyczną matematyką .

Zobacz też

Uwagi

Bibliografia

Teksty licencjackie

  • Walicki, Michał (2011). Wprowadzenie do logiki matematycznej . Singapur : Światowe Wydawnictwo Naukowe . Numer ISBN 9789814343879.
  • Boolos, George ; Burgess, John; Jeffrey, Richard (2002). Obliczalność i logika (wyd. 4). Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 9780521007580.
  • Crossley, JN; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972). Czym jest logika matematyczna? . Londyn, Oxford, Nowy Jork: Oxford University Press . Numer ISBN 9780198880875. Zbl  0251.02001 .
  • Enderton, Herbert (2001). Matematyczne wprowadzenie do logiki (wyd. 2). Boston MA: Prasa akademicka . Numer ISBN 978-0-12-238452-3.
  • Fisher, Alec (1982). Formalna teoria liczb i obliczalność: skoroszyt . (odpowiedni jako pierwszy kurs do samodzielnego badania) (1st ed.). Oxford University Press. Numer ISBN 978-0-19-853188-3.
  • Hamilton, AG (1988). Logika dla matematyków (2nd ed.). Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-36865-0.
  • Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Logika matematyczna (wyd. 2). Nowy Jork : Springer . Numer ISBN 9780387942582.
  • Katz, Robert (1964). Analiza aksjomatyczna . Boston MA: DC Heath and Company .
  • Mendelson, Elliott (1997). Wprowadzenie do logiki matematycznej (wyd. 4). Londyn: Chapman i Hall . Numer ISBN 978-0-412-80830-2.
  • Rautenberg, Wolfgang (2010). Zwięzłe wprowadzenie do logiki matematycznej (3rd ed.). Nowy Jork : Springer . doi : 10.1007/978-1-4419-1221-3 . Numer ISBN 9781441912206.
  • Schwichtenberg, Helmut (2003–2004). Logika matematyczna (PDF) . Monachium : Mathematisches Institut der Universität München . Źródło 2016-02-24 .
  • Shawn Hedman, Pierwszy kurs logiki: wprowadzenie do teorii modeli, teorii dowodu, obliczalności i złożoności , Oxford University Press , 2004, ISBN  0-19-852981-3 . Obejmuje logikę w ścisłym związku z teorią obliczalności i teorią złożoności
  • van Dalen, Dirk (2013). Logika i struktura . Universitext. Berlin: Springer . doi : 10.1007/978-1-4471-4558-5 . Numer ISBN 978-1-4471-4557-8.

Teksty magisterskie

Artykuły naukowe, monografie, teksty i ankiety

Klasyczne gazety, teksty i kolekcje

Bocheński, Józef Maria, wyd. (1959). Precyzja logiki matematycznej . Biblioteka Syntezy, tom. 1. Przetłumaczone przez Otto Birda. Dordrecht : Springer . doi : 10.1007/978-94-017-0592-9 . Numer ISBN 9789048183296.

  • Burali-Forti, Cesare (1897). Pytanie o liczby nieskończone .Przedruk w van Heijenoort 1976 , s. 104-111

Kantor Georg (1874). „Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen” (PDF) . Journal für die Reine und Angewandte Mathematik . 1874 (77): 258–262. doi : 10.1515/crll.1874.77.258 . S2CID  199545885 . Carroll, Lewis (1896). Logika symboliczna . Przedruki z dziedzictwem Kessingera. Numer ISBN 9781163444955.

Soare, Robert Irving (22 grudnia 2011). „Teoria obliczalności i aplikacje: sztuka klasycznej obliczalności” (PDF) . Wydział Matematyki . Uniwersytet w Chicago . Źródło 23 sierpnia 2017 . Swineshead, Richard (1498). Calculationes Suiseth Anglici (po litewsku). Papie: Per Franciscum Gyrardengum.

Zewnętrzne linki