Completitud (llògica)

En metalógica, la completitud o completud semàntica és la propietat metateórica que tenen els sistemes formals quan totes les fòrmules llògicament vàlides (totes les veritats llògiques) del sistema són ademés teoremas del sistema. És dir, quan el conjunt de les veritats llògiques del sistema és un subconjunt del conjunt de teoremes. En atres paraules, si A és una fòrmula qualsevol del llenguage i S és el sistema formal baixe consideració, llavors es complix que:

Si  ${\models }_{\mathrm{S}}A$  llavors  ${⊢}_{\mathrm{S}}A$

Per una atra part, la completitud sintàctica és la propietat que tenen els sistemes formals quan, per a tota fòrmula tancada del llenguage del sistema, o be és una teorema o be la seua negació ho és. Açò és, existix una prova per a cada fòrmula tancada o per a la seua negació.

La llògica proposicional i la llògica de primer orde són abdós semánticamente completes, pero no sintácticamente completes. Per eixemple, en la llògica proposicional, la fòrmula p no és una teorema, i tampoc ho és la seua negació, de modo que això basta per a mostrar que no és sintácticamente completa. No obstant, com cap d'eixes dos fòrmules és una veritat llògica, no afecten a la completitud semàntica del sistema.

El segona teorema de incompletitud de Gödel demostra que cap sistema (definit recursivamente) en cert poder expressiu pot ser al mateix temps consistent i sintácticamente complet.

Una atra propietat metateórica distinta és la completitud semàntica forta, que diu: si en un sistema formal S, A és una fòrmula ben formada qualsevol que és una conseqüència semàntica d'un conjunt $\Gamma$ de fòrmules, llavors existix una derivació de A a partir de $\Gamma$. En símbols:

Si  $\Gamma {\models }_{\mathrm{S}}A$  llavors  $\Gamma {⊢}_{\mathrm{S}}A$

Vore també

• Metalógica
• Teorema de completitud de Gödel
• Teoremes de incompletitud de Gödel