Kompletní teorie

V matematické logice se teorie nazývá úplná , pokud je v této teorii prokazatelná nějaká syntakticky správná uzavřená formule nebo její negace [1] . Jestliže tam je uzavřený vzorec takový že žádný ani negace je provable v teorii , pak taková teorie je volána neúplná . Uzavření formule znamená, že neobsahuje vnější parametry, a syntaktická správnost znamená, že odpovídá pravidlům formálního jazyka teorie. Prokazatelnost formule je chápána jako existence posloupnosti formálních tvrzení, z nichž každý je buď axiomem teorie, nebo je získán podle formálních pravidel odvozování z předchozích tvrzení, a poslední tvrzení v posloupnosti se shoduje s dokazovaným vzorcem.

Neformálně řečeno, teorie je úplná, pokud lze jakékoli dobře formulované tvrzení v ní dokázat nebo vyvrátit. V klasické logice je tedy každá protichůdná teorie zjevně úplná, protože jakýkoli vzorec v ní je odvozen spolu s její negací. Ze slavné Gödelovy věty o neúplnosti vyplývá , že jakákoli dostatečně silná rekurzivně axiomatizovatelná konzistentní teorie prvního řádu je neúplná. Konkrétně se jedná o Peanovu aritmetiku - teorii, která popisuje obvyklé vlastnosti přirozených čísel se sčítáním a násobením.

Pojem úplnosti teorie představený výše by neměl být zaměňován s pojmem úplnost logiky , což znamená, že v jakékoli teorii této logiky se všechny platné formule ukáží jako odvoditelné z axiomů logiky. Například Gödelův teorém úplnosti říká, že klasická logika prvního řádu je úplná. To znamená, že v jakékoli teorii prvního řádu bude odvoditelný jakýkoli stejně pravdivý vzorec (to znamená pravdivý bez ohledu na interpretaci podpisu a hodnot proměnných).

Příklady úplných teorií

• Počet výroků druhého řádu .
• Tarskiho systém axiomů pro euklidovskou geometrii .
• Presburgerova aritmetika je teorie, která popisuje přirozená čísla se sčítáním, ale bez násobení.
• Teorie racionálních čísel s řádovou relací a sčítáním.
• Teorie skutečně uzavřených polí . Zejména teorie reálných čísel se sčítáním, násobením a relací uspořádání ( Seidenbergova-Tarského věta ).
• Teorie hustých lineárně uspořádaných množin bez prvního a posledního prvku.

Příklady teorií, které nejsou úplné

Je intuitivně jasné, že nejobecnější teorie, jako je například teorie grup , teorie lineárně uspořádaných množin , nemusí být úplné: jinak by to znamenalo, že stejné uzavřené vzorce platí pro všechny grupy resp. pro všechny lineárně uspořádané množiny. Je zřejmé, že tomu tak není.

• Formální aritmetika se sčítáním a násobením přirozených čísel. Netriviálním příkladem výroku napsaného v jazyce této teorie, který není v ní dokazatelný, je Goodsteinova věta o posloupnosti .
• Teorie pologrup s násobením obsahující axiom asociativity.
• Teorie grup s axiomy asociativity, existence neutrálního a inverzního prvku.
• Teorie rovnosti obsahující jediný predikát rovnosti a axiomy rovnosti .

Viz také

• Moose-Wothovo kritérium
• Konzistentní teorie
• Rozhodnutelná teorie

Poznámky

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

Literatura

• Vereshchagin N.K., Shen A. Přednášky o matematické logice a teorii algoritmů. Část 2: Jazyky a počet archivované 30. listopadu 2016 na Wayback Machine , M.: MTsNMO , 2012.
• Gilbert D., Akkerman V. Základy teoretické logiky. - M. : URSS, 2010. - 304 s. — ISBN 978-5-484-01144-5 .
• Curry, Haskell B. Základy matematické logiky. — M .: Mir, 1969. — 567 s.
• Kleene S.K. Úvod do metamatematiky. - M . : Nakladatelství zahraniční literatury, 1957. - 526 s.
• Lyndon R. Poznámky k logice. - M .: Mir, 1968. - 128 s.