Relación+consecuencia+sintáctica+y+semántica-MM-2013

1

Lógica 2013

Consecuencia sintáctica y sus relaciones con la consecuencia semántica.

Miguel Molina

En estas notas vamos a estudiar la relación de consecuencia sintáctica, teniendo in

mente que se trata de una forma de capturar, por medio de un concepto

rigurosamente definido, la noción preformal de consecuencia lógica. Ya teníamos

otra elucidación de esa noción, la consecuencia semántica. Veremos entonces

algunas de las relaciones que hay entre ambos conceptos, y nos referiremos

siempre a lo que sucede en lenguajes de primer orden y fórmulas cerradas.

Recordemos entonces las definiciones que están en juego.

Consecuencia semántica: Una fórmula es consecuencia semántica de un

conjunto Γ si y solo si todos los modelos de Γ son modelos de . Esto se representa

como Γ⊨ .

Derivación: Una derivación de en el sistema de deducción natural a partir de Γ

es una secuencia finita de fórmulas en las que cada fórmula es o bien

i) un elemento de Γ, o bien

ii) un supuesto, o bien

iii) se puede extraer como resultado de aplicar reglas del sistema de deducción

natural a términos anteriores de la misma secuencia,

y además

iv) no tiene supuestos abiertos, (esto es, para cada término que corresponde a un

supuesto hay un término posterior que “lo cancela”, es decir, un término que es el

resultado de aplicar una regla que exige la existencia de la subderivación que

utiliza ese supuesto);

v) no se justifica ningún término por la aplicación de reglas a términos anteriores

que se encuentran en subderivaciones canceladas en algún término anterior;

vi) el último término es la fórmula .

Consecuencia sintáctica: Una fórmula es consecuencia sintáctica de un conjunto

Γ si y solo si existe una derivación de en el sistema de deducción natural a partir

de Γ. Esto se representa como Γ⊢.

Obviamente, consecuencia semántica y consecuencia sintáctica son conceptos

diferentes, ya que en uno lo que importa es si el conjunto de los modelos de Γ está

2

o no incluido en el conjunto de los modelos de , mientras que en el otro lo que

importa es si existe o no una secuencia de fórmulas que cumpla determinadas

restricciones que solamente tienen que ver con las características morfológicas de

esas fórmulas, es decir, con criterios puramente sintácticos.

Sin embargo, debemos esperar que ambos conceptos se hallen estrechamente

relacionados, porque las reglas de inferencia, que regulan la cuestión de si una

determinada secuencia de fórmulas es una derivación o no lo es, fueron escogidas

de tal manera que preservaran la consecuencia semántica. Investiguemos algunas

propiedades de la consecuencia sintáctica y luego intentemos precisar sus

relaciones con la consecuencia semántica.

Ya que hemos visto que la consecuencia semántica tiene algunas propiedades que

estudiamos con cierto detenimiento, una pregunta que podemos hacernos es si

existen propiedades análogas para la consecuencia sintáctica.

1. La consecuencia sintáctica es una relación.

Esto es algo obvio, dado cualquier conjunto de fórmulas y cualquier fórmula

aislada, existe una derivación de la fórmula aislada a partir del conjunto o no existe

tal derivación. Por eso, dados cualesquiera Γ y tendremos que o bien Γ⊢ o bien

Γ⊬.

2. Conjuntos inconsistentes y contradicciones.

Cuando estudiábamos los modelos de conjuntos de fórmulas, atendiendo a la

relación de consecuencia semántica, definimos conjuntos insatisfacibles como

aquellos que no tienen modelos, y contradicciones como aquellas fórmulas que

tampoco los tienen. Desde el punto de vista sintáctico, redefiniremos lo que es una

contradicción (y el lector deberá entender en algunos casos por el contexto a qué

nos estamos refiriendo, si a una contradicción en sentido semántico o en sentido

sintáctico).

Definición: Una contradicción (en el sentido sintáctico) es una fórmula de la forma

(A∧¬A), siendo A una fórmula cualquiera.

Obviamente, la satisfacibilidad es una noción semántica, relativa a modelos. Para

trabajar con la consecuencia sintáctica, introduciremos la noción de consistencia.

Definición: Un conjunto de fórmulas es consistente si ninguna contradicción (en

sentido sintáctico) es consecuencia sintáctica de .

3

Hay una analogía muy evidente entre las nociones semánticas y sintácticas.

Plano semántico Plano sintáctico

es una contradicción: no tiene

modelos

es una contradicción: es de la

forma (A∧¬A)

es satisfacible: tiene al menos

un modelo

es consistente: No existe una

contradicción (según el punto de vista

sintáctico) que sea consecuencia

sintáctica de

Observemos lo siguiente: Toda contradicción desde el punto de vista sintáctico es

una contradicción desde el punto de vista semántico, pero lo recíproco no es cierto.

Por ejemplo, la fórmula (PaPa) es una contradicción desde el punto de vista

semántico pero no lo es desde el punto de vista sintáctico.

Con respecto a la relación entre conjuntos satisfacibles y conjuntos consistentes,

aun no podemos decir nada. Tal vez todos los conjuntos satisfacibles sean

consistentes o al revés, o haya conjuntos consistentes no satisfacibles, etc.

Volveremos más adelante sobre el punto, que es de extremada importancia.

Recordemos que cualquier fórmula es consecuencia semántica de un conjunto

insatisfacible, y que si un conjunto tiene como consecuencia semántica a una

contradicción, se trata de un conjunto insatisfacible, o sea:

Si es insatisfacible, entonces ⊨ para toda fórmula .

Si κ es una contradicción y ⊨ κ, entonces es insatisfacible.

Mostremos que tenemos resultados análogos para la relación de consecuencia

sintáctica. (En realidad, para la consecuencia sintáctica el análogo de la segunda

proposición de arriba sería: “Si κ es una contradicción (en sentido sintáctico) y

⊢κ, entonces es inconsistente”, lo que es simplemente la definición de conjunto

inconsistente). Demostremos el análogo de la primera proposición.

Si es inconsistente, entonces ⊢ para toda fórmula .

Supongamos que es inconsistente. Entonces existe una fórmula A tal que

⊢(A∧¬A).

Esto significa que existe una derivación Ɗ de (A∧¬A) en la que las premisas son

elementos de . Introduzcamos la siguiente notación: Sea PRE(Ɗ, , ) el conjunto

de premisas de la derivación Ɗ de a partir de . Es claro que PRE(Ɗ, ,) es un

subconjunto de , y que depende de la derivación concreta Ɗ de que se trate, ya

4

que nada asegura que todas las derivaciones de a partir de utilicen las mismas

premisas.

Podemos representar la derivación Ɗ de (A∧¬A) a partir de de la siguiente

manera:

(0-k) PRE(Ɗ, ,)

n. (A∧¬A)

significando que colocamos todas las premisas al principio, de las líneas 1 hasta k y

luego aplicamos las reglas hasta obtener (A∧¬A) en la línea n1. Ahora bien, si

tenemos esta derivación, podemos construir esta derivación Ɗ’ de una fórmula

cualquiera B a partir de .

(0-k) PRE(Ɗ, ,)

Ɗ

(n). (A∧¬A)

(n+1) [B] Supuesto

(n+2) A Elim ∧, n. Ɗ’

(n+3) ¬A Elim ∧, n.

(n+4) (A∧¬A) Intr ∧, n+2, n+3.

(n+5) B Intr , (n+1)-(n+4)

(n+6) B Elim , n+5.

Como la derivación Ɗ’ utiliza las mismas premisas que la derivación Ɗ, y todas

estas son elementos de , esto muestra que ⊢B, siendo B una fórmula cualquiera.

Hemos demostrado que

Si es inconsistente, entonces ⊢ para toda fórmula

1 Ponemos una línea numerada con cero para considerar el caso en que no se utilice ninguna fórmula como premisa. En caso de que utilicemos la línea 0, será también k=0, es decir, no se coloca ninguna premisa en la derivación.

5

3. Conjunto vacío y teoremas.

Recordemos que al trabajar con consecuencia semántica encontramos algunas

fórmulas –a las que llamamos válidas- que son consecuencia semántica del

conjunto vacío y también consecuencia semántica de cualquier conjunto. ¿Qué

puede significar que una fórmula es consecuencia sintáctica del conjunto vacío?

Evidentemente, solo puede significar que se trata de una fórmula derivable sin

utilizar premisas. Existen fórmulas así. Mostremos que la fórmula (∀xPxxPx) es

consecuencia sintáctica del conjunto vacío, es decir, que existe una derivación de

ella que no utiliza premisas:

1. [∀xPx] Supuesto

2. Pa Elim ∀, 1

3. xPx Intr ,2

4. (∀xPxxPx) Intr , 1- 3.

Observará el lector atento que esta fórmula que hemos derivado a partir del

conjunto vacío es válida. ¿Será esto un ejemplo de una ley general? Estamos lejos

aun de poder responder esa pregunta. Por lo pronto, demos un nombre específico

al concepto:

Definición: Una fórmula es un teorema si y solo si es consecuencia sintáctica del

conjunto vacío.

Obviamente, también podemos representarlo así:

Definición: es un teorema si y solo si ⊢.

Se tiene el resultado siguiente: Si es un teorema, entonces es consecuencia

sintáctica de cualquier conjunto . La demostración es inmediata, porque la

derivación de a partir del conjunto vacío es también, por definición, una

derivación de a partir de . El recíproco, o sea, que si una fórmula es

consecuencia sintáctica de cualquier conjunto es un teorema, es también obvio ya

que si la fórmula es consecuencia sintáctica de cualquier conjunto también lo es, en

particular, del conjunto vacío.

6

Tenemos entonces dos nociones paralelas:

Plano semántico Plano sintáctico Fórmulas válidas (Tienen todas las interpretaciones como modelos, son las únicas consecuencias semánticas del conjunto vacío, son consecuencia semántica de cualquier conjunto de fórmulas)

Teoremas (Son las únicas consecuencias sintácticas del conjunto vacío, son consecuencia sintáctica de cualquier conjunto de fórmulas)

Por supuesto, surge inmediatamente el problema de saber cuál es la relación entre

fórmulas válidas y teoremas. ¿Serán las mismas fórmulas, será que hay teoremas

que no son válidos, será que hay fórmulas válidas que no son teoremas? Al igual

que frente a otras cuestiones, no estamos en condiciones aun de responder estas

preguntas.

4. Monotonía.

Recordemos que la relación de consecuencia semántica cumplía la propiedad de

monotonía: Si ⊨, entonces ,⊨.

Es obvio que también se tiene que

Si ⊢, entonces ,⊢

Esto es así porque cualquier derivación de a partir de es también una

derivación de a partir de ,.

5. Teorema de deducción.

Cuando mostramos el teorema de deducción para la consecuencia semántica

advertimos que se trataba de, justamente, la versión semántica, la cual establecía:

,A⊨B si y solo si ⊨(AB)

Es por eso que no resultará sorprendente la noticia de que existe una versión

sintáctica, que establece:

,A⊢B si y solo si ⊢(AB)

Supongamos que se cumple ,A⊢B.

Esto quiere decir que existe una derivación Ɗ de B en la que las premisas

pertenecen al conjunto {A}, en la que podemos incluir la fórmula A como

premisa, aun cuando esto no sea estrictamente necesario. Ubiquemos todas las

premisas que pertenecen a y son diferentes a A en las primeras líneas de la

derivación. Este conjunto es PRE(Ɗ,{A},B) – {A}. Enseguida ubiquemos A, y ya

7

tenemos todo lo necesario para derivar B. La derivación Ɗ quedaría esquematizada

así:

(0-k) PRE(Ɗ, {A}, B) – {A}

(k+1) A Premisa

(n) B

A partir de esta derivación podemos construir la siguiente derivación Ɗ’ de la

fórmula (AB) a partir de , en la que A aparece como supuesto y se aplica la regla

de introducción del condicional para obtener lo deseado.

(0-k) PRE(Ɗ, {A}, B) – {A}

(k+1) [A] Supuesto

(n) B

(n+1) (AB) Int. , (k+1)-(n).

Esto demuestra que si ,A ⊢B, entonces ⊢(AB).

Supongamos ahora que tenemos una derivación Ɗ de (AB) partir de , y

mostremos que existe una derivación Ɗ’ de B a partir de ,A.

Ɗ se puede representar así:

(0-k) PRE(Ɗ,, AB)

(n) (AB)

Si tomamos esta misma derivación, le agregamos la fórmula A como premisa y

obtenemos una nueva derivación de otra fórmula, esa fórmula será derivada de

,A. Obtengamos de ese modo la fórmula B:

8

(0-k) PRE(Ɗ, ,AB)

Ɗ

(n) (AB)

(n+1) A Premisa

(n+2) B Elim , n, (n+1)

Esto demuestra que si ⊢(AB), entonces ,A⊢B.

Por lo tanto queda demostrado el teorema de deducción tal cual lo recuadramos

arriba.

6. El “absurdo”.

Al estudiar la relación de consecuencia semántica habíamos establecido el

siguiente resultado:

⊨ si y solo si , es insatisfacible.

El análogo para la consecuencia sintáctica es el siguiente, y como demostraremos,

también se cumple.

⊢ si y solo si , es inconsistente.

Recordemos que un conjunto es inconsistente si a partir de él es posible derivar

una contradicción. Supongamos que hay una derivación Ɗ de a partir de y

mostremos que en ese caso es posible construir una derivación de una

contradicción a partir de ,.

Podemos representar Ɗ así:

( 0-k) PRE(Ɗ, , )

(n)

Si tomamos esta misma derivación, le agregamos la fórmula como premisa y

obtenemos una nueva derivación de otra fórmula, esa fórmula será derivada de

,. Obtengamos de ese modo una contradicción:

9

( 0-k) PRE(Ɗ, ,)

(n)

(n+1) Premisa

(n+2) () Int. , n, (n+1).

Esto demuestra que si ⊢ entonces , es inconsistente.

Para demostrar el recíproco, supongamos , es inconsistente, y mostremos

cómo construir una derivación de a partir de . Al ser , inconsistente,

podemos derivar una contradicción a partir de él. Representemos esa derivación Ɗ

así:

( 0-k) PRE(Ɗ, ∪{},(B∧¬B))- {}

(k+1) Premisa Ɗ

(n) (B∧¬B)

La idea es construir una nueva derivación Ɗ’ en la que se utilizan todas las premisas de las primeras k líneas de la anterior, y se introduce ¬ como supuesto, se deriva una contradicción, y por regla de introducción de la negación se concluye :

( 0-k) PRE(Ɗ, ∪{},(B∧¬B))- {}

(k+1) [] Supuesto

Ɗ

Ɗ’

(n) (B∧¬B)

(n+1) ¬¬ Int. ¬, (k+1)-(n).

(n+2) Elim. ¬, (n+1)

De este modo, queda demostrado el teorema tal cual lo hemos recuadrado arriba.

10

Consecuencia sintáctica y consecuencia semántica.

Hemos dejado planteadas varias preguntas acerca de la relación que existe entre

conceptos definidos en términos de consecuencia semántica y conceptos definidos

en términos de consecuencia semántica. Recordemos las cuestiones planteadas en

partes anteriores de este trabajo.

Plano semántico Plano sintáctico

es una contradicción: no tiene modelos

es una contradicción: es de la forma (A∧¬A)

es satisfacible: tiene al menos un modelo

es consistente: No existe una contradicción (según el punto de vista sintáctico) que sea consecuencia sintáctica de

Fórmulas válidas (Tienen todas las interpretaciones como modelos, son las únicas consecuencias semánticas del conjunto vacío, son consecuencia semántica de cualquier conjunto de fórmulas)

Teoremas (Son las únicas consecuencias sintácticas del conjunto vacío, son consecuencia sintáctica de cualquier conjunto de fórmulas)

Nos hemos preguntado por las relaciones entre contradicciones en sentido

semántico y sintáctico, por las relaciones entre conjuntos satisfacibles y

consistentes, y por las relaciones entre fórmulas válidas y teoremas. Todas estas

cuestiones se podrán responder cabalmente si respondemos a esta pregunta,

absolutamente central:

¿Cuál es la relación entre la consecuencia semántica y

la consecuencia sintáctica?

Precisando, lo que queremos saber es lo siguiente: Supongamos que se cumple

⊢. ¿Asegura eso que ⊨? Y recíprocamente, si se cumple ⊨, ¿asegura eso

que ⊢?

Pensemos un momento qué significan estas preguntas. Supongamos que se

pudiera dar, para un conjunto y una fórmula , que ⊢ y sin embargo ⊭. Esto

querría decir que nuestro sistema formal de deducción natural nos estaría

indicando como consecuencia lógica de un conjunto una fórmula que, al no ser

consecuencia semántica del conjunto, será falsa bajo una interpretación que hace

verdadera todas las fórmulas del conjunto, y por lo tanto, difícilmente la

11

aceptaríamos como consecuencia lógica de él. Esta situación representaría una

catástrofe para el sistema de deducción natural por razones obvias. No nos

aseguraría la preservación de la verdad, no podríamos confiar en que la verdad de

las premisas asegura la verdad de la conclusión y para propósitos lógicos, el

sistema vería muy duramente cuestionado su valor. Un sistema en el que esta

indeseable situación no se da, o sea, un sistema para el cual

Si ⊢, entonces ⊨

es un sistema correcto.

Vamos a demostrar que nuestro sistema de deducción natural es correcto. ¿Cómo

podemos hacerlo? Bueno, obviamente, nuestra gran ayuda en esta tarea será el

hecho de que hemos elegido las reglas de forma que preserven la consecuencia

semántica. Eso nos permite idear la siguiente demostración: Sabemos que ⊢

significa que hay una derivación de a partir de . Queremos mostrar que cada vez

que esto se da, también será consecuencia semántica de . Consideremos la

longitud de las derivaciones, medida según la cantidad de líneas que tienen. Hay

derivaciones de longitud 1, de longitud 2, de longitud 3…, y de cualquier longitud.

Si logramos demostrar que las derivaciones de cualquier longitud son correctas –

esto es, que para las derivaciones de cualquier longitud la conclusión es

consecuencia semántica de las premisas-, habremos logrado nuestro objetivo.

Empecemos considerando el caso en que se da ⊢ porque hay una derivación

de longitud 1 de a partir de . Es obvio que la única forma en que esto sea

posible es que sea un elemento de . La derivación tiene la forma:

1. Premisa

Ahora, bien, en este caso, es obvio que ⊨ porque es un elemento de .

Por ahora hemos demostrado que todas las derivaciones de longitud 1 son

correctas.

Por supuesto que es poco, y lo que es peor, el camino de demostrar que todas las

derivaciones de longitud 2 son correctas, todas las derivaciones de longitud 3 son

correctas, y seguir así, no nos llevaría a otra cosa que a que la muerte nos alcanzara

antes de que demostremos que las derivaciones de longitud 10000 son correctas, y

seguramente la causa de la muerte sería el tedio. Por lo tanto, intentaremos un

camino clásico en matemática.

Hagamos la hipótesis de que las demostraciones de longitud n o menor son

correctas. Si a partir de aquí demostramos que todas las derivaciones de longitud

n+1 son correctas, habremos demostrado que todas las derivaciones son correctas.

¿Y esto? Aquí hay gato encerrado, dirá el lector. No, responderé yo.

12

Observe lo siguiente. Lo que le propongo es demostrar estas dos proposiciones:

(a) Las derivaciones de longitud 1 son correctas. (Esto ya está demostrado)

(b) Para cualquier n, si las derivaciones de longitud n o menor son correctas,

entonces las derivaciones de longitud n+1 son correctas.

y agrego que si alguien demuestra (a) y (b), demuestra que las derivaciones de

cualquier longitud son correctas. ¿Por qué? Porque por (a) se sabe que las

derivaciones de longitud 1 son correctas. Entonces, como las derivaciones de

longitud 1 son correctas y se cumple (b), las derivaciones de longitud 1+1, o sea de

longitud 2, son correctas. Y como las derivaciones de longitud 2 son correctas y se

cumple (b), las derivaciones de longitud 2+1, o sea de longitud 3, son correctas. Y

así podemos seguir para mostrar que las derivaciones de cualquier longitud son

correctas.

Este clásico procedimiento se llama inducción completa y, a pesar de su nombre,

configura un argumento deductivo, no inductivo. (El argumento cuyas premisas

son (a) y (b) y su conclusión es que las derivaciones de cualquier longitud son

correctas).

¿Cómo es que obtenemos derivaciones de longitud mayor que 1? Qué pregunta

tonta, ¿no? Obviamente, lo hacemos agregando líneas, y las líneas se agregan

aplicando reglas o introduciendo premisas o supuestos.

Observemos cuidadosamente qué pasa con los supuestos. Supongamos que

estamos haciendo una derivación, y en el transcurso de ella introducimos el

supuesto [A]. Hasta que no cancelemos el supuesto, podemos considerar que lo

que tenemos es una derivación de la última línea a partir de ,A. Esto es lo mismo

que considerar que hemos introducido A como premisa y no como supuesto.

Cuando lo cancelamos, obtenemos fórmulas derivadas con prescindencia de A. De

esa manera podemos considerar que cualquier línea de una derivación de a

partir de nos está mostrando que una fórmula es consecuencia sintáctica de un

conjunto, aunque no necesariamente del conjunto .

13

Por ejemplo:

1. A Premisa

2. B Premisa

Estas fórmulas son consecuencia sintáctica de

[C] Supuesto

Estas fórmulas son consecuencia sintáctica de ,C

[D] Supuesto

Estas fórmulas son consecuencia sintáctica de ,C,D

E

Estas fórmulas son consecuencia sintáctica de ,C

F

Estas fórmulas son consecuencia sintáctica de

Desde este punto de vista, cada línea de una derivación indica que la fórmula que

contiene es consecuencia sintáctica de un conjunto. Hagamos ahora la siguiente

hipótesis (para llevar adelante la inducción completa):

Todas las veces que con n líneas o menos se muestra que una fórmula es consecuencia

sintáctica de un conjunto (entendiendo que se muestra en el sentido indicado arriba,

o sea, la fórmula puede ser consecuencia sintáctica del conjunto o del conjunto al

que se le han adjuntado los supuestos abiertos), se cumple que también es

consecuencia semántica de ese mismo conjunto.

Usando esta hipótesis debemos mostrar:

Todas las veces que con n+1 línea se muestra que una fórmula es consecuencia

sintáctica de un conjunto , la fórmula es consecuencia semántica de .

Manos a la obra entonces.

Supongamos que ⊢ y que hay una derivación de a partir de de longitud n+1.

Queremos demostrar que ⊨.

Advertencia: la demostración del teorema es larga –ocupa desde la página siguiente, la 14, hasta la 20-, repetitiva

y nadie se la va a pedir. Puede ser sin embargo instructivo examinar cómo procede sobre algunos conectivos

binarios y sobre todo sobre los cuantificadores. Como sea, no es necesario que recuerde los detalles, aunque

14

sería deseable que comprendiese la idea que anima la demostración más allá de ellos. Incluimos la demostración

(casi) completa en este trabajo porque nos parece importante mostrar efectivamente la corrección del sistema y

no simplemente enunciarla.

Nos preguntamos ¿cómo es que apareció la última línea, la que contiene a ?

Obviamente no puede ser un supuesto, porque en ese caso no estaríamos frente a

una derivación. Si es una premisa, trivialmente ⊨ ya que es elemento de . El

caso que nos queda es que sea el resultado de la aplicación de una regla a líneas

anteriores de la derivación. Estudiemos las diversas posibilidades.

1. es el resultado de aplicar la regla Int.. En ese caso la derivación tiene la

forma:

(i) A

(j) B

(n+1) (AB) Int. (i),(j)

Como la última línea se obtiene a través de una regla que no cancela supuestos, ni

A ni B pueden depender de supuestos y por lo tanto tenemos, ⊢ A y ⊢B a través

de una derivación de n líneas o menos, por lo que según nuestra hipótesis

⊨A y ⊨B

Ahora bien, es trivial demostrar a partir de esto que ⊨ (AB): todos los modelos

de son modelos de A y de B y por lo tanto, modelos de (AB).

2. es el resultado de aplicar la regla Elim.. En ese caso la derivación tiene la

forma:

(i) () o (i) ()

(n+1) Elim. (i) (n+1) Elim. (i)

Como la última línea se obtiene a través de una regla que no cancela supuestos,

() no puede depender de supuestos y por lo tanto tenemos ⊢() a través

de una derivación de n líneas o menos, por lo que según nuestra hipótesis

⊨ ()

Ahora bien, es trivial demostrar a partir de esto que ⊨ : todos los modelos de

son modelos de () y por lo tanto, modelos de .

El caso de la derecha es totalmente análogo.

15


forma:

(i) A o (i) B

(n+1) (A B) Int. (i) (n+1) (A B) Int. (i)

Como la última línea se obtiene a través de una regla que no cancela supuestos, A

no puede depender de supuestos y por lo tanto tenemos, ⊢ A a través de una

derivación de n líneas o menos, por lo que según nuestra hipótesis

⊨A

Ahora bien, es trivial demostrar a partir de esto que ⊨ (AB): todos los modelos

de son modelos de A y por lo tanto, modelos de (AB).

El caso de la derecha es totalmente análogo.

4. es el resultado de aplicar la regla Elim. . En ese caso la derivación tiene la

forma:

(i) (AB)

(j) [A]

(k) C

(l) [B]

(m) C

(n+1) C Elim. (i),(j)-(k), (l)-(m)

Mirando la derivación tenemos que ⊢ (AB). Además mirando hasta la línea k,

vemos que ,A ⊢C y mirando hasta la línea m que ,B⊢C. Todas estas

consecuencias sintácticas surgen de derivaciones de n líneas o menos, por lo que

según nuestra hipótesis

16

⊨ (AB), ,A ⊨C y ,B ⊨C.

A partir de aquí debemos demostrar que ⊨C.

Supongamos que hubiese un modelo I de que fuese contramodelo de C. Como I es

modelo de , será modelo de (AB). Entonces o bien I es modelo también de A o

bien es modelo también de B. Pero tanto si se da lo primero como si se da lo

segundo, I será modelo de C. Contradicción. Por lo tanto, todo modelo de será

modelo de C.


forma:

(i) [A]

(j) B

(n+1) (AB) Int. (i)-(j)

Observando la derivación vemos que ,A⊢B y esta consecuencia se desprende de

una derivación de n líneas o menos. Por lo tanto, según nuestra hipótesis, tenemos

que ,A ⊨B. A partir de aquí debemos demostrar que ⊨ (AB), lo que es nada

más que una aplicación del teorema de deducción en versión semántica.

6. es el resultado de aplicar la regla Elim. . En ese caso la derivación tiene

la forma:

(i) (AB)

(j) A

(n+1) B Elim. (i),(j)

Como la última línea se obtiene a través de una regla que no cancela supuestos, ni

(AB) ni A pueden depender de supuestos y por lo tanto tenemos, ⊢ (AB) y

⊢A a través de una derivación de n líneas o menos, por lo que según nuestra

hipótesis

17

⊨(AB) y ⊨A

A partir de aquí se debe demostrar que ⊨ B. A esta hora de la noche decido

dejarlo como ejercicio para el lector.


forma:

(i) []

(j) (BB)

(n+1) Int. (i)-(j)

Observando la derivación vemos que , ⊢(BB) y esta consecuencia se

desprende de una derivación de n líneas o menos. Por lo tanto, según nuestra

hipótesis, tenemos que , ⊨(BB). A partir de aquí debemos demostrar que

⊨. Como , tiene como consecuencia semántica una contradicción, , es

insatisfacible y se sigue, por teorema del “Absurdo” que ⊨.

8. es el resultado de aplicar la regla Elim.. En ese caso la derivación tiene la

forma:

(i) A

(n+1) A Elim. (i)


A no puede depender de supuestos y por lo tanto tenemos, ⊢A a través de

una derivación de n líneas o menos, por lo que según nuestra hipótesis

⊨A

Queda como ejercicio para el lector, demostrar que en estas condiciones se tiene

⊨A, además de los que deberían ser nuestros siguientes dos casos: los de Int. y

Elim. .

18

9. es el resultado de aplicar la regla Elim.∀. En ese caso la derivación tiene la

forma:

(i) ∀xA(x)

(n+1) A(ā) Elim. ∀ (i)


∀xA(x) no puede depender de supuestos y por lo tanto tenemos, ⊢ ∀xA(x) a

través de una derivación de n líneas o menos, por lo que según nuestra hipótesis

⊨ ∀xA(x)


⊨A(ā), lo que es una aplicación directa de la cláusula pertinente de la definición

de Interpretación en LPO.

10. es el resultado de aplicar la regla Int.∀. En ese caso la derivación tiene la

forma:

(i) A(ā)

(n+1) ∀xA(x) Int. ∀ (i)

Recordemos que ā no aparece en ninguna fórmula de . No es necesario

considerar supuestos sin cancelar porque al tratarse de una derivación no los hay.


A(ā) no puede depender de supuestos y por lo tanto tenemos, ⊢ A(ā) a través de


(1) ⊨ A(ā)

donde ā no aparece en ninguna fórmula de que se utilice en la derivación como

premisa. Debemos demostrar que en estas condiciones se cumple

(2) ⊨∀xA(x).

Lo haremos por contrarrecíproco. Supongamos que no se cumple (2) o sea que

existe una interpretación I sobre una estructura E tal que I es modelo de todas las

fórmulas de y

19

(3) I (∀xA(x))=F.

(3) nos indica que hay en el dominio de E un elemento u tal que

(4) I (A(ū))=F.

A partir de I construyamos una nueva interpretación J de la siguiente manera:

J actúa sobre una estructura exactamente igual a E excepto que el individuo

asignado a la constante ā es u. Como solo hemos cambiado el individuo asignado a

ā y esta constante no aparece en las fórmulas de , se tiene que bajo esta nueva

interpretación todas las fórmulas de tienen el mismo valor de verdad que bajo I,

o sea, V. Pero como ā está asignado al elemento u será J(A(ā))=F contradiciendo

(1). Esto demuestra que ⊨∀x A(x).


forma:

(i) A(ā)

(n+1) xA(x) Int. (i)

Y ā no aparece en la fórmula A(x).


A(ā) no puede depender de supuestos y por lo tanto tenemos, ⊢A(ā) a través de


⊨A(ā)


⊨xA(x).

20

12. es el resultado de aplicar la regla Elim. . En ese caso la derivación tiene la

forma:

(i) xA(x)

(j) [A(ā)]

(k) B

(n+1) B Elim. (i),(j)-(k)

Observando la derivación hasta la línea (i) vemos que ⊢ xA(x). Además mirando

hasta la línea k, vemos que ,A(ā) ⊢B. Todas estas consecuencias sintácticas

surgen de derivaciones de n líneas o menos, por lo que según nuestra hipótesis

⊨ xA(x) y ,A(ā)⊨B.

A partir de aquí debemos demostrar que ⊨B.

Supongamos dos casos: (a) A(ā) no tiene modelos. Entonces, como ⊨ xA(x)

resulta que es insatisfacible y por lo tanto ⊨B. (b) Supongamos que , A(ā) es

satisfacible. Tomemos un modelo cualquiera I de que actúa sobre una estructura

E. Si I es también modelo de A(ā), como ,A(ā)⊨B, I será modelo de B. Si I no es

modelo de A(ā), supongamos que I no es modelo de B y llegaremos a una

contradicción. I es modelo de y contramodelo de A(ā), pero como ⊨ xA(x)

existe un individuo u del dominio tal que I(A(ū))=V. Construyamos una nueva

interpretación J sobre una estructura E’ idéntica a E excepto en que asigna el

individuo u a la constante ā. Entonces J(A(ā))=V. Como la constante ā no aparece

en las fórmulas de , ni en B, los valores de verdad de las fórmulas de

permanecen iguales a los que eran bajo I o sea, V; el valor de B permanece igual al

que era bajo I, o sea, F, y el valor de verdad de A(ā) es V. Esto contradice ,A(ā)⊨B.

Por lo tanto, ⊨B.

Hemos demostrado así un resultado metateórico tan fundamental que podemos

decir lo siguiente: si no valiera, deberíamos tirar el sistema de deducción natural a

la basura y adoptar otro. Lleva el nombre de

21

Teorema de corrección

Para todo conjunto de fórmulas y toda fórmula ,

si ⊢ entonces ⊨.

En particular esto demuestra, tomando = que

Si es un teorema, entonces es una fórmula válida

Supongamos que es inconsistente. Entonces tiene como consecuencia

sintáctica a una contradicción, y por lo tanto, tiene como consecuencia semántica a

una contradicción. Esto demuestra que

Si es inconsistente, entonces es insatisfacible

o, en forma equivalente,

Si es satisfacible, entonces es consistente

Claro que esta es la mitad de la historia. La otra mitad es obtener respuesta a las

preguntas: ¿Hay fórmulas válidas que no son teoremas? ¿Hay conjuntos

consistentes insatisfacibles? Con mayor generalidad, siempre que sea ⊨, ¿será

⊢?

Pensemos qué significaría una respuesta negativa a la última pregunta. Si fuera el

caso de que hubiera un conjunto y una fórmula tales que ⊨ pero ⊬,

tendríamos que nuestro sistema formal no podría capturar todas las consecuencias

semánticas de un conjunto. No es una situación tan grave como la incorrección,

pero representaría un resultado que marcaría límites a la capacidad de nuestro

sistema para descubrir las consecuencias lógicas de al menos algunos conjuntos.

Un sistema así se dice incompleto.

¿Qué seguridad tenemos de la completitud de nuestro sistema?

En principio, puede parecer que no hay razones para temer que estemos

trabajando con un sistema incompleto. Pero vamos a hacer tambalear esa

pseudoseguridad a través de un ejemplo:

22

Considere el siguiente conjunto infinito de proposiciones numeradas expresadas

en lenguaje natural:

1) Existe al menos un elemento con la propiedad P y todos los elementos tienen la

propiedad P.

2) Existen al menos dos elementos con la propiedad P.

3) Existen al menos tres elementos con la propiedad P.

n) Existen al menos n elementos con la propiedad P.

Hay dos cosas claras: La primera es que cualquier modelo de ese conjunto de

proposiciones debe tener dominio infinito. Si tuviera un dominio finito, tendría k

elementos, siendo k un número natural, y en ese dominio la proposición “Existen al

menos k+1 elementos con la propiedad P” y todas las siguientes serían falsas.

La segunda es que todas estas proposiciones son expresables en un lenguaje de

primer orden con identidad. Por ejemplo, la primera proposición se puede traducir

como (∃xPx∧∀xPx) y la segunda como ∃x∃y((Px∧Py) ∧ x≠y).

Agreguemos a ese conjunto la siguiente proposición:

ω) El conjunto de los elementos que tienen la propiedad P es finito.

Obviamente, el conjunto formado por todas las proposiciones numeradas con

números naturales y la proposición etiquetada con ω (al que llamaremos ) es

insatisfacible por lo que acabamos de decir. No puede haber un modelo que tenga a

la vez infinitos individuos con la propiedad P (para hacer verdaderas las infinitas

proposiciones numeradas) y una cantidad finita de individuos con la propiedad P

(para hacer verdadera la proposición etiquetada con ω). Supongamos además que

logramos traducir todas las proposiciones de a LPO. ¿Podremos derivar una

contradicción de ? Respuesta: No. Sería imposible. ¿Por qué? Porque una

derivación está obligada a utilizar una cantidad finita de premisas. Y si tomamos

una cantidad finita de proposiciones de obtenemos un conjunto satisfacible.

Supongamos que el número más alto de proposición que tomamos como premisa

es k, y sin importar si tomamos o no como premisa a la proposición etiquetada con

ω, cualquier conjunto de k elementos a los cuales se les asigne la propiedad P será

modelo del conjunto de premisas. Por lo tanto, al ser el conjunto de premisas

satisfacible, es consistente, y no podremos derivar una contradicción a partir de él.

¿Demuestra esto que nuestro sistema es incompleto?

23

Bueno, justo se termina el curso aquí, de manera que para saberlo van a tener que

cursar Lógica 2.

…………………………………………………………………………………………………………………

Está bien, a pedido del público vamos a dar algunos avances. Según la humilde

opinión de quien escribe, los tres lógicos más grandes de la historia son, por orden

cronológico, Aristóteles (384 a.C.-322 a.C.), Frege (1848-1925) y Gödel (1906-

1978). De Aristóteles, creador de la Lógica, no es necesario que diga nada, ya que

tanto nomini nullum par elogium, es el intelecto más poderoso que ha dado la

especie humana, la que, salvo prueba de lo contrario, es la que da los intelectos

más poderosos que existen. A Frege se le debe el más importante avance en la

ciencia de la lógica desde que su creación por Aristóteles: un sistema lógico con la

potencia de LPO. Explicar los aportes de Gödel es un poco más complejo, pero hizo

uno muy fundamental que no demostraremos pero sí estamos en condiciones de

entender:

Teorema de completitud (Gödel, 1930)

LPO es completo, o sea, si ⊨, entonces ⊢

Gödel no lo demostró para nuestro sistema de deducción natural por la perentoria

razón de que éste no había sido aun descubierto. (El sistema es debido a Gentzen

(1909-1945), un brillante lógico alemán que trabajó en la Checoslovaquia ocupada

bajo el régimen nazi y terminó muriendo como prisionero de los soviéticos a fines

de la Segunda Guerra Mundial. Curiosamente, tanto Gödel como Gentzen murieron

de inanición. Gödel desarrolló una paranoia y dejó de comer porque creía que lo

querían envenenar). Gödel demostró la completitud de un sistema equivalente a

DN, o sea en el que se puede derivar todo lo que se deriva en DN, y tal que todo lo

que se puede derivar con el sistema con el cual Gödel trabajaba es derivable en DN.

Esta bicoca fue la tesis doctoral de Gödel. Posteriormente hizo descubrimientos de

no menor importancia, aunque solo este hubiera bastado para darle un lugar entre

los lógicos más importantes de la historia.

Todo esto es muy impresionante, pero ¿no demostramos antes que había un

conjunto insatisfacible y consistente? Eso sería un contraejemplo del Teorema de

Completitud de Gödel, porque si el conjunto es insatisfacible tiene como

consecuencia semántica a cualquier proposición, y ya vimos que no podemos

derivar contradicciones del conjunto, por lo que no tiene como consecuencia

sintáctica a cualquier proposición.

Respuesta: No. Lo que surge del Teorema de completitud de Gödel y la

consideración del conjunto es algo muy notable: No es posible expresar en LPO la

proposición etiquetada como ω. Si fuera posible hacerlo, sí tendríamos un

contraejemplo.

24

Esto nos muestra algo importante: LPO tiene límites expresivos. No debería ser

algo asombroso, ya que parece natural que todos los lenguajes los tengan, pero al

recordar todos los proyectos de lenguas perfectas, vemos con qué facilidad

olvidamos algo tan trivial y a veces hasta nos convencemos de lo contrario.

¿Qué más hay para estudiar en Lógica?

La lógica es, como cualquier ciencia, un universo. Por supuesto que en ese universo

algunas cosas nos son más cercanas que otras. Las preguntas que naturalmente

surgen desde el lugar en que estamos situados son:

Pregunta 1: ¿Cómo se demuestra la completitud de LPO?

Respuesta: Curse lógica 2.

Pregunta 2: ¿Podemos hacer de nuestro sistema DN algo mecánico, como lo son las

tablas de verdad, o siempre se requiere algo de ingenio para aplicarlo?

Respuesta: DN no es reductible a un sistema mecánico. Para saber por qué, curse

Lógica 2.

Pregunta 3: Está bien, aplicar DN requiere ingenio, pero, ¿existe algún sistema

mecánico para determinar si una fórmula es consecuencia lógica de un conjunto?

Respuesta: No. No se trata simplemente de que no conocemos un procedimiento así.

Se trata de que no existe ninguno, no puede existir. Para saber por qué, curse Lógica

2.

Pregunta 4: Acá hablan de un tal “Teorema de completitud de Gödel”, pero una vez

yo leí un libro de sociología (o de lingüística, o de psicología, o incluso de divulgación

científica) en el que se mencionaba un tal “Teorema de INcompletitud de Gödel”. ¿El

error es de estas notas o del libro?

Respuesta: Existe el Teorema de Completitud de Gödel y también el Teorema de

Incompletitud de Gödel, que refiere a sistemas matemáticos, no exclusivamente

lógicos. Advertencia: si el libro en el que encontró la referencia no es de divulgación

científica, lo más probable es que la única parte que refiere al teorema y no dice

cualquier sinsentido sea el índice del libro, si es que indica correctamente en qué

página se encuentra el sinsentido. Si quiere conocer exactamente el enunciado del

Teorema de incompletitud, lo que establece, curse Lógica 2. Si además es un alumno

muy aplicado, podrá ver alguna demostración.

Pregunta 5: ¿Cuáles son los límites expresivos de LPO?

Respuesta: Según desde dónde se mire, están muy lejos o ahí nomás, cerquita. Si

quiere saber más sobre eso, curse Lógica 2.

25

Pregunta 6: ¿Hay otros lenguajes, otras lógicas?

Respuesta: Por supuesto. Y algunos son ciertamente útiles en filosofía. Pero es un

tema demasiado amplio para tocarlo aquí haciéndole un mínimo de justicia.

También queda para Lógica 2.

Al finalizar no queda más que decirles que esperamos que hayan aprendido como

alumnos del curso tanto como nosotros aprendimos preparándolo. Que el espíritu

aristotélico los acompañe por el resto de sus días.

Documents

Relación+consecuencia+sintáctica+y+semántica-MM-2013