1

Lgica 2012

Consecuencia sintctica y sus relaciones con la consecuencia semntica.

Miguel Molina

En estas notas vamos a estudiar la relacin de consecuencia sintctica, teniendo in

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

rigurosamente definido, la nocin preformal de consecuencia lgica. Ya tenamos

otra elucidacin de esa nocin, la consecuencia semntica. 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 frmulas cerradas.

Recordemos entonces las definiciones que estn en juego.

Consecuencia semntica: Una frmula es consecuencia semntica de un

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

como .

Derivacin: Una derivacin de en el sistema de deduccin natural a partir de

es una secuencia finita de frmulas en las que cada frmula 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 deduccin

natural a trminos anteriores de la misma secuencia,

y adems

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

supuesto hay un trmino posterior que lo cancela, es decir, un trmino que es el

resultado de aplicar una regla que exige la existencia de la subderivacin que

utiliza ese supuesto);

v) no se justifica ningn trmino por la aplicacin de reglas a trminos anteriores

que se encuentran en subderivaciones canceladas en algn trmino anterior;

vi) el ltimo trmino es la frmula .

Consecuencia sintctica: Una frmula es consecuencia sintctica de un conjunto

si y solo si existe una derivacin de en el sistema de deduccin natural a partir

de . Esto se representa como .

Obviamente, consecuencia semntica y consecuencia sintctica 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 frmulas que cumpla determinadas

restricciones que solamente tienen que ver con las caractersticas morfolgicas de

esas frmulas, es decir, con criterios puramente sintcticos.

Sin embargo, debemos esperar que ambos conceptos se hallen estrechamente

relacionados, porque las reglas de inferencia, que regulan la cuestin de si una

determinada secuencia de frmulas es una derivacin o no lo es, fueron escogidas

de tal manera que preservaran la consecuencia semntica. Investiguemos algunas

propiedades de la consecuencia sintctica y luego intentemos precisar sus

relaciones con la consecuencia semntica.

Ya que hemos visto que la consecuencia semntica tiene algunas propiedades que

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

existen propiedades anlogas para la consecuencia sintctica.

1. La consecuencia sintctica es una relacin.

Esto es algo obvio, dado cualquier conjunto de frmulas y cualquier frmula

aislada, existe una derivacin de la frmula aislada a partir del conjunto o no existe

tal derivacin. Por eso, dados cualesquiera y tendremos que o bien o bien

.

2. Conjuntos inconsistentes y contradicciones.

Cuando estudibamos los modelos de conjuntos de frmulas, atendiendo a la

relacin de consecuencia semntica, definimos conjuntos insatisfacibles como

aquellos que no tienen modelos, y contradicciones como aquellas frmulas que

tampoco los tienen. Desde el punto de vista sintctico, redefiniremos lo que es una

contradiccin (y el lector deber entender en algunos casos por el contexto a qu

nos estamos refiriendo, si a una contradiccin en sentido semntico o en sentido

sintctico).

Definicin: Una contradiccin (en el sentido sintctico) es una frmula de la forma

(AA), siendo A una frmula cualquiera.

Obviamente, la satisfacibilidad es una nocin semntica, relativa a modelos. Para

trabajar con la consecuencia sintctica, introduciremos la nocin de consistencia.

Definicin: Un conjunto de frmulas es consistente si ninguna contradiccin (en

sentido sintctico) es consecuencia sintctica de .

3

Hay una analoga muy evidente entre las nociones semnticas y sintcticas.

Plano semntico Plano sintctico

es una contradiccin: no tiene

modelos

es una contradiccin: es de la

forma (AA)

es satisfacible: tiene al menos

un modelo

es consistente: No existe una

contradiccin (segn el punto de vista

sintctico) que sea consecuencia

sintctica de

Observemos lo siguiente: Toda contradiccin desde el punto de vista sintctico es

una contradiccin desde el punto de vista semntico, pero lo recproco no es cierto.

Por ejemplo, la frmula (PaPa) es una contradiccin desde el punto de vista

semntico pero no lo es desde el punto de vista sintctico.

Con respecto a la relacin entre conjuntos satisfacibles y conjuntos consistentes,

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

consistentes o al revs, o haya conjuntos consistentes no satisfacibles, etc.

Volveremos ms adelante sobre el punto, que es de extremada importancia.

Recordemos que cualquier frmula es consecuencia semntica de un conjunto

insatisfacible, y que si un conjunto tiene como consecuencia semntica a una

contradiccin, se trata de un conjunto insatisfacible, o sea:

Si es insatisfacible, entonces para toda frmula .

Si es una contradiccin y , entonces es insatisfacible.

Mostremos que tenemos resultados anlogos para la relacin de consecuencia

sintctica. (En realidad, para la consecuencia sintctica el anlogo de la segunda

proposicin de arriba sera: Si es una contradiccin (en sentido sintctico) y

, entonces es inconsistente, lo que es simplemente la definicin de conjunto

inconsistente). Demostremos el anlogo de la primera proposicin.

Si es inconsistente, entonces para toda frmula .

Supongamos que es inconsistente. Entonces existe una frmula A tal que

(AA).

Esto significa que existe una derivacin de (AA) en la que las premisas son

elementos de . Introduzcamos la siguiente notacin: Sea PRE(, , ) el conjunto

de premisas de la derivacin de a partir de . Es claro que PRE(, ,) es un

subconjunto de , y que depende de la derivacin 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 derivacin de (AA) a partir de de la siguiente

manera:

(0-k) PRE(, ,)

n. (AA)

significando que colocamos todas las premisas al principio, de las lneas 1 hasta k y

luego aplicamos las reglas hasta obtener (AA) en la lnea n1. Ahora bien, si

tenemos esta derivacin, podemos construir esta derivacin de una frmula

cualquiera B a partir de .

(0-k) PRE(, ,)

(n). (AA)

(n+1) [B] Supuesto

(n+2) A Elim , n.

(n+3) A Elim , n.

(n+4) (AA) Intr , n+2, n+3.

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

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

Como la derivacin utiliza las mismas premisas que la derivacin , y todas

estas son elementos de , esto muestra que B, siendo B una frmula cualquiera.

Hemos demostrado que

Si es inconsistente, entonces para toda frmula

1 Ponemos una lnea numerada con cero para considerar el caso en que no se utilice ninguna frmula

como premisa. En caso de que utilicemos la lnea 0, ser tambin k=0, es decir, no se coloca ninguna premisa en la derivacin.

5

3. Conjunto vaco y teoremas.

Recordemos que al trabajar con consecuencia semntica encontramos algunas

frmulas a las que llamamos vlidas- que son consecuencia semntica del

conjunto vaco y tambin consecuencia semntica de cualquier conjunto. Qu

puede significar que una frmula es consecuencia sintctica del conjunto vaco?

Evidentemente, solo puede significar que se trata de una frmula derivable sin

utilizar premisas. Existen frmulas as. Mostremos que la frmula (xPxxPx) es

consecuencia sintctica del conjunto vaco, es decir, que existe una derivacin 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 frmula que hemos derivado a partir del

conjunto vaco es vlida. Ser esto un ejemplo de una ley general? Estamos lejos

aun de poder responder esa pregunta. Por lo pronto, demos un nombre especfico

al concepto:

Definicin: Una frmula es un teorema si y solo si es consecuencia sintctica del

conjunto vaco.

Obviamente, tambin podemos representarlo as:

Definicin: es un teorema si y solo si .

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

sintctica de cualquier conjunto . La demostracin es inmediata, porque la

derivacin de a partir del conjunto vaco es tambin, por definicin, una

derivacin de a partir de . El recproco, o sea, que si una frmula es

consecuencia sintctica de cualquier conjunto es un teorema, es tambin obvio ya

que si la frmula es consecuencia sintctica de cualquier conjunto tambin lo es, en

particular, del conjunto vaco.

6

Tenemos entonces dos nociones paralelas:

Plano semntico Plano sintctico Frmulas vlidas (Tienen todas las interpretaciones como modelos, son las nicas consecuencias semnticas del conjunto vaco, son consecuencia semntica de cualquier conjunto de frmulas)

Teoremas (Son las nicas consecuencias sintcticas del conjunto vaco, son consecuencia sintctica de cualquier conjunto de frmulas)

Por supuesto, surge inmediatamente el problema de saber cul es la relacin entre

frmulas vlidas y teoremas. Sern las mismas frmulas, ser que hay teoremas

que no son vlidos, ser que hay frmulas vlidas que no son teoremas? Al igual

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

preguntas.

4. Monotona.

Recordemos que la relacin de consecuencia semntica cumpla la propiedad de

monotona: Si , entonces ,.

Es obvio que tambin se tiene que

Si , entonces ,

Esto es as porque cualquier derivacin de a partir de es tambin una

derivacin de a partir de ,.

5. Teorema de deduccin.

Cuando mostramos el teorema de deduccin para la consecuencia semntica

advertimos que se trataba de, justamente, la versin semntica, la cual estableca:

,AB si y solo si (AB)

Es por eso que no resultar sorprendente la noticia de que existe una versin

sintctica, que establece:

,AB si y solo si (AB)

Supongamos que se cumple ,AB.

Esto quiere decir que existe una derivacin de B en la que las premisas

pertenecen al conjunto {A}, en la que podemos incluir la frmula 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 lneas de la

derivacin. Este conjunto es PRE(,{A},B) {A}. Enseguida ubiquemos A, y ya

7

tenemos todo lo necesario para derivar B. La derivacin quedara esquematizada

as:

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

(k+1) A Premisa

(n) B

A partir de esta derivacin podemos construir la siguiente derivacin de la

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

de introduccin 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 derivacin de (AB) partir de , y

mostremos que existe una derivacin de B a partir de ,A.

se puede representar as:

(0-k) PRE(,, AB)

(n) (AB)

Si tomamos esta misma derivacin, le agregamos la frmula A como premisa y

obtenemos una nueva derivacin de otra frmula, esa frmula ser derivada de

,A. Obtengamos de ese modo la frmula 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 ,AB.

Por lo tanto queda demostrado el teorema de deduccin tal cual lo recuadramos

arriba.

6. El absurdo.

Al estudiar la relacin de consecuencia semntica habamos establecido el

siguiente resultado:

si y solo si , es insatisfacible.

El anlogo para la consecuencia sintctica es el siguiente, y como demostraremos,

tambin se cumple.

si y solo si , es inconsistente.

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

una contradiccin. Supongamos que hay una derivacin de a partir de y

mostremos que en ese caso es posible construir una derivacin de una

contradiccin a partir de ,.

Podemos representar as:

( 0-k) PRE(, , )

(n)

Si tomamos esta misma derivacin, le agregamos la frmula como premisa y

obtenemos una nueva derivacin de otra frmula, esa frmula ser derivada de

,. Obtengamos de ese modo una contradiccin:

9

( 0-k) PRE(, ,)

(n)

(n+1) Premisa

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

Esto demuestra que si entonces , es inconsistente.

Para demostrar el recproco, supongamos , es inconsistente, y mostremos

cmo construir una derivacin de a partir de . Al ser , inconsistente,

podemos derivar una contradiccin a partir de l. Representemos esa derivacin

as:

( 0-k) PRE(, {},(BB))- {}

(k+1) Premisa

(n) (BB)

La idea es construir una nueva derivacin en la que se utilizan todas las premisas de las primeras k lneas de la anterior, y se introduce como supuesto, se deriva una contradiccin, y por regla de introduccin de la negacin se concluye :

( 0-k) PRE(, {},(BB)) - {}

(k+1) [] Supuesto

(n) (BB)

(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 sintctica y consecuencia semntica.

Hemos dejado planteadas varias preguntas acerca de la relacin que existe entre

conceptos definidos en trminos de consecuencia semntica y conceptos definidos

en trminos de consecuencia semntica. Recordemos las cuestiones planteadas en

partes anteriores de este trabajo.

Plano semntico Plano sintctico

es una contradiccin: no tiene modelos

es una contradiccin: es de la forma (AA)

es satisfacible: tiene al menos un modelo

es consistente: No existe una contradiccin (segn el punto de vista sintctico) que sea consecuencia sintctica de

Frmulas vlidas (Tienen todas las interpretaciones como modelos, son las nicas consecuencias semnticas del conjunto vaco, son consecuencia semntica de cualquier conjunto de frmulas)

Teoremas (Son las nicas consecuencias sintcticas del conjunto vaco, son consecuencia sintctica de cualquier conjunto de frmulas)

Nos hemos preguntado por las relaciones entre contradicciones en sentido

semntico y sintctico, por las relaciones entre conjuntos satisfacibles y

consistentes, y por las relaciones entre frmulas vlidas y teoremas. Todas estas

cuestiones se podrn responder cabalmente si respondemos a esta pregunta,

absolutamente central:

Cul es la relacin entre la consecuencia semntica y

la consecuencia sintctica?

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

. Asegura eso que ? Y recprocamente, si se cumple , asegura eso

que ?

Pensemos un momento qu significan estas preguntas. Supongamos que se

pudiera dar, para un conjunto y una frmula , que y sin embargo . Esto

querra decir que nuestro sistema formal de deduccin natural nos estara

indicando como consecuencia lgica de un conjunto una frmula que, al no ser

consecuencia semntica del conjunto, ser falsa bajo una interpretacin que hace

verdadera todas las frmulas del conjunto, y por lo tanto, difcilmente la

11

aceptaramos como consecuencia lgica de l. Esta situacin representara una

catstrofe para el sistema de deduccin natural por razones obvias. No nos

asegurara la preservacin de la verdad, no podramos confiar en que la verdad de

las premisas asegura la verdad de la conclusin y para propsitos lgicos, el

sistema vera muy duramente cuestionado su valor. Un sistema en el que esta

indeseable situacin no se da, o sea, un sistema para el cual

Si , entonces

es un sistema correcto.

Vamos a demostrar que nuestro sistema de deduccin natural es correcto. Cmo

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

semntica. Eso nos permite idear la siguiente demostracin: Sabemos que

significa que hay una derivacin de a partir de . Queremos mostrar que cada vez

que esto se da, tambin ser consecuencia semntica de . Consideremos la

longitud de las derivaciones, medida segn la cantidad de lneas 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 conclusin es

consecuencia semntica de las premisas-, habremos logrado nuestro objetivo.

Empecemos considerando el caso en que se da porque hay una derivacin

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 derivacin 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 llevara 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 sera el tedio. Por lo tanto, intentaremos un

camino clsico en matemtica.

Hagamos la hiptesis 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 clsico procedimiento se llama induccin completa y, a pesar de su nombre,

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

son (a) y (b) y su conclusin es que las derivaciones de cualquier longitud son

correctas).

Cmo es que obtenemos derivaciones de longitud mayor que 1? Qu pregunta

tonta, no? Obviamente, lo hacemos agregando lneas, y las lneas se agregan

aplicando reglas o introduciendo premisas o supuestos.

Observemos cuidadosamente qu pasa con los supuestos. Supongamos que

estamos haciendo una derivacin, y en el transcurso de ella introducimos el

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

que tenemos es una derivacin de la ltima lnea a partir de ,A. Esto es lo mismo

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

Cuando lo cancelamos, obtenemos frmulas derivadas con prescindencia de A. De

esa manera podemos considerar que cualquier lnea de una derivacin de a

partir de nos est mostrando que una frmula es consecuencia sintctica de un

conjunto, aunque no necesariamente del conjunto .

13

Por ejemplo:

1. A Premisa

2. B Premisa

Estas frmulas son consecuencia sintctica de

[C] Supuesto

Estas frmulas son consecuencia sintctica de ,C

[D] Supuesto

Estas frmulas son consecuencia sintctica de ,C,D

E

Estas frmulas son consecuencia sintctica de ,C

F

Estas frmulas son consecuencia sintctica de

Desde este punto de vista, cada lnea de una derivacin indica que la frmula que

contiene es consecuencia sintctica de un conjunto. Hagamos ahora la siguiente

hiptesis (para llevar adelante la induccin completa):

Todas las veces que con n lneas o menos se muestra que una frmula es consecuencia

sintctica de un conjunto (entendiendo que se muestra en el sentido indicado arriba,

o sea, la frmula puede ser consecuencia sintctica del conjunto o del conjunto al

que se le han adjuntado los supuestos abiertos), se cumple que tambin es

consecuencia semntica de ese mismo conjunto.

Usando esta hiptesis debemos mostrar:

Todas las veces que con n+1 lnea se muestra que una frmula es consecuencia

sintctica de un conjunto , la frmula es consecuencia semntica de .

Manos a la obra entonces.

Supongamos que y que hay una derivacin de a partir de de longitud n+1.

Queremos demostrar que .

Advertencia: la demostracin del teorema es larga ocupa desde la pgina siguiente, la 14, hasta la 20-, repetitiva

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

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

14

sera deseable que comprendiese la idea que anima la demostracin ms all de ellos. Incluimos la demostracin

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

no simplemente enunciarla.

Nos preguntamos cmo es que apareci la ltima lnea, la que contiene a ?

Obviamente no puede ser un supuesto, porque en ese caso no estaramos frente a

una derivacin. Si es una premisa, trivialmente ya que es elemento de . El

caso que nos queda es que sea el resultado de la aplicacin de una regla a lneas

anteriores de la derivacin. Estudiemos las diversas posibilidades.

1. es el resultado de aplicar la regla Int.. En ese caso la derivacin tiene la

forma:

(i) A

(j) B

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

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos, ni

A ni B pueden depender de supuestos y por lo tanto tenemos, A y B a travs

de una derivacin de n lneas o menos, por lo que segn nuestra hiptesis

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 derivacin tiene la

forma:

(i) () o (i) ()

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

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos,

() no puede depender de supuestos y por lo tanto tenemos () a travs

de una derivacin de n lneas o menos, por lo que segn nuestra hiptesis

()

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 anlogo.

15

3. es el resultado de aplicar la regla Int.. En ese caso la derivacin tiene la

forma:

(i) A o (i) B

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

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos, A

no puede depender de supuestos y por lo tanto tenemos, A a travs de una

derivacin de n lneas o menos, por lo que segn nuestra hiptesis

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 anlogo.

4. es el resultado de aplicar la regla Elim. . En ese caso la derivacin tiene la

forma:

(i) (AB)

(j) [A]

(k) C

(l) [B]

(m) C

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

Mirando la derivacin tenemos que (AB). Adems mirando hasta la lnea k,

vemos que ,A C y mirando hasta la lnea m que ,BC. Todas estas

consecuencias sintcticas surgen de derivaciones de n lneas o menos, por lo que

segn nuestra hiptesis

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 tambin de A o

bien es modelo tambin de B. Pero tanto si se da lo primero como si se da lo

segundo, I ser modelo de C. Contradiccin. Por lo tanto, todo modelo de ser

modelo de C.

5. es el resultado de aplicar la regla Int.. En ese caso la derivacin tiene la

forma:

(i) [A]

(j) B

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

Observando la derivacin vemos que ,AB y esta consecuencia se desprende de

una derivacin de n lneas o menos. Por lo tanto, segn nuestra hiptesis, tenemos

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

ms que una aplicacin del teorema de deduccin en versin semntica.

6. es el resultado de aplicar la regla Elim. . En ese caso la derivacin tiene

la forma:

(i) (AB)

(j) A

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

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos, ni

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

A a travs de una derivacin de n lneas o menos, por lo que segn nuestra

hiptesis

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.

7. es el resultado de aplicar la regla Int.. En ese caso la derivacin tiene la

forma:

(i) []

(j) (BB)

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

Observando la derivacin vemos que , (BB) y esta consecuencia se

desprende de una derivacin de n lneas o menos. Por lo tanto, segn nuestra

hiptesis, tenemos que , (BB). A partir de aqu debemos demostrar que

. Como , tiene como consecuencia semntica una contradiccin, , es

insatisfacible y se sigue, por teorema del Absurdo que .

8. es el resultado de aplicar la regla Elim.. En ese caso la derivacin tiene la

forma:

(i) A

(n+1) A Elim. (i)

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos,

A no puede depender de supuestos y por lo tanto tenemos, A a travs de

una derivacin de n lneas o menos, por lo que segn nuestra hiptesis

A

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

A, adems de los que deberan ser nuestros siguientes dos casos: los de Int. y

Elim. .

18

9. es el resultado de aplicar la regla Elim.. En ese caso la derivacin tiene la

forma:

(i) xA(x)

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

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos,

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

travs de una derivacin de n lneas o menos, por lo que segn nuestra hiptesis

xA(x)

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

A(), lo que es una aplicacin directa de la clusula pertinente de la definicin

de Interpretacin en LPO.

10. es el resultado de aplicar la regla Int.. En ese caso la derivacin tiene la

forma:

(i) A()

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

Recordemos que no aparece en ninguna frmula de . No es necesario

considerar supuestos sin cancelar porque al tratarse de una derivacin no los hay.

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos,

A() no puede depender de supuestos y por lo tanto tenemos, A() a travs de

una derivacin de n lneas o menos, por lo que segn nuestra hiptesis

(1) A()

donde no aparece en ninguna frmula de que se utilice en la derivacin como

premisa. Debemos demostrar que en estas condiciones se cumple

(2) xA(x).

Lo haremos por contrarrecproco. Supongamos que no se cumple (2) o sea que

existe una interpretacin I sobre una estructura E tal que I es modelo de todas las

frmulas 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 interpretacin J de la siguiente manera:

J acta 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 frmulas de , se tiene que bajo esta nueva

interpretacin todas las frmulas 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).

11. es el resultado de aplicar la regla Int.. En ese caso la derivacin tiene la

forma:

(i) A()

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

Y no aparece en la frmula A(x).

Como la ltima lnea se obtiene a travs de una regla que no cancela supuestos,

A() no puede depender de supuestos y por lo tanto tenemos, A() a travs de

una derivacin de n lneas o menos, por lo que segn nuestra hiptesis

A()

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

xA(x).

20

12. es el resultado de aplicar la regla Elim. . En ese caso la derivacin tiene la

forma:

(i) xA(x)

(j) [A()]

(k) B

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

Observando la derivacin hasta la lnea (i) vemos que xA(x). Adems mirando

hasta la lnea k, vemos que ,A() B. Todas estas consecuencias sintcticas

surgen de derivaciones de n lneas o menos, por lo que segn nuestra hiptesis

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 acta sobre una estructura

E. Si I es tambin 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

contradiccin. 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

interpretacin J sobre una estructura E idntica a E excepto en que asigna el

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

en las frmulas de , ni en B, los valores de verdad de las frmulas 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 metaterico tan fundamental que podemos

decir lo siguiente: si no valiera, deberamos tirar el sistema de deduccin natural a

la basura y adoptar otro. Lleva el nombre de

21

Teorema de correccin

Para todo conjunto de frmulas y toda frmula ,

si entonces .

En particular esto demuestra, tomando = que

Si es un teorema, entonces es una frmula vlida

Supongamos que es inconsistente. Entonces tiene como consecuencia

sintctica a una contradiccin, y por lo tanto, tiene como consecuencia semntica a

una contradiccin. 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 frmulas vlidas que no son teoremas? Hay conjuntos

consistentes insatisfacibles? Con mayor generalidad, siempre que sea , ser

?

Pensemos qu significara una respuesta negativa a la ltima pregunta. Si fuera el

caso de que hubiera un conjunto y una frmula tales que pero ,

tendramos que nuestro sistema formal no podra capturar todas las consecuencias

semnticas de un conjunto. No es una situacin tan grave como la incorreccin,

pero representara un resultado que marcara lmites a la capacidad de nuestro

sistema para descubrir las consecuencias lgicas 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 travs 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, tendra k

elementos, siendo k un nmero natural, y en ese dominio la proposicin Existen al

menos k+1 elementos con la propiedad P y todas las siguientes seran falsas.

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

primer orden con identidad. Por ejemplo, la primera proposicin se puede traducir

como (xPxxPx) y la segunda como xy((PxPy) xy).

Agreguemos a ese conjunto la siguiente proposicin:

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

Obviamente, el conjunto formado por todas las proposiciones numeradas con

nmeros naturales y la proposicin 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 proposicin etiquetada con ). Supongamos adems que

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

contradiccin de ? Respuesta: No. Sera imposible. Por qu? Porque una

derivacin 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 nmero ms alto de proposicin que tomamos como premisa

es k, y sin importar si tomamos o no como premisa a la proposicin 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 contradiccin 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 Lgica 2.

Est bien, a pedido del pblico vamos a dar algunos avances. Segn la humilde

opinin de quien escribe, los tres lgicos ms grandes de la historia son, por orden

cronolgico, Aristteles (384 a.C.-322 a.C.), Frege (1848-1925) y Gdel (1906-

1978). De Aristteles, creador de la Lgica, no es necesario que diga nada, ya que

tanto nomini nullum par elogium, es el intelecto ms poderoso que ha dado la

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

ms poderosos que existen. A Frege se le debe el ms importante avance en la

ciencia de la lgica desde que su creacin por Aristteles: un sistema lgico con la

potencia de LPO. Explicar los aportes de Gdel es un poco ms complejo, pero hizo

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

entender:

Teorema de completitud (Gdel, 1930)

LPO es completo, o sea, si , entonces

Gdel no lo demostr para nuestro sistema de deduccin natural por la perentoria

razn de que ste no haba sido aun descubierto. (El sistema es debido a Gentzen

(1909-1945), un brillante lgico alemn que trabaj en la Checoslovaquia ocupada

bajo el rgimen nazi y termin muriendo como prisionero de los soviticos a fines

de la Segunda Guerra Mundial. Curiosamente, tanto Gdel como Gentzen murieron

de inanicin. Gdel desarroll una paranoia y dej de comer porque crea que lo

queran envenenar). Gdel 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 Gdel trabajaba es derivable en DN.

Esta bicoca fue la tesis doctoral de Gdel. Posteriormente hizo descubrimientos de

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

los lgicos ms importantes de la historia.

Todo esto es muy impresionante, pero no demostramos antes que haba un

conjunto insatisfacible y consistente? Eso sera un contraejemplo del Teorema de

Completitud de Gdel, porque si el conjunto es insatisfacible tiene como

consecuencia semntica a cualquier proposicin, y ya vimos que no podemos

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

sintctica a cualquier proposicin.

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

consideracin del conjunto es algo muy notable: No es posible expresar en LPO la

proposicin etiquetada como . Si fuera posible hacerlo, s tendramos un

contraejemplo.

24

Esto nos muestra algo importante: LPO tiene lmites expresivos. No debera 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 ms hay para estudiar en Lgica?

La lgica es, como cualquier ciencia, un universo. Por supuesto que en ese universo

algunas cosas nos son ms cercanas que otras. Las preguntas que naturalmente

surgen desde el lugar en que estamos situados son:

Pregunta 1: Cmo se demuestra la completitud de LPO?

Respuesta: Curse lgica 2.

Pregunta 2: Podemos hacer de nuestro sistema DN algo mecnico, como lo son las

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

Respuesta: DN no es reductible a un sistema mecnico. Para saber por qu, curse

Lgica 2.

Pregunta 3: Est bien, aplicar DN requiere ingenio, pero, existe algn sistema

mecnico para determinar si una frmula es consecuencia lgica 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 Lgica

2.

Pregunta 4: Ac hablan de un tal Teorema de completitud de Gdel, pero una vez

yo le un libro de sociologa (o de lingstica, o de psicologa, o incluso de divulgacin

cientfica) en el que se mencionaba un tal Teorema de INcompletitud de Gdel. El

error es de estas notas o del libro?

Respuesta: Existe el Teorema de Completitud de Gdel y tambin el Teorema de

Incompletitud de Gdel, que refiere a sistemas matemticos, no exclusivamente

lgicos. Advertencia: si el libro en el que encontr la referencia no es de divulgacin

cientfica, lo ms 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

pgina se encuentra el sinsentido. Si quiere conocer exactamente el enunciado del

Teorema de incompletitud, lo que establece, curse Lgica 2. Si adems es un alumno

muy aplicado, podr ver alguna demostracin.

Pregunta 5: Cules son los lmites expresivos de LPO?

Respuesta: Segn desde dnde se mire, estn muy lejos o ah noms, cerquita. Si

quiere saber ms sobre eso, curse Lgica 2.

25

Pregunta 6: Hay otros lenguajes, otras lgicas?

Respuesta: Por supuesto. Y algunos son ciertamente tiles en filosofa. Pero es un

tema demasiado amplio para tocarlo aqu hacindole un mnimo de justicia.

Tambin queda para Lgica 2.

Pregunta 7: Todo bien con la deduccin, pero, qu pasa con las inferencias no

deductivas?

Respuesta: Excelente pregunta. Lo esperamos en el seminario del segundo semestre

de 2012, que tratar sobre lgica inductiva.

Al finalizar no queda ms que decirles que esperamos que hayan aprendido como

alumnos del curso tanto como nosotros aprendimos preparndolo. Que el espritu

aristotlico los acompae por el resto de sus das.