Teorema de completitud de Gödel

Archiu:Completudé logique premier ordre.png

Fòrmula de la teorema de completitud de Gödel.

La teorema de completitud de Gödel és una important teorema de la llògica matemàtica, que va ser demostrat per primera volta per Kurt Gödel en 1929 i que en la seua forma més coneguda establix lo següent:

En una llògica de primer orde, tota fòrmula que és vàlida en un sentit llògic és demostrador. Kurt Gödel

La paraula «demostradora» significa que existix una deducció formal de la fòrmula. La deducció consistix en una llista finita de passos en els que cada pas o be invoca a un axioma o és obtingut a partir de passos previs per mig d'una bàsica regla d'inferència. A partir de dita deducció, és possible verificar si cada u dels passos és correcte per mig d'un algoritme (per eixemple, per mig d'una computadora o a mà).

Una fòrmula és llògicament vàlida si és verdadera en tot model per al llenguage utilisat en la fòrmula. Per a expressar de manera formal la teorema de completitud de Gödel, es deu definir el significat de la paraula modele en este context. Esta és una definició bàsica en la teoria de models.

La teorema de Gödel establix una correspondència entre la veritat semàntica i la demostrabilidad sintàctica en la llògica de primer orde. Crea un víncul entre la teoria de models que s'ocupa de lo que és cert en diferents models, i la teoria de la demostració que estudia lo que es pot provar formalment en sistemes formals particulars. Gödel va utilisar la teorema de completitud per a provar el teorema de compacidad, demostrant la naturalea finitaria de l'operador de conseqüència llògica. Estos resultats varen ajudar a establir la llògica de primer orde com el tipo de llògica dominant en les matemàtiques actuals.

Va ser després simplificat en 1947, quan Leon Henkin va observar en la seua tesis de doctorat que la part difícil de la prova es pot presentar com el Model de Teorema de l'Existència (publicat en 1949). A la seua volta, la prova de Henkin va ser simplificada per Gisbert Hasenjaeger en 1953.

Declaració de la teorema

Introducció

Una fòrmula de primer orde es diu llògicament vàlida si és verdadera en cada estructura per al llenguage de la fòrmula (és dir, per a qualsevol assignació de valors a les variables de la fòrmula). Per a declarar formalment, i després demostrar, el teorema de l'integritat, és necessari també definir un sistema deductivo. Un sistema deductivo es diu complet si tota fòrmula llògicament vàlida és la conclusió d'alguna deducció formal, i la teorema de la completitud per a un sistema deductivo particular és la teorema de que està complet en este sentit. Aixina, en cert sentit, hi ha una teorema de completitud diferent per a cada sistema deductivo. Alguna cosa important junt en l'integritat és la solidea, el fet de que només les fòrmules llògicament vàlides són demostradores en el sistema deductivo.

Si algun sistema deductivo específic de llògica de primer orde és sòlit i complet, llavors és «perfecte» (una fòrmula és demostradora si i només si és una conseqüència semàntica dels axioma), equivalent a qualsevol atre sistema deductivo en el mateix Calitat (qualsevol prova en un sistema es pot convertir en l'atre).

La formulació original de Gödel

La teorema de l'integritat diu que si una fòrmula és llògicament vàlida llavors hi ha una deducció finita (una prova formal) de la fòrmula.

La teorema de Gödel de completitud diu que un sistema deductivo de càlcul de predicats de primer orde és «complet» en el sentit de que no es requerixen regles d'inferència adicionals per a provar totes les fòrmules llògicament vàlides. Junt en l'integritat cal tindre en conte la solidea, el fet de que només les fòrmules llògicament vàlides són demostradores en el sistema deductivo. Junt en la solidea (la verificació de la qual és fàcil), esta teorema implica que una fòrmula és llògicament vàlida si i només si és la conclusió d'una deducció formal.

Teorema de l'existència del model

La versió més simple d'esta teorema que és suficient en la pràctica per a la majoria de les necessitats, i té conexions en la teorema de Löwenheim-Skolem, diu:

Plantilla:Center Una versió més general es pot expressar com:

Plantilla:Center Ací, una teoria consistent es definix com aquella en la que, per a cap fòrmula 'F', tant 'F' com a '¬F' poden ser provats. Vore Consistència, la definició sintàctica; La definició semàntica seria tautológica en este context.

Esta teorema d'Henkin és la versió més directa obtinguda de la teorema de la completitud en la seua prova més simple.

Donat la teorema de Henkin, la demostració de la teorema de la completitud és com seguix: Si $\Phi \models A$ és vàlit, llavors$\Phi \cup \mathrm{\neg }A$ no té models. Per la contraposició de Henkin, llavors $\mathrm{\neg }A$ és una fòrmula inconsistente. Pero, per la definició de consistència, si $\Phi \cup \mathrm{\neg }A$ és inconsistente llavors és possible construir una prova de $\Phi ⊢A$.

Demostracions

Demostració original

En 1930 Gödel va demostrar la completitud de la llògica cuantificacional de primer orde. Lliteralment la teorema de completitud de Gödel establix: «Per a tota fòrmula A de la llògica cuantificacional de primer orde, si A és llògicament verdadera, llavors A és deduible». Dit formalment: «Si ╞ A, llavors ├ A». Açò vol dir que el sistema formal de la llògica cuantificacional serà complet si totes les fòrmules que representen veritats llògiques són formalment deduibles en el sistema.

La prova de la teorema de completitud es reduïx a consignar les següents premisses

1. A és llògicament verdadera: A ╞ A #

Si A és llògicament verdadera, llavors ¬A és insatisfacible

1. Si ¬A és insatisfacible, llavors ¬A és inconsistente
2. Si ¬A és inconsistente, llavors dona lloc a contradicció: ¬A ├ B i ¬A ├ ¬B
3. Si ¬A ├ B i ¬A ├ ¬B, llavors ├ A

La justificació d'estes premisses és la següent

1. És l'hipòtesis de la teorema de completitud
2. Se seguix de la definició del concepte de fòrmula llògicament verdadera: la seua negació ha de ser insatisfacible
3. És la contraposició de la teorema de Henkin
4. És un mer anàlisis de la definició de inconsistencia
5. Es basa en la teorema de deducció, que permet passar de ¬A ├ B i ¬A ├ ¬B a ├ ¬A ^ B i ├ ¬A ^ ¬B, respectivament, i en Modus Ponens, que permet, en ajuda d'estes dos últimes fòrmules, eliminar els antecedents en la llei de reducció a l'absurt (├ (¬A ^ B) ® ((¬A ^ ¬B) ^ ¬¬A); de ├ ¬¬As passa a ├ a per mig d'una aplicació de MP a la llei de doble negació ├ ¬¬A ^ A

Acceptades estes premisses, se'ls aplica reiteradament la regla MP, escomençant per (2) i (1), seguint en (3) i el conseqüent de (2), i aixina successivament, fins a lliberar el conseqüent de (5): ├ A, que és justament la tesis de la teorema de Gödel, el qual queda, per tant, demostrat.

Demostració moderna

En els llibres de llògica moderns, la teorema de completitud de Gödel és per lo general demostrat per mig de la demostració d'Henkin, encara que a voltes també s'utilisa la demostració d'Herbrand, en lloc de la demostració original de Gödel.

Vore també

• Teoremes de incompletitud de Gödel

Referències

Bibliografia

• (1929).University Of Vienna.. Esta tesis és la font original de la demostració de la teorema de completitud.
• (1930).Monatshefte für Mathematik.37

349–360.doi:10.1007/BF01696781. Este artícul conté el mateix material que la tesis doctoral en una forma abreviada. Les demostracions són més curtes, les explicacions més sucintas, i s'ha omés l'extensa introducció.