Teljes elmélet

A matematikai logikában egy elméletet akkor nevezünk teljesnek , ha ebben az elméletben bármely szintaktikailag helyes zárt formula vagy tagadása bizonyítható [1] . Ha van olyan zárt képlet , amelyre sem a tagadás, sem a tagadás nem bizonyítható az elméletben , akkor az ilyen elméletet hiányosnak nevezzük . A képlet lezárása azt jelenti, hogy nem tartalmaz külső paramétereket, a szintaktikai helyesség pedig azt, hogy megfelel az elmélet formális nyelvezetének szabályainak. A képlet bizonyíthatósága alatt olyan formális állítások sorozatának létezését értjük, amelyek mindegyike vagy az elmélet axiómája , vagy az előző állításokból való levezetés formális szabályai szerint , és a sorozat utolsó állítása szerint kapjuk. egybeesik a bizonyított formulával.

Informálisan szólva egy elmélet akkor teljes, ha bármely jól megfogalmazott állítás bizonyítható vagy cáfolható. Így a klasszikus logikában minden ellentmondásos elmélet nyilvánvalóan teljes, mivel minden benne lévő képlet a tagadásával együtt származik. Gödel híres befejezetlenségi tételéből következik , hogy minden kellően erős, rekurzívan axiomatizálható konzisztens elsőrendű elmélet hiányos. Ez különösen a Peano aritmetika - egy elmélet, amely a természetes számok szokásos tulajdonságait írja le összeadással és szorzással.

Egy elmélet teljességének fentebb bemutatott fogalmát nem szabad összetéveszteni a logika teljességének fogalmával , ami azt jelenti, hogy e logika bármely elméletében minden érvényes képlet a logika axiómáiból származtatható. Például Gödel teljességi tétele kimondja, hogy a klasszikus elsőrendű logika teljes. Ez azt jelenti, hogy bármely elsőrendű elméletben bármely azonosan igaz képlet (vagyis igaz, függetlenül az aláírás értelmezésétől és a változók értékétől) származtatható lesz.

Példák teljes elméletekre

• Másodrendű állítások számítása .
• Tarski axiómarendszere az euklideszi geometriához .
• A Presburger aritmetika olyan elmélet, amely a természetes számokat összeadással, de szorzás nélkül írja le.
• Racionális számok elmélete sorrendi relációval és összeadással.
• A valóban zárt mezők elmélete . Különösen a valós számok elmélete összeadási, szorzási és sorrendi viszonyokkal ( Seidenberg-Tarski tétel ).
• Az első és utolsó elemek nélküli sűrű lineárisan rendezett halmazok elmélete .

Példák olyan elméletekre, amelyek nem teljesek

Intuitív módon világos, hogy a legáltalánosabb elméleteknek, mint például a csoportok elméletének , a lineárisan rendezett halmazok elméletének nem kell teljesnek lennie: különben ez azt jelentené, hogy ugyanazok a zárt képletek igazak minden csoportra, ill. minden lineárisan rendezett halmazhoz. Nyilvánvaló, hogy ez nem így van.

• Formális aritmetika természetes számok összeadásával és szorzásával. Egy nem triviális példa egy ezen elmélet nyelvén írt és nem bizonyítható kijelentésre Goodstein sorozattétele .
• Az asszociativitás axiómáját tartalmazó szorzásos félcsoportok elmélete .
• A csoportok elmélete az asszociativitás axiómáival, a semleges és inverz elem létezésével.
• Egy egyenlőségelmélet, amely az egyenlőség egyetlen predikátumát és az egyenlőség axiómáit tartalmazza .

Lásd még

• Moose-Woth kritérium
• Következetes elmélet
• Dönthető elmélet

Jegyzetek

1. ↑ Lyndon R., 1968 , p. 56.

Irodalom

• Vereshchagin N.K., Shen A. Előadások a matematikai logikáról és az algoritmusok elméletéről. 2. rész: Languages ​​and Calculus archiválva : 2016. november 30., the Wayback Machine , M.: MCNMO , 2012.
• Gilbert D., Akkerman V. Az elméleti logika alapjai. - M. : URSS, 2010. - 304 p. — ISBN 978-5-484-01144-5 .
• Curry, Haskell B. A matematikai logika alapjai. — M .: Mir, 1969. — 567 p.
• Kleene S.K. Bevezetés a metamatematikába. - M . : Külföldi Irodalmi Kiadó, 1957. - 526 p.
• Lyndon R. Megjegyzések a logikáról. - M . : Mir, 1968. - 128 p.