Komplett teori
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 augusti 2020; kontroller kräver 2 redigeringar .I matematisk logik kallas en teori fullständig om någon syntaktiskt korrekt sluten formel eller dess negation är bevisbar i denna teori [1] . Om det finns en sluten formel så att varken eller negation är bevisbar i teorin , så kallas en sådan teori ofullständig . Stängningen av en formel innebär att den inte innehåller externa parametrar, och den syntaktiska riktigheten gör att den överensstämmer med reglerna för teorins formspråk . Bevisbarheten av en formel förstås som förekomsten av en sekvens av formella uttalanden, som vart och ett är antingen ett axiom för teorin eller erhålls enligt de formella reglerna för härledning från de tidigare uttalandena, och det sista uttalandet i sekvensen sammanfaller med att formeln bevisas.
Informellt sett är en teori komplett om något välformulerat påstående i den kan bevisas eller motbevisas. Således, i klassisk logik , är varje motsägelsefull teori uppenbarligen komplett, eftersom varje formel i den härleds tillsammans med dess negation. Det följer av Gödels berömda ofullständighetsteorem att varje tillräckligt stark rekursivt axiomatiserbar konsekvent första ordningens teori är ofullständig. I synnerhet är detta Peano-aritmetik - en teori som beskriver de vanliga egenskaperna hos naturliga tal med addition och multiplikation.
Begreppet fullständighet av en teori som introducerats ovan bör inte förväxlas med begreppet fullständighet av logik , vilket betyder att i vilken teori som helst av denna logik, kommer alla giltiga formler att visa sig kunna härledas från logikens axiom. Till exempel säger Gödels fullständighetssats att klassisk första ordningens logik är komplett. Detta innebär att i vilken första ordningens teori som helst kommer varje identiskt sann formel (det vill säga sann oavsett tolkningen av signaturen och variablernas värden) att kunna härledas.
Exempel på kompletta teorier
- Propositionskalkyl av andra ordningen .
- Tarskis system av axiom för euklidisk geometri .
- Presburger aritmetik är en teori som beskriver naturliga tal med addition men utan multiplikation.
- Teori om rationella tal med ordningsrelation och addition.
- Teorin om riktigt stängda fält . I synnerhet teorin om reella tal med addition, multiplikation och ordningsrelation ( Seidenberg-Tarski-satsen ).
- Teorin om täta linjärt ordnade mängder utan första och sista element.
Exempel på teorier som inte är fullständiga
Det är intuitivt tydligt att de mest generella teorierna, som till exempel teorin om grupper , teorin om linjärt ordnade mängder , inte behöver vara kompletta: annars skulle detta innebära att samma slutna formler är sanna för alla grupper eller för alla linjärt ordnade uppsättningar. Det är uppenbart att så inte är fallet.
- Formell aritmetik med addition och multiplikation av naturliga tal. Ett icke-trivialt exempel på ett uttalande skrivet på språket i denna teori och inte kan bevisas i det är Goodsteins sekvenssats .
- Teorin om semigrupper med multiplikation som innehåller axiomet för associativitet.
- Teorin om grupper med associativitetens axiom, förekomsten av ett neutralt och omvänt element.
- En teori om jämlikhet som innehåller ett enda predikat för jämlikhet och jämlikhetens axiom .
Se även
- Älg-Woth kriterium
- Konsekvent teori
- Avgörande teori
Anteckningar
- ↑ Lyndon R., 1968 , sid. 56.
Litteratur
- Vereshchagin N.K., Shen A. Föreläsningar om matematisk logik och teori om algoritmer. Del 2: Languages and Calculus Arkiverad 30 november 2016 på Wayback Machine , M.: MCNMO , 2012.
- Gilbert D., Akkerman V. Fundamentals of theoretical logic. - M. : URSS, 2010. - 304 sid. — ISBN 978-5-484-01144-5 .
- Curry, Haskell B. Foundations of Mathematical Logic. — M .: Mir, 1969. — 567 sid.
- Kleene S.K. Introduktion till metamatematik. - M . : Förlag för utländsk litteratur, 1957. - 526 sid.
- Lyndon R. Anteckningar om logik. - M . : Mir, 1968. - 128 sid.