Komplet teori
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. august 2020; checks kræver 2 redigeringer .I matematisk logik kaldes en teori komplet , hvis en syntaktisk korrekt lukket formel eller dens negation kan bevises i denne teori [1] . Hvis der er en lukket formel , således at hverken eller negation kan bevises i teorien , så kaldes en sådan teori ufuldstændig . Lukningen af en formel betyder, at den ikke indeholder eksterne parametre, og den syntaktiske korrekthed betyder, at den stemmer overens med reglerne i teoriens formsprog . Bevisbarheden af en formel forstås som eksistensen af en sekvens af formelle udsagn, som hver af dem enten er et aksiom for teorien eller opnås i henhold til de formelle regler for afledning fra de foregående udsagn og det sidste udsagn i sekvensen falder sammen med formlen, der bevises.
Uformelt set er en teori komplet, hvis et velformuleret udsagn i den kan bevises eller modbevises. I klassisk logik er enhver modstridende teori således åbenlyst komplet, da enhver formel i den er afledt sammen med dens negation. Det følger af Gödels berømte ufuldstændighedsteorem , at enhver tilstrækkelig stærk rekursivt aksiomatiserbar konsistent førsteordensteori er ufuldstændig. Dette er især Peano-aritmetik - en teori, der beskriver de sædvanlige egenskaber ved naturlige tal med addition og multiplikation.
Begrebet fuldstændighed af en teori introduceret ovenfor bør ikke forveksles med begrebet fuldstændighed af logik , hvilket betyder, at i enhver teori om denne logik vil alle gyldige formler vise sig at kunne udledes af logikkens aksiomer. For eksempel siger Gödels fuldstændighedssætning , at klassisk førsteordenslogik er komplet. Dette betyder, at i enhver førsteordensteori vil enhver identisk sand formel (det vil sige sand uanset fortolkningen af signaturen og værdierne af variablerne) kunne udledes.
Eksempler på komplette teorier
- Propositionsregning af anden orden .
- Tarskis system af aksiomer for euklidisk geometri .
- Presburger aritmetik er en teori, der beskriver naturlige tal med addition, men uden multiplikation.
- Teori om rationelle tal med ordensrelation og addition.
- Teorien om virkelig lukkede felter . Især teorien om reelle tal med addition, multiplikation og ordensrelation ( Seidenberg-Tarski-sætning ).
- Teorien om tætte lineært ordnede mængder uden første og sidste elementer.
Eksempler på teorier, der ikke er fuldstændige
Det er intuitivt klart, at de mest generelle teorier, såsom for eksempel teorien om grupper , teorien om lineært ordnede mængder , ikke behøver at være fuldstændige: ellers ville det betyde, at de samme lukkede formler er sande for alle grupper eller for alle lineært ordnede sæt. Det er indlysende, at dette ikke er tilfældet.
- Formel aritmetik med addition og multiplikation af naturlige tal. Et ikke-trivielt eksempel på et udsagn skrevet på sproget i denne teori og ikke kan bevises i det, er Goodsteins sekvenssætning .
- Teorien om semigrupper med multiplikation, der indeholder associativitetsaksiomet.
- Teorien om grupper med associativitetens aksiomer, eksistensen af et neutralt og omvendt element.
- En teori om lighed, der indeholder et enkelt prædikat for lighed og lighedsaksiomerne .
Se også
- Moose-Woth kriterium
- Konsekvent teori
- Afgørlig teori
Noter
- ↑ Lyndon R., 1968 , s. 56.
Litteratur
- Vereshchagin N.K., Shen A. Forelæsninger om matematisk logik og teori om algoritmer. Del 2: Languages and Calculus Arkiveret 30. november 2016 på Wayback Machine , M.: MCNMO , 2012.
- Gilbert D., Akkerman V. Fundamentals of theoretical logic. - M. : URSS, 2010. - 304 s. — ISBN 978-5-484-01144-5 .
- Curry, Haskell B. Fundamenter af matematisk logik. — M .: Mir, 1969. — 567 s.
- Kleene S.K. Introduktion til metamatematik. - M . : Forlaget for udenlandsk litteratur, 1957. - 526 s.
- Lyndon R. Noter om logik. - M . : Mir, 1968. - 128 s.