Consistència (llògica)

En metalógica, la consistència o consistència llògica és la propietat que tenen els sistemes formals quan no és possible deduir una contradicció dins del sistema. És dir, donat un llenguage formal i un aparat deductivo (axiomas i regles d'inferència), no és possible deduir una fòrmula i la seua negació. L'existència d'un modele implica que una teoria llògica és consistent.

Generalisant, la consistència és una propietat que poden tindre els conjunts de fòrmules. Intuitivament, un conjunt de fòrmules és consistent quan no és possible deduir una contradicció del mateix. És dir, donat un llenguage formal i un aparat deductivo, no és possible demostrar una fòrmula i la seua negació. Equivalentement, açò es pot expressar dient que per a cap proposició llògica p: $𝒜 ⊢ p$ i $𝒜 ⊢ \neg p$ simultàneament.

Introducció

La consistència d'un conjunt de proposicions $𝒜$ pot ser definida tant en térmens semàntics com en térmens sintàctics. En térmens semàntics, un conjunt de fòrmules és consistent si i només si té un modele $ℳ$ :

És dir, si existix a lo manco una interpretació que faça verdaderes a totes les fòrmules del conjunt.

Per a evaluar si el conjunt és consistent segons la definició semàntica, podem construir una taula de veres:

\begin{matrix} p & q & (q \to \neg p) & r \\ V & V & F & V \\ V & V & F & F \\ V & F & V & V \\ V & F & V & F \\ F & V & V & V \\ F & V & V & F \\ F & F & V & V \\ F & F & V & F \end{matrix}

Com es veu, en cap de les interpretacions (cap de les files de la taula) es dona que totes les fòrmules són verdaderes. Després, d'acort en la definició semàntica, el conjunt és inconsistente.

En térmens sintàctics, un conjunt de fòrmules és consistent si i només si per a tota fòrmula A, no és possible deduir tant A com ￢A (i.i. la negació llògica de A) a partir del conjunt de fòrmules.^[1]

Per eixemple, considere's el següent conjunt de fòrmules de la llògica proposicional: $p, q, (q \to \neg q), r$ . Utilisant la regla d'inferència del modus ponens entre $q \land (q \to \neg q)$ , és possible deduir $\neg p$ . Després, segons la definició sintàctica de consistència, el conjunt és inconsistente.

Un sistema formal és consistent si i solament si el conjunt dels seus teoremas és consistent.^[1]

Pels teoremes de la incompletitud de Gödel sabem que cap sistema formal que tinga un mínim de poder expressiu pot ser al mateix temps consistent i complet.

Demostració de consistència

Una demostració de consistència, o prova de consistència, és una demostració formal de que un sistema formal és consistent. Un sistema formal és consistent si no conté una contradicció, o, en forma més precisa, no existix una proposició tal que es pot demostrar o deduir simultàneament la proposició i la seua negació.

Referit a un argument, la consistència és la necessitat de que totes les premisses tinguen que ser necessàriament i al mateix temps, com a producte, totes verdaderes, per a que l'argument, si és consistent, puga ser vàlit o no vàlit. Referit al discurs, la consistència té que vore en que les implicacions llògiques del mateix no siguen autocontradictorias.

El desenroll inicial de la teoria de la demostració matemàtica va ser motivat pel desig de proveir demostracions de coherència finita per a totes les matemàtiques com a part del programa de Hilbert. El programa de Hilbert complix en les observacions de Gödel, tal com s'expressa en les seues dos teoremes de incompletitud de Gödel, de que les teories de demostració robustes no són capaces de provar la seua pròpia consistència.

A pesar de que és possible demostrar la consistència per mig de teoria de models, per lo general es realisa d'una manera purament sintàctica, sense la necessitat de proveir una referència a algun model de la llògica. l'eliminació de tall (o en forma equivalent, la normalisació del càlcul subjacent, si és que existix un) implica la consistència del càlcul: ya que òbviament no existix prova de falsetat que siga lliure de tall, no existix, per lo tant, contradicció en general.

Consistència i completitud

Els principals resultats relacionats en la consistència i completitud varen ser demostrats per Kurt Gödel:

El teorema de completitud de Gödel indica que tota teoria de primer orde consistent és completa sobre el conjunt consistent màxim de les fòrmules que es generen per mig de l'algoritme de busca de demostració.
Els teoremes de la incompletitud de Gödel indiquen que les teories capaces d'expressar la seua pròpia relació de demostrabilidad i de desenrollar un argument diagonal són capaços de demostrar la seua pròpia consistència solament si són inconsistentes. Estes teories, si són consistents, són denominades teories essencialment incompletes.

Per mig de l'aplicació d'estes idees, es poden trobar quatre tipos distints de teories de primer orde:

Teories inconsistentes, que no posseïxen models.
Teories que no poden analisar la seua pròpia relació de demostració, tals com la axiomatisació de Tarski de la geometria del punt i la llínea, i l'aritmètica de Presburg. Ya que estes teories són descriptas en forma satisfactòria pel model que s'obté per mig de la teorema de completitud, llavors estos sistemes són complets.
Teories capaces d'analisar la seua pròpia consistència, i que inclouen la negació de la proposició que assevera la seua pròpia consistència. Este tipo de teories són completes sobre el model que s'obté a partir de la teorema de completitud, pero contenen com a teorema la implicancia d'una contradicció, en contradicció al fet de que són consistents.
Teories essencialment incompletes.

En forma adicional, s'ha descobert recentment que existix un quint tipo de teoria, les teories auto verificables, que són lo suficientment robustes com per a analisar la seua pròpia relació de demostració, pero són massa dèbils com per a realisar una diagonalización de Gödel, i que, per lo tant, poden demostrar en forma consistència la seua pròpia consistència. No obstant, una teoria que demostra la seua pròpia consistència no permet obtindre cap informació interessant, ya que les teories inconsistentes també demostren la seua pròpia consistència.

Fòrmules

Un conjunt de fòrmules $Φ$ en llògica de primer orde és consistent (expressat com En $Φ$ ) si i solament si no existix una fòrmula $ϕ$ tal que $Φ ⊢ ϕ$ i $Φ ⊢ \neg ϕ$ . De lo contrari $Φ$ és inconsistente i s'expressa Inc $Φ$ .

$Φ$ és simplement consistent si i solament si per a cap fòrmula $ϕ$ de $Φ$ són tant $ϕ$ com la negació de $ϕ$ teoremes de $Φ$ .

$Φ$ és absolutament consistent si per lo manco una fòrmula de $Φ$ no és una teorema de $Φ$ .

$Φ$ és máximamente consistent si i solament si para tota fòrmula $ϕ$ , si En $Φ \cup ϕ$ llavors $ϕ \in Φ$ .

$Φ$ es diu conté testics si i solament si per a cada fòrmula de la forma $\exists x ϕ$ existix un terme $t$ tal que $(\exists x ϕ \to ϕ \frac{t}{x}) \in Φ$ .

Resultats bàsics

1. Els següents són equivalents:

(a) Inc $Φ$

(b) Para tot $ϕ, Φ ⊢ ϕ .$

2. Tot conjunt de fòrmules satisfactible és consistent, un conjunt de fòrmules $Φ$ és satisfactible si i solament si existix un model $ℑ$ tal que $ℑ ⊨ Φ$ .

3. Per a tot $Φ$ i $ϕ$ :

(a) si no $Φ ⊢ ϕ$ , llavors En $Φ \cup {\neg ϕ}$ ;

(b) si En $Φ$ i $Φ ⊢ ϕ$ , llavors En $Φ \cup {ϕ}$ ;

(c) si En $Φ$ , llavors En $Φ \cup {ϕ}$ o En $Φ \cup {\neg ϕ}$ .

4. Siga $Φ$ un conjunt de fòrmules consistents i que posseïxen testics. Per a tot $ϕ$ i $ψ$ :

(a) si $Φ ⊢ ϕ$ , llavors $ϕ \in Φ$ ,

(b) o be $ϕ \in Φ$ o be $\neg ϕ \in Φ$ ,

(c) $(ϕ \lor ψ) \in Φ$ si i solament si $ϕ \in Φ$ o $ψ \in Φ$ ,

(d) si $(ϕ \to ψ) \in Φ$ i $ϕ \in Φ$ , llavors $ψ \in Φ$ ,

(i) $\exists x ϕ \in Φ$ si i solament si existix un terme $t$ tal que $ϕ \frac{t}{x} \in Φ$ .

Teorema de Henkin

Siga $Φ$ un conjunt de fòrmules máximamente consistents testics.

Definix una relació binaria en el conjunt de térmens S $t_{0} \sim t_{1}$ si i solament si $t_{0} = t_{1} \in Φ$ ; i siga $\overline{t}$ la classe de térmens d'equivalència contenint $t$ ; i siga $T_{Φ} : = {\overline{t} | t \in T^{S}}$ a on $T^{S}$ és el conjunt de térmens basats en el conjunt de símbol $S$ .

Definix l'estructura S $𝔗_{Φ}$ sobre $T_{Φ}$ el terme-estructura corresponent a $Φ$ per mig de:

(1) Per a el $n$ -ésimo $R \in S$ , $R^{𝔗_{Φ}} \overline{t_{0}} \dots \overline{t_{n - 1}}$ si i solament si $R t_{0} \dots t_{n - 1} \in Φ$ ,

(2) Per a el $n$ -ésimo $f \in S$ , $f^{𝔗_{Φ}} (\overline{t_{0}} \dots \overline{t_{n - 1}}) : = \overline{f t_{0} \dots t_{n - 1}}$ ,

(3) Para $c \in S$ , $c^{𝔗_{Φ}} : = \overline{c}$ .

Siga $ℑ_{Φ} : = (𝔗_{Φ}, β_{Φ})$ el terme-interpretació han associat en $Φ$ , a on $β_{Φ} (x) : = \bar{x}$ .

(*)

Para tot

ϕ

,

ℑ_{Φ} ⊨ ϕ

si i solament si

ϕ \in Φ

.

Vore també

Referències

↑ ^1,0 ^1,1 Hunter, Geoffrey (1971). «Secció 24», Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of Califòrnia Press.

Bibliografia

(1994) Mathematical Logic, Second Edition edició (en anglés), Springer-Verlag. ISBN 0-387-94258-0.

Referències

Este artícul conté una traducció derivada de «Consistencia (lógica)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Hunter-1] 1,0 ^1,1 Hunter, Geoffrey (1971). «Secció 24», Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of Califòrnia Press.

[1]