Logica de Primer Orden. Jesus Moster¡n

JESÚS MOSTERÍN

LOGICADEPRIMERORDEN

A R IE L

Jesús Mosterín

LÓGICA DE PRIMER ORDEN

Desde finales del siglo xix, y después de un letargo de 2.000 años, la lógica se ha desarrollado a un ritmo acelerado, convirtiéndose en upa de las ciencias formales más sólidas y bien establecidas. Actualmente, algunos conocimientos básicós de lógica resultan imprescindibles al filósofo y al matemático, e incluso al lingüista, al programador y al interesado por la teoría de la información o la cibernética.Las ramas de la filosofía contemporánea que han logrado un progreso indudable y un rico acopio de resultados y aclaramientos fecundos — tales como la filosofía de la ciencia y la filosofía del lenguaje— se basan en la aplicación de técnicas y conceptos lógicos al análisis de sus problemas. Incluso en campos tan aparentemente alejados como la ética se empieza a hacer uso de la lógica como potente instrumento de dilucidación y sistematización. Y no pocos filósofos actuales piensan que la filosofía entera no es otra cosa sino la actividad del análisis lógico.El progreso de la lógica llevó a principios de siglo al descubrimiento de las paradojas de la teoría de conjuntos y, con ello, a la más grave “crisis de fundamentos” de la matemática moderna. Pero precisamente con ayuda de la lógica se encontraron también las diversas soluciones a la crisis: teorías axiomáticas de conjuntos, teoría de tipos, matemática intuicionista, etc. Las relaciones entre lógica y matemática son estrechas y sus fronteras arbitrarias. Respecto a los conceptos fundamentales de la teoría de conjuntos nadie sabría afirmar si son lógicos o matemáticos. Y en la metamatemática logramos obtener resultados inequívocamente matemáticos por procedimientos lógicos y resultados típicamente lógicos por procedimientos matemáticos. En cierto modo, se puede decir que la matemática se reduce a la lógica, pues la actividad matemática consiste en deducir consecuencias (teoremas) a partir de axiomas dados. En otro sentido se puede decir que la lógica se reduce a la matemática, de la que constituye la parte más general.La asimilación de las nociones y técnicas lógicas elementales facilita grandemente la labor del lingüista, del programador, del cibernético, etc. Recuérdese la importancia de la lógica en el desar r o l l o de la leería general de la computabilidad o de las máquinas do Turing. Recuérdese también quel a s C O I ! K M des lingüísticas más recientes — gramá-1 i r a g O l l i M aliva y 1 ransformaeional de Chomsky,K . U / . ele. halan de obtener para los lenguajes■ m i l l í a l e ; . ,con | ui i los de reglas o algoritmos recur-' . 1 V‘ i ) d e g , i M i e r a e i o n similares a los empleados parad rl i i in lo-, fm malí.-.mos lóg ieos. I n c lu s o e n l a p s i - lo l. ijpi i, 111 p e d a g o g í a v la j u r i s p r u d e n c i a e n c u e n t r a I a o 'U din I < i l o g a n ap i lene iones.

w.áq-,1 / in v /m ' in )

COLECCION «CONVIVÍUM» - 11

LÓGICA DE PRIMER ORDEN

COLECCION CONYIVIUM

1. Historia del espíritu griego

2. Metafísica

3. Literatura latina

4. Introducción a la latín

por Wilhelm Nestle

por Emerich Coreth

por Jean Bayet

sintaxis estructural del

por Lisardo Rubio

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

ABC de la grafologíapor J. Crépieux-Jamin

Literatura griega. Contenido, problemas y métodos

por José Alsina

Tragedia y política en Esquilopor Carlos Miralles

La investigación científicapor Mario Bunge

Historia de la filosofíapor Frederick Copleston

Introducción a la lógica y al análisis formal

por Manuel Sacristán

Lógica de primer ordenpor Jesús Mosterín

Los orígenes de la civilización anglosajonapor Micaela Misiego

Teoría axiomática de conjuntospor Jesús Mosterín

Hipócrates y la nosología hipocráticapor Eulalia Vintró

Salustio. Política e historiografíapor José-Ignacio Ciruelo

Cálculo de las normaspor Miguel Sánchez-Mazas

JESÚS MOSTERlN

L Ó G I C ADE P R I M E R ORDEN

EDITORIAL ARIEL BARCELONA - CA R A C A S - MÉXICO

1. * edición: 19702. a edición: septiembre de 1976

© 1970 y 1976: Jesús Mosterín, Barcelona

Depósito legal: B. 3 5 7 5 9 - 1976 ISBN: 84 344 3939 5

Impreso en España

1976. — ■ I. G. Seix y Barra! Unos., S. A.Av. J. Antonio, 134, Esplugues de Llobregat (Barcelona)

PROLOGO A LA PRIMERA EDICIÓN

Numerosas ciencias, desde la matemática hasta la meteorología, pasando por la química, utilizan símbolos. Así también lo hace la lógica, desde que ésta se constituye en ciencia en 1879, con la publicación del Begriffsschrift de Frege. El simbolismo usado por Frege tenía el inconveniente de ser bastante complicado — las variables, por ejemplo, tenían distinta forma., según que estuviesen libres o ligadas — y, además, era bidimensional. Estos inconvenientes fueron eliminados por Peano, que en 1894, en su Notation de logi- que mathématique, introdujo el primer simbolismo lógico simple y unidimensional. El simbolismo de Peano, convenientemente ampliado, fue adoptado por Russell y Whvtehead en sus Principia Mathematica, de 1910-13. Sin embargo, pronto se vio que este simbolismo no era muy elegante, pues sus signos no reflejaban algunas importantes relaciones entre las operaciones por ellos designadas, tales como la dualidad entre conyunción y disyunción, la equivalencia del hicondícional con dos condicionales de direcciones opuestas, la relación entre conyunción y cuantificación universal o entre disyunción y cuantificación existencial, etc. Por esta razón, el simbolismo de Peano ha ido siendo abandonado (aunque algunos autores, como Quine, aún lo conservan) en favor de simbolismos más adecuados (en el sentido indicado) y elegantes.

Desgraciadamente, todavía no se ha. llegado a una uniformidad en los signos lógicos empleados. En este libro adoptaremos el simbolismo que nos parece más intuitivo y que más claramente refleja las relaciones arriba indicadas. Actualmente, este simbolismo es de uso universal en Alemania y la parte oeste de los Estados Unidos (California, etc.).

La definición de la sustitución plantea serias dificultades. La primera versión completamente explícita de un sistema lógico de primer orden, la de Hilbert y Ackermann de 1928, resultó inconsistente por una mala definición de la sustitución. Tarski ha'mostrado en 1951 cóm.o la sustitución puede ser evitada. Sin embargo, el disponer de la sustitución en todo su alcance y potencia simplifica enormemente las deducciones y la metateoría.

Al contrario de lo que frecuentemente pasa en la bibliografía lógica, en las páginas 42-43 de este libro se presenta una definición recursiva exacta

6 PRÓLOGO

de la sustitución para todos los casos, incluidas las fórmulas cu-antificadas y las descripciones.

En la mayoría de los libros de texto de lógica se introducen formalismos de primer orden sin identidad ni functores y, en cualquier caso, sin descripciones. Para estos formalismos pobres se definen los conceptos y se presenta un cálculo deductivo. Pero esto es de poca utilidad, pues cualquier teoría matemática o cualquier argumentación filosófica, a poco complicada que sea, necesita para su formalización de la identidad, los functores y las descripciones. La teoría de conjuntos, por ejemplo, hace uso de las descripciones a cada paso. Esto suele arreglarse mencionando estos temas en un apéndice al final.

Una de las peculiaridades de este libro es que aquí, desde un principio, se introducen los formalismos de primer orden en toda su potencia, incluyendo la identidad, los functores y las descripciones. Esta presentación exige un mayor esfuerzo inicial por parte del lector o alumno, pero representa una gran economía de esfuerzos al final, pues no hay que volver una y otra vez sobre lo mismo, complicándolo cada vez un poco más.

Una de las tareas más importantes de la lógica consiste sin duda alguna en el desarrollo de algoritmos generales que nos permitan “mecanizar” o normalizar determinados procesos intelectuales. Especialmente importantes son los algoritmos o cálculos deductivos, que nos permiten mostrar la corrección de las argumentaciones válidas, desarrollar las teorías axiomáticas, precisar el concepto de prueba o demostración, etc.

El primer cálculo deductivo fue presentado por Frege en su citado trabajo de 1879. Los cálculos lógicos posteriores a 1879 y anteriores a 1934 estaban formulados — igual que el de Frege — como sistemas axiomáticos. Había, por un lado, una serie de “axiomas lógicos” y, por otro, una serie de reglas de inferencia. La aplicación de estos cálculos resultaba engorrosa y artificial, y se parecía poco al proceso del razonamiento no formalizado, que parte de las premisas, y, paso a paso, llega a la conclusión. En 1934 Gentzen presentó los dos primeros cálculos lógicos sin axiomas y con sólo reglas de inferencia, cuya aplicación resulta más familiar y natural que la de los viejos cálculos, por lo que los llamó cálculos “de deducción natúral”. A partir de entonces se han presentado diversas variantes y simplificaciones de la idea de Gentzen.

Aqui presentamos el cálculo deductivo expuesto por Kalish y Montague en 1964. Aunque un poco complicado a primera vista, resulta luego sorprendentemente fácil de manejar y de aplicar. Además, tiene la ventaja de seguir muy de cerca el proceso normal de la prueba matemática. El lector que conozca otros cálculos observará que le resulta más fácil obtener deducciones en este cálculo que en los otros. En este sentido, es el cálculo más “natural” que conozco. Ni que decir tiene que todos los cálculos clásicos de primer orden son equivalentes, es decir, que con ellos pueden deducirse las

PROLOGO 7

mismas sentencias. Por eso, a la hora de elegir un cálculo entre otros, no cabe más que invocar motivos pragmáticos o estéticos — en este caso, más bien pragmáticos que estéticos, pues hay cálculos mucho más elegantes, aunque también mucho más difíciles de manejar y aplicar.

En este libro se presenta la semántica de los formalismos de primer orden de un modo riguroso, comenzando por el concepto de interpretación de un formalismo y siguiendo por la dilucidación de los conceptos de satisfacibilidad, consecuencia, etc., llevada a cabo en el sentido de Tarski.

La semántica aquí presentada es la semántica clásica, no la intuicionista. (Esto no implica juicio alguno de valor.) La semántica clásica está perfectamente fijada. El único punto problemático es el de la interpretación de las descripciones, donde hemos adoptado una solución tipo Frege-Carnap-Mon- tague, asignando una designación arbitraria, pero única en cada interpretación, a todas las descripciones impropias. La solución resulta artificiosa y poco intuitiva, pero es la más cómoda a la hora de formalizar y manejar el cálculo. El mismo Quine, que siempre había preconizado una solución tipo Russell, a la hora de hacer teoría, en su Set theory and its logic, adopta una solución del mismo tipo que la aquí adoptada, para no complicarse exageradamente al vida.

En la parte de semántica se ofrece la prueba detallada y entera del fundamental teorema de la completud semántica de nuestro cálculo deductivo. Este resultado fue obtenido por primera vez por Gódel, en 1930. En 1949 Henkin ofreció una prueba distinta y más simple del mismo resultado. En 1957, Kalish y Montague realizaron la prueba de la completud semántica referida al cálculo aquí presentado — más rico que el tomado como base por Gódel y Henkin. La prueba que nosotros ofrecemos representa una notable modificación y simplificación de la de Kalish y Montague, aprovechando ideas de Hasenjaeger y Hermas.

Sólo a los lógicos puros — que son muy pocos — interesa la lógica por sí misma. La mayoría de las personas — filósofos, matemáticos, etc. — que se interesan por la lógica se interesan sobre todo por sus aplicaciones. Saber aplicar la lógica, dominar la lógica como arte, consiste sobre todo en saber probar que una sentencia dada es o no es una consecuencia de un conjunto dado de sentencias, es decir, en saber hacer deducciones y pruebas de independencia. Y esto, más que una teoría, es una praxis, que sólo se aprende practicándola. La experiencia muestra que los estudiantes encuentran dificultades a la hora de buscar ocasiones de practicar, ejercicio resueltos. Por eso en este libro se ofrece una cantidad considerable de ejercicios de deducción y de prueba de independencia, que espero resulten útiles al lector.

Este libro es de texto en el sentido estricto o estrecho de la palabra. Ha surgido de las clases de lógica que el autor ha dado en la Universidad de Barcelona en los últimos cuatro años y está destinado a servir de texto a cursos de lógica de nivel universitario.

8 PROLOGO

Para acabar, desearía expresar aquí mi agradecimiento a Hans Hermas, de quien he sido discípulo durante tres años, en Münster, y a los estudiantes de lógica de la Universidad de Barcelona de los cuatro últimos cursos, cuyo sentido de la crítica y del humor ha constituido para mí un constante aliciente y una continua satisfacción.

Barcelona, junio de 1970.J esús M osterín

PRÓLOGO A LA SEGUNDA EDICIÓN

Los manuales de lógica aparecidos en nuestro país en los seis años transcurridos desde la primera edición de esta obra han adoptado el sistema de signos lógicos aquí propuesto, lo cual no puede por menos de contribuir a la deseable uniformización de la terminología científica.

En esta segunda edición se han corregido erratas y descuidos de la primera y se han añadido algunos ejemplos. Pero el carácter y articulación de la obra permanecen inalterados: la lógica de primer orden con functores, identidad y descripciones se presenta de una vez y desde el principio de un modo escueto y preciso, con la mayoría de las pruebas plenamente desarrolladas y con abundantes ejemplos y ejercicios que faciliten la asimilación de ¡as técnicas formales por parte del estudiante.

Agradezco sus observaciones a cuantos lectores me las han hecho llegar, y en especial a Calixto Badesa.

J esús M osterín

Barcelona, junio de 1976.

Í N D I C E

Prólogo a la primera edición .............................................. 5Prólogo a la segunda e d ic ió n ..................................................................... 8

INTRODUCCIÓN

1. N om b res................................................................................................... 132. Functores.................................................................................................... 143. S e n t e n c i a s ......................................... .................................................. 154. P r e d i c a d o s ............................................................................................ 165. C o n e c t o r e s ............................................................................................ 176. Variables................................................................................................... 197. Términos y fórmulas ............................................................................. 198. C u an tificad ores.................................................................................... 219. Descripciones........................................................................................... 22

10. P a r é n t e s i s ........................................................................................... 2411. F o r m a liz a c ió n .................................................................................... 2512. Form alism os............................................................................................ 2713. Lenguaje y metaleriguaje..................................................................... 27

P a rte prim era

SINTAXIS: GRAMÁTICA DE LOS FORMALISMOS

1.1. Signos comunes a todos los formalismos...................................... 311.2. Signos peculiares de un formalismo . . . . . . . 321.3. Filas de s i g n o s .................................................................................... 341.4. Términos y fórmulas..................................................... 351.5. Inducción se m ió tica ............................................................................. 371.6. Estancia libre y ligada de una variable ....................................... 391.7. Sustitución de una variable por un té r m in o ................................. 411.8. Convenciones notacionales . . . . . . . . . 43

P a rte segunda

SINTAXIS: UN CÁLCULO DEDUCTIVO

11.1. Reglas primitivas de in fe re n c ia ...................................................... 4911.2. D educciones.................................................................................................. 5111.3. Reglas derivadas de in f e r e n c ia ...................................................... 5411.4. Ejercicios de d e d u cció n ..................................................................... 5711.5. Teoremas sintácticos sobre la deducibilidad............................... 8811.6. Cuasieliminación de descriptores...................................................... 9311.7. Consistencia y contradicción............................................................. 9711.8. Consistencia máxima y ejem plificación................................................100

P a rte tercera

SEMÁNTICA

111.1. Interpretaciones . 107111.2. Denotación y satisfacción.............................................................................. 109111.3. Interpretación y su stitución ...................................................................... 111111.4. Satisfacibilidad, validez y co n secu en cia ................................................115111.5. In d e p e n d e n c ia ..............................................................................................117111.6. Ejercicios de prueba de in d ep en d en cia................................................119111.7. Corrección semántica......................................................................................127111.8. Consistencia y sa tisfa cib ilid a d ............................................................... 129111.9. Completud s e m á n t ic a .............................................................................. 136

Bibliografía . 139

IN T R O D U C C IÓ N

La cadena sonora que sale de nuestras bocas al hablar puede ser segmentada de diversas maneras. De la mayoría de los segmentos no tendría sentido preguntar por el objeto o individuo al que se refieren o designan. No designan objeto alguno. A los segmentos de la cadena sonora que se refieren a algún objeto o individuo les llamamos designadores.

Si en vez de analizar la cadena sonora analizamos textos escritos, nos encontraremos en una situación parecida. Podremos segmentar los textos (o sucesiones finitas de signos gráficos del alfabeto de que se trate, ampliado para abarcar los signos de puntuación y el espacio de separación) de muchas maneras. Algunos segmentos de texto designarán quizás algo o a alguien, y les llamaremos designadores. La mayoría no designan nada, no se refieren a nada.

Hay muchos tipos de designadores. Uno de los más sencillos está constituido por los nombres.

Todos conocemos ejemplos de nombres. Por ejemplo, “1”, “2”, “3 ”, “4 ”, “5”, “6” ... son nombres de números. “París”, “Roma”, “Barcelona”, “Reus”, “Sao Paulo”, “Yokohama”... son nombres de ciudades. “Pablo Picasso”, “Andró Gide”, “José María de Porcioles”, etc., son nombres de personas. “Marte”, “Tierra”, “Venus” ... son nombres de planetas. “R EN FE”, “UNESCO”, “ONU”, “NATO” ... son nombres de empresas u organizaciones.

Los nombres son —limitando ahora nuestra atención al lenguaje escrito— sucesiones de signos gráficos que designan algo — un número, una ciudad, una persona, un planeta, una empresa...— . En esto se comportan como el resto de los designadores, de los que se diferencian por ser generalmente más cortos, más sencillos, más unívocos, más independientes del contexto.

Si digo: “yo he comido machacamoya”, “yo” actúa como designador, es un designador que se refiere a mí. Pero su referencia variará con el contexto, con la persona que pronuncie esa sentencia. Podría decir lo mismo, diciendo “Jesús Mosterín ha comido machacamoya”, utilizando el

1. Nombres

14 INTRODUCCION

nombre “Jesús Mosterín”, cuya referencia permanecerá invariable, utilice la sentencia quien la utilice. En este caso, pues, aunque el nombre era más largo que el otro designador — el pronombre “yo" — , resultaba más unívoco, más independiente del contexto.

Vamos a ir introduciendo un simbolismo sencillo para formalizar las expresiones lingüísticas que nos interesen. Así, en vez de los nombres del lenguaje ordinario, nosotros utilizaremos las primeras letras minúsculas del alfabeto latino: a, b, c, e, k, si es necesario con subíndices de diferenciación(íifl, di, d%, ..., etc.).

Consideremos el texto: “Charles de Gaulle vive en París, que es la capital de Francia”. Podemos simbolizar a “de Gaulle” por a, “París” por b, y “Francia” por e, con lo que obtenemos: “a vive en b, que es la capital de e”.

2. Functores

Los norfibres son designadores simples, en el sentido de que ninguna parte propia de ellos es a su vez un designador. Pero no todos los designadores son así. Con frecuencia nos encontramos con designadores compuestos, designadores que pueden segmentarse en varias partes, algunas de las cuales son a su vez designadores.

“El río que atraviesa la capital de Francia” es un designador, una expresión lingüística que se refiere a un objeto o individuo: el río Sena. “Sena” es su nombre, pero no la única expresión que lo designa. “La capital de Francia” es, una parte propia del designador citado y, a su vez, un designador, e incluso un designador compuesto también, pues una de sus partes, “Francia”, es ella misma un designador; un designador simple en este caso, es decir, un nombre.

Hay algunas expresiones lingüísticas que, seguidas de un número determinado de designadores, forman a su vez un designador. Estas expresiones se llaman functores.

Un functor que, seguido de un designador de cierto tipo, forma un designador, se llama functor monádico o monario. Así, hablando de personas, “la madre d e ...” es un functor monádico. Junto con los designadores personales “Pablo VI” o “Juan Ramón Jiménez” forma los designadores “la madre de Pablo VI” o “la madre de Juan Ramón Jiménez”. Hablando de números naturales, “...2” o “el siguiente d e ...” son functores monádicos. Junto con los designadores “3” o “4” forman los designadores “32” y “el siguiente de 3”, o “42” y “el siguiente de 4”.

Un functor que necesita de dos designadores de un cierto tipo para formar un nuevo designador se llama functor diádico o binario. Así, hablando de números naturales, “el máximo común divisor de... y...”, “el mínimo común múltiplo de... y...” son functores diádicos.

SENTENCIAS 15

Junto con los dos designadores 7 y 5 forman los designadores “el m.c.d. de 7 y 5”, “el m.c.m. de 7 y 5”, “7 + 5”, “7 ■ 5”.

Un functor que necesita de tres designadores para formar un nuevo designador se llama functor triádico o temario. En general, un functor que necesita de n (donde n es un número natural cualquiera) designadores para formar un nuevo designador se llama un functor n-ádico o n-ario.

Obsérvese que los nombres señalan simplemente su objeto de referencia sin indicar nada acerca de él, mientras que los designadores compuestos (de un functor y otros designadores) señalan su objeto de referencia indicando alguna relación en que ese objeto está con los otros objetos designados por los designadores componentes. Así, el nombre “9 ” no indica nada del objeto al que se refiere, mientras que su designador compuesto “32” indica que es el cuadrado de 3. Lo mismo puede decirse de “París” y “la capital de Francia”, etc.

En nuestra simbolización, en vez de los functores del lenguaje ordinario, utilizaremos las siguientes letras minúsculas del alfabeto latino: f, g, 7i, si es necesario con subíndices de diferenciación (/0, fi, /2,---) etc.). Cuando lo creamos oportuno, indicaremos el número ádico o ario de un functor (es decir, el número de designadores que necesita para formar un nuevo designador) colocándolo en la parte superior derecha de la letra con que lo simbolicemos. Así, si “/ ” es un functor triádico y queremos indicarlo, escribiremos “f3”.

Consideremos el texto: “El padre de Juan Sebastián Bach también era músico”. Podemos simbolizar al nombre “Juan Sebastián Bach” por o, y al functor “padre d e ...” por /, con lo que obtenemos, escribiendo delante el functor: “fa también era músico”.

3. Sentencias

Un designador se refiere a algo. “El Sena”, lo mismo que “El río que atraviesa la capital de Francia”, se refiere al río Sena. Pero ¿qué sentido tendría preguntar si “el Sena” es verdadero o falso? Ninguno, evidentemente. De muchos de los segmentos en que podemos dividir la cadena sonora que sale de nuestras bocas o los textos escritos que salen de nuestra mano no podemos decir que sean verdaderos o falsos. Sólo de algunos. A éstos les llamamos sentencias. Una sentencia es una expresión lingüística de la que podemos decir que es verdadera o falsa, aunque no sepamos si es lo uno o lo otro.

Así, por ejemplo, “París es la capital de Francia”, “5 + 5 = 12” y “Tengo unas ganas enormes de cantar” son sentencias. La verdad o falsedad de las sentencias depende con frecuencia del contexto. “Ayer fui al cine” puede ser verdadera o falsa, según la persona que la diga y el día en que la diga. Nosotros nos interesaremos por sentencias que sean lo más

2 . — L Ó G I C A D E P R I M E R O R D E N

1 6 INTRODUCCION

independientes posible del contexto, tales como muchas sentencias científicas o notariales. Al decir “Ayer fui al cine” digo lo mismo que al decir “el día 8 de enero de 1969 jesús Mosterín fue al cine”, pero esta segunda sentencia es mucho más independiente del contexto que la primera.

Hemos visto que podemos establecer una correspondencia entre desig- n adores del lenguaje y objetos del mundo. Algunos filósofos han buscado una correspondencia parecida para las sentencias, y han creído encontrarla en los hechos. Así como un nombre designa un objeto, una sentencia pretendería describir un hecho. De una sentencia diríamos que es verdadera, si realmente describe un hecho; y que es falsa, en el caso contrario.

4. Relatores

Habíamos visto que hay expresiones lingüísticas que, junto con un número determinado de designadores, forman un nuevo designador. Las habíamos llamado functores. Del mismo modo podemos observar que hay expresiones lingüísticas que, junto con un número determinado de designadores, forman una sentencia. Las llamaremos relatores.

Un relator que, seguido de un designador de un cierto tipo, forma una sentencia se llama un relator monádico o monario. Así, hablando de personas, “... es bueno”, “... está enfermo”, ronca terriblemente”, vive en una casa de campo en las afueras de Amsterdam” son relatores moiuí- dicos. Junto con designadores tales como “Juan Peláez”, “el rey de Thailandia”, “el padre de Juan Peláez” y “el alcalde de Amsterdam”, forman sentencias tales como “Juan Peláez es bueno”, “el rey de Thailandia . está enfermo”, “el padre de Juan Peláez ronca terriblemente” y “el alcalde de Amsterdam vive en una casa de campo en las afueras de Amsterdam”.

Un relator que necesita dos designadores para formar una sentencia se llama un relator diádico o binario. Así, hablando de personas “ ... ama a . . .”, y es mucho más alto que . . . ” son relatores diádicos. Junto con designadores tales como “Juan Peláez”, “la hija mayor del alcalde de Amsterdam”, “Julio Quebrantahuesos” y “el rey del Nepal”, forman sentencias tales como “Juan Peláez ama a la hija mayor del alcalde de Amsterdam” y “Julio Quebrantahuesos es mucho más alto que el rey del Nepal”.

Un relator que necesita tres designadores para formar una sentencia se llama un relator triádico o ternario. Así, hablando de ciudades, " ... está situada entre ... y . . .” es un relator triádico. Junto con designadores tales como “Zaragoza”, “Madrid” y “Barcelona” forma sentencias tales como “Zaragoza está situada entre Madrid y Barcelona”.

En general, un relator que necesita n designadores para formar una sentencia se llama un relator n-ádico o « ario.

En nuestro simbolismo, emplearemos las letras mayúsculas del alfabeto latino H, P, Q, R, S para representar los relatores del lenguaje ordinario.

CONECTORES 17

Sí es necesario, emplearemos subíndices de diferenciación : Po, Pi, P2, Cuando lo creamos oportuno, indicaremos el número ádico o ario de un relator (es decir, el número de designadores que necesita para formar una sentencia) colocándolo en la parte superior derecha de la letra con la que lo simbolicemos. Así, si R es un relator diádico y queremos indicarlo, escribiremos R*.

Consideremos el texto: “Juan ama a su madre, pero no aguanta a doña Leovigilda”. Podemos simbolizar el nombre “Juan” por a, el nombre “doña Leovigilda” por h, el functor “la madre de . . . ” por /, el relator

ama a .. .” por P y el relator " ... aguanta a . . . ” por Q. Escribiendo el relator delante de los designadores con los que forma una sentencia, obtenemos :

Paja, pero no Qab.

■5. Comedores

Hay ciertas expresiones de las que no se puede decir que sean designadores o sentencias, pero que desempeñan un importante papel en la formación de sentencias compuestas a .partir de otras más simples. Éste es el caso, por ejemplo, de algunas de las partículas que los gramáticos llaman conjunciones: “y”, “o”, “no”, “pero”, “si ... entonces . . .”, etc.

Estas partículas sirven, entre otras cosas, para determinar el valor de verdad (es decir, si es verdadera o falsa) de la sentencia compuesta en función de los valores de verdad de las sentencias simples que la componen. Así, una sentencia como “Juan duerme y Pedro estudia” será verdadera en el caso y sólo en el caso de que tanto la sentencia “Juan duerme” como la sentencia “Pedro estudia” lo sean.

En nuestro simbolismo, utilizaremos el signo “~i” para representar la partícula “no” y otras de función parecida” tales como “ni”, “no es el caso que”, etc. Así, representaremos la sentencia “no Qab” por i Qab”.

Para representar la partícula “y”, así como otras de función parecida, como “también”, “pero”, “igualmente”, “tanto ... como”, etc., utilizaremos el signo “a ”. A sí representaremos “Paja, pero no Qab” por “Pafa a —i Qab”.

Al decir “de función parecida” en éste y en los otros párrafos, no hav que suponer ninguna concesión a la vaguedad. Puesto que los conectores sirven especialmente para determinar los valores de verdad de las sentencias compuestas, no nos interesan de ellos las connotaciones de otro orden que pudieran tener. Aunque “pero”, por ejemplo, se usa cuando hay una cierta oposición entre las dos sentencias que une, su contribución al valor de verdad de la sentencia compuesta resultante es la misma que la de “y” . Así: “Juan no viene hoy pero vendrá mañana” es verdadera en el caso y solamente en el caso en que lo sea “Juan no viene hoy y vendrá mañana”. La diferencia entre ambas sentencias es retórica,- no lógica.

18 INTRODUCCION

Consideraciones semejantes pueden hacerse para las restantes partículas. La partícula “o” se utiliza al menos en dos sentidos, uno exclusivo (que

excluye la verdad simultánea de las dos sentencias que conecta), como en “a estas horas ya le habrán aprobado o le habrán suspendido”, y otro no exclusivo (que no excluye la verdad simultánea de las dos sentencias que conecta), como “aprobarán los alumnos que hayan escrito un buen trabajo en casa o hayan hecho un buen examen”, “se requiere saber francés o inglés”, “todos sus amigos son aficionados al cine o a la música”, etc. Representaremos la partícula “o”, en su uso no exclusivo, mediante el signo “v ”. Así en vez de “Qab o no Qab”, escribiremos “Qab v —> Qab”.

Para representar la expresión “si ..., entonces . . . ” u otras parecidas utilizaremos el signo Si A y B son dos sentencias, en vez de cualquiera de estas sentencias:

si A, entonces B si A, Bsuponiendo que A, B B, si AB, a condición de que A A es una condición suficiente de B B es una condición necesaria de A

escribiremos: “A —» B ”. Lo que queremos decir es que, siempre que A sea cierto, también lo será B.

Para representar la expresión " ... si y sólo si . . . ” u otras parecidas utilizaremos el signo Si A y B son dos sentencias, en vez de

A si y sólo si BA es una condición necesaria y suficiente de B si A, B, y si B, A,

escribiremos: “A < ^ B ”. Lo que queremos decir es que A y B tienen el mismo valor de verdad, que las dos son ciertas o las dos son falsas.

A estos signos:

“ l, A, V,

y a las expresiones lingüísticas por ellos representadas, les llamaremos conectares, porque sirven para conectar unas sentencias con otras (excepto ““ ó ), formando sentencias más complicadas a partir de otras más simples.

Lo fundamental de los conectares es que determinan unívocamente el valor de verdad de la sentencia compuesta, por ellos conectada, en función de los valores de verdad de las sentencias componentes. Esto no ocurre

VARIABLES. TERMINOS Y FORMULAS 19

siempre así con las expresiones del lenguaje ordinario. Pero nosotros sólo usaremos los nuevos signos aquí introducidos cuando esto ocúrra.

“ i A será verdadero, si A es falso. En los demás casos, falso.A a B será verdadero, si tanto A como B son verdaderos. En

los demás casos, falso.A v B será falso, si tanto A como B son falsos. En los demás

casos, verdadero.A —» B será falso, si A es verdadero y B falso. En los demás

casos, verdadero.A * > B será verdadero, tanto si A y B son los dos verdaderos,

como si A y B son los dos falsos. En los demás casos, falso.

6. Variables

Los matemáticos utilizan con frecuencia variables, sobre todo cuando quieren decir algo bastante general, como que la ecuación

x + y = y + x

siempre resulta satisfecha, cualesquiera que sean los números reales que pongamos en vez de las variables.

En el lenguaje ordinario, los pronombres juegan con frecuencia el papel de variables. “Él ha sido el asesino”. ¿Él? ¿Quién? Es como decir: “x ha sido el asesino”. “Lo he visto con mis propios ojos”. ¿Lo? ¿Qué? Es como decir: “He visto x con mis propios ojos”.

En realidad, a la hora de analizar textos del lenguaje ordinario y simbolizarlos adecuadamente, nos daremos cuenta de que las variables constituyen un valioso recurso de simbolización. Como variables utilizaremos las últimas letras minúsculas del alfabeto latino: u, v, w, x, y, z. Si es necesario usaremos subíndices de diferenciación: x0, xu x2, X?.. ... 7

7. Términos y fórmulas

Si en una sentencia sustituimos un designador por una variable (o varios desígnadores por otras tantas variables), el resultado es lo que llamamos una fórmula abierta.

Así, sustituyendo el designador “Juan” por la variable “x” en la sentencia “Juan ama a su prima”, obtenemos la fórmula abierta “x ama a su prima”. Del mismo modo, sustituyendo el designador “la madre de Luis” por “y” en la sentencia “la madre de Luis se pasa el día cosiendo”, obtenemos la fórmula abierta “y se pasa el día cosiendo”. Sustituyendo el

20 INTRODUCCIÓN

designador “5 ” por “x” y el designador “7” por “y” éii la sentencia “5 7 > 10”, obtenemos la fórmula abierta “x-j- y ~ > 1 0 ”.

Obsérvese que, mientras las sentencias son verdaderas o falsas, las fórmulas abiertas no son ni lo uno ni lo otro. “5 7 >• 10” es cierto, pero“x -f- y > 10” no es ni cierto ni falso.

Si en un designador sustituimos un designador por una variable (o varios designadores por varias variables), el resultado es lo que llamamos un término abierto.

Así, sustituyendo el designador “Luis” por la variable “x” en el designador “la madre de Luis”, obtenemos el ténnino abierto “la madre de x”. De igual modo, sustituyendo “el último rey de Francia” por “z” en el designador “la cabeza del último rey de Francia”, obtenemos el término abierto “la cabeza de z”. Y sustituyendo el designador “8 ” por “x” y el designador “9” por “y” en “(8 -f- 9)2”, obtenemos el término abierto “(x -f- y)2”.

Obsérvese aquí también que, mientras los designadores designan o se refieren a un individuo u objeto determinado, los términos abiertos no se refieren a individuo u objeto alguno. Así, por ejemplo, “(8 -f- 9)2” designa al número 289, pero “(x - f - y)2” no designa número alguno.

De ahora en adelante, llamaremos fórmulas tanto a las fórmulas abiertas como a las sentencias. Y llamaremos términos tanto a los términos abiertos como a los designadores.

Según la terminología que hemos adoptado, “El padre de Enrique es amigo del alcalde de Reus” es una fórmula y, en especial, una sentencia. “x es amigo de y” es una fórmula y, en especial, una fórmula abierta. “Madrid es la capital de España” es una fórmula y, en especial, una sentencia (en este caso, verdadera). “5 -j- x = 10” es una fórmula y, en especial, una fórmula abierta (ni verdadera ni falsa). “La capital de Francia” es un término y, en especial, un designador (que designa París). “El padre de Felipe II de España” es un término y, en especial, un designador (que designa a Carlos I de España). “5 -j- 6 ” es un término y, en especial, un designador (que designa al número 11). “La capital de x”, “el padre de z” y “5 -f- y” son términos y, en especial, son términos abiertos, que no designan objeto alguno.

El siguiente cuadro resume lo dicho:

abiertotérmino <

[ designador (designa un objeto o individuo)

fórmula

CUANTIFICADORES 2 1

8. Cuantificadores

A veces nos encontramos con expresiones lingüísticas que nos sirven para decir algo de todos los objetos de una clase determinada. Por ejemplo, la expresión “todos los” en “todos los chinos aman a Mao”, o la expresión “cada” en “cada uno tiene sus gustos”, o la expresión “el” en “el hombre es un mamífero”. Otras expresiones nos sirven para decir algo de algunos objetos de una clase determinada, para afirmar que en esa clase hay al menos un objeto que cumple lo que se dice. Por ejemplo, la expresión “unos” en “unos tipos sospechosos me seguían”, o la expresión “algunos” en “algunos chinos aman a Liu Chao-chi”, o la expresión “hay” en “hay personas que pesan más de 120 kg”. A todas estas expresiones las llamaremos cuantificadores. A las primeras (“todo”, “cada”, “el” ...), cuantificadores universales, alas segundas (“algún”, “unos”, “hay”, ...), cuantificadores particulares.

Al cuantificador universal lo representaremos por “A ”, al particular por “V ”. Después del cuantificador escribiremos siempre una variable, a la que llamaremos variable cuantificada:

Ax, Ay, Vz, \/w ...

A partir de fórmulas abiertas podemos construir fórmulas cuantificadas, anteponiendo cuantificadores, seguidos cada uno de una variable. Si digo “todos mis amigos son gentes de fiar” quiero decir que, de cualquier x, se puede afirmar la fórmula abierta:

si x es amigo mío, entonces x es de fiares decir,

x es amigo rnío —> x es de fiar.

Para simbolizar enteramente la sentencia “todos mis amigos son gente de fiar”, he de añadir el cuantificador universal:

Ax (x es amigo mío —» x es de fiar).

O, simbolizando los relatores “... es amigo mío” y “... es de fiar” por “P” v “Q”, respectivamente:

Ax (Px -» Qx).

Obsérvese que, desde el punto de vista gráfico, el cuantificador universal, A, es como un conyuntor más grande, mientras que el cuantificador particular, V, parece un disyuntor de gran tamaño. También a nivel intuitivo existe una semejanza funcional entre estos dos pares ds signos. En efecto, si tomamos una clase finita como ámbito de referencia, entonces la cuantificación universal equivale a una conyunción repetida, mientras que la cuantificación particular es como una disyunción iterada.

0 9 INTRODUCCIÓN

Así, por ejemplo, si en un club sólo hay tres socios: Juan, Pedro y Enrique, decir “todos los socios spn honrados” equivale a decir “Juan es honrado y Pedro es honrado y Enrique es honrado”; y decir “algún socio es un ladrón” equivale a decir “Juan es un ladrón o Pedro es un ladrón o Enrique es un ladrón”. Simbolizando “Juan” por a, “Pedro” por b y “Enrique” por c, el relator " ... es honrado” por H y “ ...e s un ladrón” por L, y conviniendo que nuestras variables se refieren a socios del club, tenemos que

Ax Hx equivale a Ha a H '> a He Vx Lx equivale a La v Lb v Le

Claro está que esto sólo ocurre, como ya hemos indicado, en el caso de que hablemos de una clase finita, como la de los miembros de un club. En el caso de clases infinitas, como la de los números naturales, la cuantifica- ción es insustituible. Si queremos decir que todos los números naturales poseen una determinada propiedad P, podemos escribir:

A xPx

Pero si quisiéramos escribirlo como conyunción repetida

P1 a P2 a P3 a P4 a P5 a P6 a P7 a . . .

no podríamos, pues no acabaríamos nunca de escribir esa conyunción.

9. Descripciones

A veces nos referimos a un individuo indicando una característica que sólo él posee, caracterizándolo, describiéndolo unívocamente. La expresión lingüística que empleamos para ello es un designador, pues designa un individuo. Pero es un designador un tanto peculiar.

Consideremos la fórmula abierta

x mató a Robert Kennedy

Supongamos que Robert Kennedy fue asesinado por una sola persona. En ese caso, la fórmula abierta que acabamos de escribir caracteriza o describe unívocamente a un individuo: al asesino de Robert Kennedy, al que mató a Robert Kennedy, al x tal que x mató a Robert Kennedy.

Para simbolizar las caracterizaciones o descripciones unívocas de un individuo, introducimos el signo “i” (la iota griega), al que llamaremos el descriptor. El descriptor, como los cuantificadores, siempre va seguido de una variable.

El designador “el que mató a Robert Kennedy” será simbolizado así:

tx x mató a Robert Kennedy

DESCRIPCIONES 23

o, más completamente, simbolizando el relator “...m ató a .. .” por M, y el nombre “Robert Kennedy”por k:

ix Mxk

Si simbolizamos el relator monódico " .. . es habitante de Barcelona” por H y el relator diádico “... es más anciano que . . .” por M, podemos simbolizar el designador “el más anciano habitante de Barcelona” por:

ix (Hx a ~iV i/ (Hy a Myx))

que, en lectura detallada, dice:

el x tal que: x es habitante de Barcelona y no hay ningún habitante de Barcelona que sea más anciano que él.

Hagamos que nuestras variables se refieran a números naturales, simbolicemos el relator diádico " ... es divisor de . . .” por “ ” y el predicado diádico " ... es menor o igual que . . .” por “<T\ Podemos simbolizar el designador “el máximo común divisor de n y m” por:

ix (x|n a x|nt a A y (¡/¡n a y m — < * ) )

que en lectura detallada, dice:

el x tal que: x es divisor de n y de m, y cualquier otro número que es divisor de n y de m es menor o igual que él.

“El menor número natural” se simbolizaría:

tx Ay x < ¡y

“El mayor número natural” sería

ix A y y <1 x

Ahora bien, mientras todos sabemos que el 0 es el menor número natural, el mayor no existe. La expresión “el mayor número natural” no describe unívocamente objeto alguno, no caracteriza a objeto alguno, aunque por su forma sea una caracterización. En el mismo caso están expresiones tales

como “el actual rey de Francia”, “el hijo menor de Fulano” (donde Fulano no tiene hijos), etc.

Ante estas caracterizaciones engañosas o descripciones impropias cabe tomar dos caminos por lo menos. Uno consiste en excluirlas del lenguaje, no admitirlas como términos (es el camino de Hilbert). Otro consiste en atribuirles una designación arbitraria, la misma para todas ellas. Cada descripción propia designaría su objeto unívocamente descrito, mientras que todas las descripciones impropias designarían un mismo objeto, arbitrariamente elegido por el hablante. Este camino resulta un tanto sofisticado

24 INTRODUCCIÓN

v artificioso, pero tiene muy ciaras ventajas técnicas a la hora de formalizar, Es el camino seguido por Frege y Camap y el que seguiremos nosotros aquí.

10. Paréntesis

Las mismas palabras, colocadas en el mismo orden, pueden dar lugar a sentencias distintas, según las pausas que hagamos al pronunciarlas o los signos de puntuación que empleemos al escribirlas. Si, refiriéndonos a nuestro amigo John, decimos: “John habla en francés, o John habla en inglés y Pedro no le entiende”, damos a entender que Pedro no entiende el inglés, pero posiblemente sí el francés. Al decir: “John habla en francés o John habla en inglés, y Pedro no le entiende”, queremos más bien indicar que Pedro no entiende ni el francés ni el inglés, que son los idiomas que habla nuestro amigo, por lo que en cualquier caso no le entiende.

Tratemos de formalizar estas dos sentencias, usando “H ” para “... habla francés”, “N ” para " ... habla inglés”, “E ” para “... entiende a . . .”, “a” para nuestro amigo “John” y “b ” para “Pedro”.

Las dos sentencias arriba citadas podrían formalizarse de momento así:

Ha v Na a ~i Eba

Ahora bien, una de esas sentencias podría ser falsa y la otra verdadera. No pueden ser formalizadas de la misma manera. Al pronunciarlas, marcábamos la diferencia mediante las pausas; al escribirlas, mediante las comas; al formalizarlas, marcaremos la diferencia mediante la distinta colocación de los paréntesis.

Ha v (Na a —i Eba)(Ha v Na) a ~ i Eba

serán la correcta formalización de la primera y la segunda sentencia, respectivamente.

Los paréntesis son al lenguaje formalizado lo que las pausas al lenguaje hablado y los signos de puntuación al lenguaje escrito normal.

Los paréntesis se emplean mucho en la matemática. No es lo mismo

8 - ( - 7 - 5 que (8 -|~ 7) ■ 5

8 - ( - 7 - 5 es 43, mientras que (8 -(-7)-5 es 75.Tampoco es lo mismo 5 -|- 7"x -|- y que (5 -(- 7)2(x -|~ y).

También en el lenguaje formal de la lógica los paréntesis están a la orden del día. Los paréntesis nos sirven para indicar hasta dónde llega el efecto de un cuantificador o de un descriptor. Supongamos que núes-

FOBMALIZ ACION 25

tras variables se refieren a personas, “S” representa a " ... es sueco” y “E ” aes europeo”.

“Si todos los hombres son suecos, x será un europeo” es una fórmula abierta y se formaliza así:

AxSx —> Ex

“Todos los suecos son europeos” es una sentencia y se formaliza asi:

Ax(Sx —» Ex)

La diferencia se indica, pues, únicamente por la colocación de los paréntesis.

Si nuestras variables se refieren a números naturales (0, 1, 2, 3, ..., etc.) y M representa a " ... es menor que . . .”, formalizaremos la descripción “el número natural menor que el 1” (que designa al 0) por

ixMxl.

Para formalizar la descripción “el número natural menor que el 2 y mayor que el 0” (que designa al 1) hemos de hacer uso de los paréntesis:

ix (Mx2 a MOx).

Si no lo hiciésemos, esto es, si escribiésemos llanamente:

tx Mx2 a MOx,

no sólo no conseguiríamos decir lo mismo, sino que, por añadidura, no diríamos nada. En efecto: la fila de signos anterior a “a ” es un término, mientras que la posterior es una fórmula, y sucede que los conectores han sido introducidos para unir precisamente dos fórmulas. (Por otra parte ‘\xMx2” no designa objeto alguno: no hay solamente un número natural menor que 2.)

11. Formalización

Formalizar las expresiones del lenguaje ordinario significa simbolizarlas de acuerdo con las normas hasta ahora expuestas. Para formalizar unas expresiones hay que empezar por analizarlas, es decir, por ver si son sentencias, designadores, etc., y cuáles son sus componentes. A continuación hay que indagar cuáles son los nombres, functores y relatores distintos que en ellas aparecen, asignando una letra distinta correspondiente a cada uno de ellos. Finalmente, y por medio de ios siglos lógicos (conectores, cuantificadores y descriptor), las variables y los paréntesis, hay que traducir simbólicamente la estructura de las expresiones de que partimos.

26 INTRODUCCIÓN

Pongamos varios ejemplos numéricos. Supongamos que nuestras variables se refieren a números naturales y simbolicemos los relatores monádi- cos " ... es par” y es impar” por “P” y “Q” respectivamente, el relator diádico " ... es menor que . . .” por “< ” y el functor monádico “el siguiente de . . . ” por

“Hay por lo menos un número par menor que tres” lo simbolizaremos por

\/x(Px A X < 3)

“Hay a lo sumo un número par menor que tres” por

A xy(Px APy A X < 3 A t j < 3 - > x = y)

“Hay exactamente un número par menor que tres”, que equivale a las dos sentencias anteriores, juntas, puede simbolizarse uniendo sus simbolizaciones respectivas:

\/x(Px a x < 3) a A xy(Px a P(/a x < 3 a ( / < 3 - > i = y)

o, más brevemente,

\/x(Px a x < 3 a Ay(Py a y < 3 -> x = y))

“El número siguiente de cualquier número par es impar” se convertirá en

Ax(Px -> Qfx)

“El número siguiente de cuatro es cinco” será

f4 = . 5

La silogística aristotélica, que es la teoría lógica más antigua, sólo se ocupa de sentencias de 4 tipos muy determinados: del tipo a: “todos los A son B”; del tipo i: “algún A es B ”; del tipo e: “ningún A es B” y del tipo o: “algún A no es B”, donde A y B son relatores monádicos. Nosotros simbolizaríamos estas sentencias así:

tipo a: Ax(Ax-+Bx) tipo i: Vx(Ax a Bx) tipo e : Ax(Ax -> Bx) tipo o: Vx(Ax a Bx)

Así, por ejemplo, si nuestras variables se refieren a hombres, y las letras G, E y M representan los relatores monádicos “... es griego”, " ... es europeo” y " ... es mortal”, respectivamente, podemos simbolizar

“todos los griegos son mortales” como

Ax(Gx -» Mx)

FORMALISMOS. LENGUAJE Y METALENGUAJE 27

“ningún griego es mortal” como

Ax(Gx —i Mi)

“algunos europeos son griegos” como

\/x(Ex a Gx)y

“algunos europeos no son griegos” como

\/x(Ex a - i Gx).

12. Formalismos

Podemos llegar a determinadas fórmulas o términos simbólicos como resultado de un proceso de formalización de textos del lenguaje ordinario, movidos, por ejemplo, por el deseo de aclarar o controlar una determinada argumentación.

Pero también podemos interesarnos por las posibilidades que hay de construir términos y fórmulas a partir de determinados signos, con independencia del lenguaje ordinario. Podemos definir propiedades de fórmulas y relaciones entre fórmulas. Podemos, en una palabra, interesarnos por los formalismos.

Un formalismo no es sino eso: un conjunto de signos y de determinadas combinaciones de esos signos. Aquí vamos a considerar un tipo peculiar de formalismos: los de primer orden.

Todos los formalismos de primer orden tienen ciertos signos comunes: los conectores, los cuantificadores, el descriptor, el relator diádico de igualdad, “= ”, y las variables. Pero unos formalismos se diferencian de otros en los distintos nombres, functores y relatores que poseen.

Un formalismo es, en principio, un mero juego de signos y de combinaciones de signos, desprovisto de toda significación. Sin embargo, podemos interpretar un formalismo, cuando así nos interesa, atribuyendo significados a sus signos. Un formalismo así interpretado se convierte en un lenguaje formal. Claro que un mismo formalismo es susceptible de ser interpretado de muy diversas maneras, dando lugar a diferentes lenguajes formales.

En la sintaxis estudiaremos los formalismos con independencia de toda interpretación. El estudio de las interpretaciones será objeto de la semántica.

13. Lenguaje y metalenguaje

Cuando un grupo de españoles vamos a clase de latín, el profesor nos habla en español acerca del latín. Utiliza la lengua española para hablarnos de la lengua latina. En ese sentido decimos que el español está siendo

2 8 INTRODUCCIÓN

usado como metalenguaje para el estudio adecuado del latín, que es el lenguaje-objeto.

Los formalismos son susceptibles de ser interpretados y, por tanto, de convertirse en lenguajes: lenguajes formales. Pero su estudio ha de realizarse desde otro lenguaje que, respecto a ellos, es un metalenguaje. En este libro estudiaremos los formalismos —o lenguaje-objeto— utilizando como metalenguaje el castellano, o, mejor dicho, el castellano enriquecido con determinadas expresiones matemáticas y determinados signos ad hoc que iremos introduciendo.

Hasta aquí hemos introducido una serie de conceptos de un modo intuitivo e insatisfactorio. Con ello espero haber conseguido lo que pretendía: que una serie de palabrotas técnicas empiecen a “sonarle” al lector. Tan pronto como pase al primer capítulo, es de esperar que el lector olvide lo leído en la introducción y se quede con las definiciones más precisas que de aquí en adelante encontrará.

PARTE PRIMERA

SINTAXIS:GRAMATICA DE LOS FORMALISMOS

1.1. Signos comunes a todos los formalismos

El alfabeto de cada formalismo está constituido por dos clases de signos: los signos comunes a todos los formalismos y los signos peculiares de él.

Los signos comunes a todos los formalismos son las variables, los signos lógicos y el igualador.

Las variables constituyen un conjunto infinito recursivamente numerable de signos distintos. Es decir, hay tantas variables como números naturales. A cada variable corresponde un número natural distinto, al que llamamos su índice. Así podemos hablar de la primera variable (o variable de índice 1), de la segunda variable (o variable de índice 2), ... de la n-ésima variable (o variable de índice n), etc. Inversamente, a cada número natural corresponde una variable: la que tiene ese número como índice. Variables distintas tienen índices distintos y una sola variable tiene un solo índice.

Las variables pueden tener cualquier forma gráfica compatible con las anteriores exigencias. Por ejemplo, podrían tener la forma de cruces seguidas de palotes (el número de palotes indicaría el índice) o de círculos con un número en su interior (donde el número en el interior de cada círculo indicaría el índice), etc.

La forma concreta que tengan las variables nos resulta indiferente, pues nosotros no las usaremos, sino únicamente las mencionaremos. Para referirnos indistintamente a variables, introducimos como metavariables las

primera variable ¢( segunda ” ¢(tercera *cuarta *

©©

3 . — - L O G I C A DE P R I M E R O R D E N

32 SINTAXIS: GRAMÁTICA DE LOS FORMALISMOS

últimas letras minúsculas del abecedario latino (provistas, cuando sea necesario, de subíndices de diferenciación): u, v, w, x, y, z, un, uu ti2, th„

ü2, V3,Los signos lógicos son 8: 5 conectares, 2 cuantificadores y 1 descriptor.

Constituyen, pues, un conjunto finito, disjunto con el de las variables. Es decir, no hay signos comunes, cada signo lógico es distinto de los demás y de cada una de las variables.

Como estos signos son pocos, podemos darles nombres. A cada uno de los 5 conectares le llamaremos respectivamente: negador, conyuntor, disyuntor, condicionador y bicondicionador. A los cuantificadores les llamaremos universal o generalizador y existencial o particularizador, respectivamente. Al descriptor le seguiremos llamando así.

Los signos lógicos pueden tener cualquier forma gráfica compatible con las anteriores exigencias. Por ejemplo, el negador podría tener la forma de una pirámide roja o de una locomotora o de una golondrina.

La forma concreta que tengan los signos lógicos nos resulta indiferente, pues nosotros no los usaremos, sino únicamente los mencionaremos. Así nos ahorramos el tener que estar escribiendo constantemente los signos entre comillas. Para referimos distintamente a los signos lógicos, introducimos como metanombres los siguientes signos:

“ 1 como nombre para el negador \A como nombre para el conyuntor jV como nombre para el disyuntor , conectores—> como nombre para el condicionador \

como nombre para el bicondicionadorA como nombre para el generalizador \ piiQriHíípílílnrpQV como nombre para el particularizador j LLtuiilJilLuvtUl vo

t como nombre para el descriptor

El igualador, finalmente, puede tener cualquier forma gráfica, con tal de que sea diferente de la de los demás signos.

Tampoco usaremos el igualador, sino que únicamente lo mencionaremos. Para rei 'rirno.s distintamente al igualador introducimos como metanombre el signo

El igualador es lo que llamaremos en 2. un relator diádico. Pero lo introducimos aquí, porque es el único relator común a todos los formalismos aquí considerados.

1.2. Signos peculiares de un formalismo

Los alfabetos de cada formalismo se parecen en sus signos comunes, que acabamos de ver, y que son los mismos para todos ellos. Y se diferencian por sus signos peculiares, distintos en cada uno.

SIGNOS PECULIARES DE UN FORMALISMO 33

Los signos peculiares son las constantes individuales, los funetores y los relatores. El número de ellos es variable, según los formalismos. Puede haber desde ninguno hasta una cantidad infinita numerable.

fin formalismo determinado puede no tener ninguna constante individual, o tener una, o dos, o tres, ..., etc., hasta un número infinito numerable de ellas.

Para cada número natural n (n > 1), un formalismo determinado puede no tener ningún functor n-ádieo, o tener un funetor n-ádico, o tener dos,0 tres, ..., etc., hasta un número infinito numerable de ellos.

Igualmente, para cada número natural n (n > 1), un formalismo determinado puede no tener ningún relator n-ádico, o tener uno, dos, tres, etc., relatores n-ádicos y hasta llegar a tener un número infinito numerable de ellos. (De todos modos, para n = 2, es seguro que cada formalismo tiene al menos un relator diádico: el igualador).

Si un formalismo determinado tiene constantes individuales, éstas han de poseer un índice o estar numeradas. Ha de poder hablarse de la primera constante individual, de la segunda, etc. Y lo mismo puede decirse de los funetores o relatores n-ádicos, caso de que los haya. También entonces ha de poder hablarse del primero, segundo, tercero, etc., funetor o relator n-ádico. Pero mientras que las constantes individuales de un formalismo vienen caracterizadas sólo por un número: su índice, los funetores y relatores vienen caracterizados por dos: su número ádico y su índice.

Todos estos conjuntos de signos peculiares (de constantes individuales, de funetores n-ádicos, y de relatores n-ádicos para cada número n) han de ser disjuntos entre sí y con el conjunto de los signos lógicos y las variables. Es decir, todos los signos han de ser distintos entre sí.

Los signos peculiares de un formalismo pueden tener cualquier forma gráfica compatible con las anteriores exigencias. Sin embargo, tampoco aquí necesitamos preocuparnos por ella.

La forma concreta que tengan los signos peculiares nos resulta indiferente, pues no vamos a usarlos, sino únicamente a mencionarlos. Para re-1 crirnos indistintamente a constantes individuales de un formalismo, introducimos como metavariables las primeras letras minúsculas del alfabeto latino (provistas, cuando sea necesario, de subíndices de diferenciación): a, b, c, ..., a0, au a-2, ..., b0, bu b2, ..., c„, cu c2, ...

Para referirnos indistintamente a funetores n-ádicos de un formalismo, introducimos como metavariables las letras f y h cubiertas de un sobreíndice n (y provistas, cuando sea necesario, de un subíndice de diferenciación): /", hn, f" f ’y ..., /i“, hnv /i;;, ...

Para referirnos indistintamente a relatores n-ádicos de un formalismo, introducimos como metavariables las letras mayúsculas P, Q, R, S, cubiertas de un sobreíndice n (y provistas, cuando sea necesario, de un subíndice de diferenciación): Pn,Q n ñ«, S”, ..., P“, P", P” ..., Qj. ()«, ()«, ... (Recuérdese


que para referirnos distintamente al especial relator diádico que es el igualador usamos el signo

Cuando el número ádico de un functor o relator esté claro por el contexto, dejaremos de lado el sobreíndice n.

Al conjunto de los signos comunes a todos los formalismos más los peculiares de un formalismo determinado le llamamos el alfabeto de ese formalismo.

1.3. Filas de signos

3.1. Cada formalismo tiene su alfabeto. Al resultado de escribir signos de ese alfabeto unos a continuación de otros (y con tantas repeticiones como se quiera) le llamamos una fila de signos de ese formalismo.

Así, pues, una fila de signos es una sucesión finita y no vacía de signos, con posibles repeticiones.

3.2. También podemos definir las filas de signos desde un punto de vista combinatorio. Dado un formalismo ü?, para cada número natural n podemos llamar Z™ al conjunto de las variaciones con repetición de n elementos del alfabeto de ü?. Entonces podemos definir al conjunto de las filas de signos de Jz?, Z.z, del siguiente modo:

= u z”n ~ 1

3.3. Para referirnos indistintamente a filas de signos de un formalismo introducimos la metavariable “£” (provista de subíndices de diferenciación, cuando sea necesario): £, £0, £i, £2, ...

3.4. La longitud de una fila de signos es el número de signos de que consta. Abreviando “la longitud de la fila de signos £” por “long (£)” y haciendo uso de la terminología de 3.2 podemos también establecer:

long (£) = n si y sólo si £ e Z ,

3.5. La yuxtaposición o concatenación de dos filas de signos £1 y £2 es la fila de signos que resulta de escribir la segunda inmediatamente a continuación de la primera: £1 £2. Siempre ocurre:

long (£x £2) = long (£: ) -f- long (£2).

3.6. Decimos que las filas de signos £1 y £2 son idénticas cuando son la misma fila de signos, es decir, cuando £1 y £2 tienen igual longitud y en cada lugar correspondiente aparece el mismo signo. Introducimos en el metalenguaje el signo “= ” para indicar la identidad de filas de signos. Mediante “ £1 = £2” indicaremos que las filas de signos £1 y £2 son idénticas.

TÉRMINOS Y FÓRMULAS 35

1.4. Términos y fórmulas

4.1. De entre las filas de signos de un formalismo hay algunas que merecen nuestra especial atención. Se trata de las expresiones del formalismo, es decir, los términos y las fórmulas.

He aquí una definición constructiva simultánea de los términos y las fórmulas de un formalismo cualquiera 88.

1. ° Cualquier variable es un término de 88.2. ° Cualquier constante individual de Jz? es un término de 88.3. ° Si ¡b, ..., í» son términos de 88 y fn es un functor de Jz?, entonces

fn ¡¡!, ..., Zn es un término de 58.4. " Si ¡h, ...y'C.n son términos de 88 y Pn es un relator de 88, entonces

i, es una fórmula de iz?. (En especial, si £i y ¡fe son términos de 88, = ¡¡i ¡fe es una fórmula de 8 8 )

5. " Si £ es una fórmula de 88, entonces —i ’í, es una fórmula de 88.6. ° Si ¡fe y ¡fe son fórmulas de ü?, entonces a ¡fe ¡fe, v ¡fe ¡fe, -> £i £2 y

¡fe ¡fe son fórmulas de 88.7. ° Si C es una fórmula de 88, entonces (para cualquier variable x) Ax £

y V i í son fórmulas de 88.8. ° Si £ es una fórmula de 88, entonces (para cualquier variable x)

tx £ es un término de 88.

Términos y fórmulas de 88 son todas y solas las filas de signos de 88 que como tales quedan caracterizadas por estas 8 reglas.

Las expresiones de 88 son las filas de signos que son términos de 88 o fórmulas de 88.

4.2. Para referimos indistintamente a expresiones de un formalismo introducimos como metavariable la letra griega “8 ” (provista, cuando sea preciso, de subíndices de diferenciación): -8, 8 0, -Si, -S2, ...

Para referirnos indistintamente a términos de un formalismo introducimos como metavariable la letra latina “t”, (provista, cuando sea necesario, de subíndices de diferenciación): t, fe, fe, f2, ...

Para referimos indistintamente a fórmulas de un formalismo introducimos como metavariables las letras minúsculas griegas “a”, “/3”, “y”, “8”,

(provistas, cuando sea preciso, de subíndices de diferenciación): a, /3, T, 3, <f, “o, «1, «2, «3, •••, /3o, /3i, /32, ...

Para referirnos indistintamente a conjuntos de fórmulas introducimos como metavariables las letras mayúsculas griegas ‘T ” y “A” (provistas, cuando sea necesario, de subíndices de diferenciación): F, A, Fo, Fj,r 2, ..., A0, Ai, a2, ...

36 SINTAXIS: DRAMÁTICA DE LOS FORMALISMOS

4.3. Según se desprende de la definición 4.1, todo término comienza por una variable, una constante individual, un functor o un descriptor.

Un término se llama variable, constante individual, término functorial o descripción, según que su primer signo sea una variable, una constante individual, un functor o un descriptor, respectivamente.

Las variables y las constantes individuales son términos simples (constan de un solo signo). Los términos functoriales y las descripciones son términos compuestos (constan de varios signos).

Respecto a cada término, es decidible si se trata de una variable, una constante individual, un término functorial o una descripción. Basta con ver si el primer signo del término es uña variable, una constante individual, un functor o un descriptor.

4.4. Según se desprende de la definición 4.1, toda fórmula comienza por un relator o por un signo lógico distinto del descriptor. Una fórmula se llama predicativa, negación, conyunción, disyunción, condicional, bicondicional, generalización o particularización, según que su primer signo sea un relator, el negador, el conyuntor, el disyuntor, el condicionador, el bieon- dicionador, el generalizador o el particularizado!', respectivamente.

Respecto a cada fórmula fes decidible si se trata de una fórmula predicativa, negación, conyunción, disyunción, condicional, bicondicional, generalización o particularización. Basta con ver si el primer signo de la fórmula es un relator, un negador, un conyuntor, un disyuntor, un condicionador, un bicondicionador, un generalizador o un particularizador.

El igualador es un relator diádico. Por tanto, una fórmula que empiece por el igualador será una fórmula predicativa. Una fórmula predicativa cuvo primer signo es el igualador se llama una ecuación.

4.5. ¿Cuántos términos hay en un formalismo? Siempre hav un número infinito numerable de términos.

En efecto, por lo menos hay un número infinito numerable, pues todas las variables son términos y hay un número infinito numerable de variables. A lo sumo hay un número infinito numerable de términos, pues todos los términos son filas de signos y sólo hay un número infinito numerable de filas de signos, ya que éstas son variaciones con repetición de elementos del alfabeto, éste es infinito numerable y sólo hay un número infinito numerable de variaciones con repetición de elementos de un conjunto infinito numerable. Por tanto, hay un número infinito numerable de términos.

¿Cuántas fórmulas hay en un formalismo? Siempre hay un número infinito numerable de fórmulas.

Esto se puede probar con consideraciones parecidas a las del caso anterior.

INDUCCIÓN SEMIÓTICA 37

1.5. Inducción semiótica

5.1. El conjunto de los números naturales es infinito numerable. Si quisiéramos probar algo para todos los números naturales (por ejemplo, que todos ellos tienen una propiedad ¡P), no tendría sentido que tratásemos de probarlo para cada número por separado, uno después de' otro, pues no acabaríamos nunca. ¿Qué haríamos? Procederíamos inductiva o recursivamente, presentando una prueba por inducción o recursión, es decir, probando lo que queríamos probar para 0 y, suponiendo que ya lo hubiésemos probado para un número cualquiera n, probándolo para n 1. Este tipo de pruebas se basan en el principio de la inducción aritmética:

. i (1) 0 tiene la propiedad ¡P j :>1 ( (2) si n tiene ¿P, entonces n -f- 1 también tiene ¿P \ entonces: todo número natural n tiene la propiedad ¡P

El mismo problema se nos plantea con las expresiones de un formalismo. También ellas constituyen un conjunto infinito numerable. También aquí nos resultaría imposible probar algo para todas las expresiones de un formalismo (por ejemplo, que todos los términos tienen la propiedad ¿P, y todas las fórmulas tienen la propiedad £P2) procediendo a probarlo por separado de cada una de ellas. ¿Qué podemos hacer? Lo mismo que en la aritmética: proceder por inducción, probarlo por una prueba inductiva o recursivá. Y así como las pruebas aritméticas por inducción se basaban en el principio de inducción aritmética, así también las pruebas por inducción de las que hablamos se basan en un principio o teorema de inducción semiótica.

5.2. En lo que sigue entiéndase “constante individual”, “término”, “fórmula”, “P”, etc., como “constante individual del formalismo ¿z?”, “término del formalismo “fórmula del formalismo JS?”, “functor f dei formalismo Ü?”, “relator P del formalismo *£’\ etc.

5.3. Teorema de la inducción semiótica:

si

/

entonces

(1) toda variable x tiene la propiedad ¿Px(2) toda constante individual tiene la propiedad £P\(3) si tu ..., f„ tienen ¿P¡, también jnti, ..., í,. tiene £Pi(4) si ti, ..., t„ tienen ¿Ply entonces P” tu ..., í„ tiene ¡P2(5) si a tiene £P->, también —i a tiene tP-i(6) si a y p tienen tam bién a <x ¡ i , v a /3, —»■ a ¡3,

a /3 tienen Sfi-¿(7) si x tiene y a tiene Ax a, V x <x tienen(8) si a tiene £P2, ix a tiene tPi(a) todo término tiene(b ) toda fórmula tiene

5.4. Demostración del teorema de la inducción semiótica. En esta demostración damos por sentada la validez del principio de inducción aritmética, que aquí utilizaremos en la siguiente versión:

Si algo vale para cualquier número natural m suponiendo que valga para todos los números menores que m, entonces eso vale para todos los números naturales.

A continuación procedemos a demostrar 5.3 por inducción aritmética sobre la longitud de las expresiones.

Toda expresión, como fila de signos que es, tiene una longitud determinada. Probaremos que para cualquier número natural m el teorema vale para toda expresión de longitud m, suponiendo que ya valga para las de longitud menor. Con ello quedará probado que el teorema vale para todas las expresiones.

9 \ y AL sean propiedades que reúnen las condiciones (1), (2), ..., (8) requeridas por el teorema.

■8 sea una expresión cualquiera de longitud m.El teorema esté ya probado para todas las expresiones de longitud menor

que m (supuesto inductivo).

Tesis: ó tiene la propiedad 9 \ (si $ es un término) o la propiedad AL (si ó es una fórmula).

La tesis puede ser demostrada examinando los casos posibles.ó = x. Entonces, ó tiene 9 \ , por (1).ó = a. Entonces, ó tiene 9 i , por (2).•$ = /” f'i,..., f„. Entonces, fi, tienen 9 i (por el supuesto inductivo,

ya que long (t¡) < long (fntu ..., tn) para l < Z i 9 n). Luego ó tiene 9 i , por (3).

■^=Pntu . . . ,f„. Entonces, tx, . . . , f2 tienen 9 \ (por el supuesto inductivo, ya que long (t¡) < long (Pntu . . . , tn) para l < t < n ) . Luego ó tiene 9->, por (4).

■S = —i a. Entonces, a tiene 9 2 (por el supuesto inductivo, ya que long (a) < long (“ i a)). Luego ó tiene AL, por (5).

•S = a a /3. Entonces, a tiene 9 2 y P tiene 9 2 (por el supuesto inductivo, ya que long (a ) < long (a a /3) y long (/3) < long (a a /3)). Luego ó tiene 9-2, por (6).

Del mismo modo se muestra que si -S = v a /3, í s - > a p, o -S = a /3, entonces ó tiene 9%.

ó = Ax a. Entonces, a tiene AL (por el supuesto inductivo, ya que kmg (a) < long (Axa)) y x tiene AL (pues long (x) < (Ax «)). Luego ó tiene 9-2, por (7).

Del mismo modo se muestra que si •&==Vxa, -8 tiene 9 2-ó — tx a. Entonces, a tiene 9 - , (por el supuesto inductivo, ya que long

(a) < long (ix a)) y x tiene A L (pues long (x) < long ( t x a)). Luego ■& tiene 9 \ , por (8).

ESTANCIA LIBRE Y LIGADA DE UNA VARIABLE 39

5.5. En la aritmética, la inducción no sólo se utiliza para probar teoremas acerca de todos los números naturales, sino también para definir propiedades, relaciones o funciones de números naturales. También aquí utilizaremos definiciones recursivas o por inducción semiótica para introducir nuevos conceptos aplicables a términos y fórmulas.

5.6. Si queremos definir un concepto para todos los términos y un concepto ^ 2 para todas las fórmulas, basta con ofrecer una definición por inducción semiótica, es decir, basta con:

1. ° Definir 9?i para cualquier variable x.2. ° Definir r-£i para cualquier constante individual a.3. ° Definir ‘g ’j para fnt 1, ..., tn, suponiendo que ya está definido para

4. ° Definir para P"ti, ..., tn, suponiendo que * '1 ya está definido parati, tn.

5. ° Definir c€ 2 para —1 a, suponiendo que Ao va está definido para a.6. ° Definir ^ 2 para a a /3, v a /3, -> a /3, <-» a /3, suponiendo que ya

está definido para a y para /3:7. ° Definir ^ 2 para Axa, Vxa, suponiendo que ^ 2 ya está definido

para a.8. ° Definir A , para tx a, suponiendo que ré'2 ya está definido para a.

1.6. Estancia libre y ligada de una variable

6.1. Los cuantificadores y el descriptor siempre van seguidos de una variable. De esta variable se dice que queda ligada por ellos. Así, si en una expresión aparece la variable x detrás de un cuantificador o de un descriptor, decimos que x está ligada en esa expresión.

Los cuantificadores y el descriptor son, pues, signos ligadores. También en el lenguaje matemático normal nos encontramos con frecuencia con signos ligadores y variables ligadas. Así, en la expresión

el signo X es un ligador que liga la variable n. En la expresión

a

el signo J ... d ... es un ligador que liga la variable x. En la expresión

y 1 m <«}el signo j... | ...j es un ligador que liga la variable 3.

Si en una expresión aparece una variable que no está ligada, decimos que está libre. También puede ocurrir que esté tanto libre como ligada en ella. A eontinuación pasamos a definir inductivamente la estancia libre o ligada de una variable en un término o una fórmula.

6.2. Definición de la estancia libre de una variable en una expresión.

x está libre en 3 syss x = za nunca

” ” f h , . . . , tn syss x está libre en algún t¡( l )—i a syss x está libre en aa a /3 syss x está libre en a o én ¡3v a d syss—> oe /3 syss<-»■ a /3 syssA z a syss x está libre en a y i ^ zVz a sysst Z a syss

6.3. Definición de la estancia ligada de una variable en una expresión.

x está ligada en 3 nunca a nunca

syss x está ligada en algún tt (1 syss x está ligada en t1 o en t2)i a syss x está ligada en a

a a /3 syss x está ligada en « o en /3a ¡3 syss

v a ¡3 svssj—> <x /3 syssA 3 a syss x está ligada en a o x = zVz a sysstz a syss

SUSTITUCIÓN DE UNA VARIABLE POR UN TERMINO 41

6.4. Observaciones sobre la estancia libre o ligada de una variable en una expresión -3:

x está en ■S si y sólo si x está libre en 3 o x está ligada en í o i está libre y ligada en 3.

x no está en 3 si y sólo si x no está libre en i y r no está ligada en ó.Para cualquier variable x y cualquier expresión 3 se presenta uno de

estos cuatro casos: (1) x no está en 3 ; (2) x está libre, pero no ligada, en ó; (3) x está ligada, pero no libre, en 3 ; (4) x está libre y ligada en 3.

Para cualquier variable x y cualquier expresión 3, es decidible en cuál de esos cuatro casos x y 3 se encuentran.

6.5. Definición de designadores y sentencias.Un designador del formalismo Jz? es un término de Jz? en el cual ninguna

variable está libre. En especial, los términos sin variables son designadores.Una sentencia del formalismo Jz? es una fórmula de Jz? en la cual nin

guna variable está libre. En especial, las fórmulas sin variables son sentencias.

Un término abierto de Jz? es un término de Jz? que no es un designador de , es decir, un término de Jz? en el cual alguna variable está libre.

Una fórmula abierta de Jz? es una fórmula de iz? que no es una sentencia de Jz?, es decir, una fórmula de Jz? en la cual alguna variable está libre.

6.6. Así, pues, obtenemos la siguiente clasificación de las filas de signos de un lenguaje formal:

no expresivafila de signos \

f expresión| término

l fórmula

j término abierto ( designador

| fórmula abierta I sentencia

1.7. Sustitución de una variable por un término

7.1. La sustitución es una operación que a cada tríada formada por una variable, un término y una expresión aplica unívocamente otra expresión, de la que decimos que es el resultado de sustituir la variable por el término en la primera expresión.

Utilizaremos el signo 5 para indicar la sustitución. En vez de 5 (x, t, 3) escribiremos 5* 3.

X

7.2. En la mayoría de los casos, 5 ' -3 se obtiene a partir de 3 por el sencillo procedimiento de borrar x en 3 y escribir en su lugar el término t. Así, por ejemplo:

5 / » —1 Ruu = ~ 1 Rfafa

S^‘Rxa ’.tjPxy = u/PixRxay

42 s i n t a x i s : g r a m á t ic a d e l o s f o r m a l is m o s

Sin embargo, hay casos en que esto no ocurre así, a fin de que la sustitución no varíe la estancia libre o ligada de las variables que ocupan determiandos lugares. Supongamos, por ejemplo, que queremos sustituir x por fy en Ay(Px v Qy). Si nos limitásemos a borrar x y escribir en su lugar fy, obtendríamos: Ay(Pfy v Qy). Pero entonces la primera variable estaría ahora ligada, mientras que antes estaba libre. Esto es algo que queremos evitar. Para ello, antes de borrar x y escribir en su lugar fy, cambiamos la variable cuantificada. En vez, de Ai¡(Px v Qy) escribimos Az(Px v Qz). Entonces borramos x y escribimos en su lugar fy, obteniendo: Az(Pfy v Qz). Ahora la primera variable sigue estando libre y la segunda ligada, exactamente como en la fórmula de que habíamos partido. Es precisamente a esta preocupación a lo que se debe la relativa complejidad de la definición de la sustitución en los casos de expresiones que empiezan por ligadores.

7.3. Definición de la aplicación 5 :

S ' z - f ‘ - S l X~ Z■" j z, si X # z

5 ‘ a = aX

i, ..., tn = fn 5 ‘ fi, ..., 5(. t„

..., t„ = P » 5 ‘ tx, ..., 5* tn

(en especial, 5* = t11., = = 5* t1 5* t.)

5* x = —i S* aX X

5 ' a y . 3 a 5(, y 5( 3

íi' v i 3 = v 5 ' y 5 ' 3x ' ./• ,r ^

5 ( —» y (3 —» 5* y 5* ¡3

5 ‘ <-> y B = <-> 5 ‘ y 5* 8X ^ X X ~

5* Az y =X

Az a

Az 5* aX

Av 5 f 5" a-V 2

si x no está libre en Az y sj í x está libre en Az a

j z no está libre en t / x está libre en Az a I z está libre en t

si / v no está en Az a ni en t (y es la va- I riable de mínimo índice que satis-l face esta condición).

CONVENCIONES NOTACIONALES 43

5 ' Vz a =X

5 ' tz a =X

Vz a , si

Vz 5* a , siX

Vv 5* 5" a , si

tz a , si

iz 5* a , siX

tu 5* 5* a , si

x no está libre en V za x está libre en V z«z no está libre en tx está libre en Vz az está libre en tv no está en Vz a ni en t (y es la va

riable de mínimo índice que satisface esta condición).

x no está libre en tz a x está libre en iz a z no está libre en t x está libre en tz a z está libre en tv no está en tz. a ni en t (y es la va

riable de mínimo índice que satisface esta condición).

7.4. Observaciones sobre la sustitución:

Para cada expresión •S1, cada variable x y cada término t hay siempre una expresión S-¿, unívocamente determinada, tal que 5*. $ 1 = ó 2

(1) : Para cualquier x y cualquier -3: 5® 3 = 3.(2) : Si x no está libre en 3, entonces 5 * $ = $.(3) : Si x está libre en 3, entonces t está en 5 ) ó, y cada variable que

esté libre en t está libre en 5 ' ó.X

(4) : Si z no está en ó, entonces 5^5^3 = 3.(5) : Si x no está libre en t, entonces x no está libre en 5 * 3 .(6) ; Z está libre en 5® ó si y sólo si x está libre en 3 o z está libre en ó.(7) : z está libre en 5 ) ó si y sólo si al menos uno de estos dos casos se

í a) z está libre en í y z # x.presen an. <j ^ x esj.¿ ]jy,re en 3 y z está libre en t.

Todas estas observaciones pueden demostrarse fácilmente por inducción semiótica.

Respecto a cualesquiera x, t, 3i, $ 2, es decidióle si #1 = £2 o no.

1.8. Convenciones notacionales

8.1. Como nosotros no usamos las fórmulas del formalismo, sino que únicamente las mencionamos mediante nombres metalingüísticos, pode

44 s i n t a x i s : g r a m á t ic a d e l o s f o r m a l is m o s

mos adaptamos en el metalenguaje a la práctica ampliamente extendida de escribir los conectores entre la fórmulas que conectan, etc., utilizando paréntesis para evitar confusiones. Esta práctica resulta más intuitiva, sobre todo cuando se trata de expresiones complicadas. Pero recuérdese que en el formalismo mismo no hay paréntesis.

Así,, pues, para acomodarnos a esta práctica corriente, escribiremos:

“ t i = íü” en vez de “= t 1 U ”

“(a a /3)” “a a /3”“ ( a v /3)” “v a ¡3”

“(a -> /3)” » a /3”“(a ±>/3)” “■o-a/3”

8.2. En expresiones algo complicadas pueden aparecer de este modo muchos paréntesis, para cuyo ahorro adoptamos las siguientes convenciones:

1. ° Los paréntesis exteriores de una fórmula pueden suprimirse en la escritura abreviada.

Ejemplos:

a a /3 es una abreviatura de (a a /3)(a a /8) v 7 ” ” ” ” ((* a /3) v y)

a (/3 -> 7) " ” ” ” (a -e» (/3 - » T))

2. " Condición ador y bicondicionador separan más que conyuntor y disvuntor. Por tanto, si el antecedente o consiguiente de un condicional es una conyunción o disyunción, pueden suprimirse los paréntesis correspondientes en la escritura abreviada. Lo mismo en el bicondicional.

Ejemplos:

aAjfl- > 7 es una abreviatura de ((a a /3) —» 7 )a -> d v 7 ” " (« ->(|8 v 7 ))a v /3 -» 7 A o ” ” ” ((a v /3) - > ( 7 a 8))- i ( 2 A ) 3 ) « - i s v -|^ ” ” ” ” ( - l ( í A ^ ) o ( n s v - i í ) )

3. " Los paréntesis intemos de una conyunción o disyunción iterada por la izquierda pueden suprimirse en la escritura abreviada.

Ejemplos:

o. a /3 a 7 a o es u n a a b r e v ia tu r a d e ( ((a a /3) a 7 ) a 0)

" i a v 8 v 7 —» o ” ” ” (((“ i a v /3) v ~ 1 7 ) —» 8)

8.3. En los lenguajes formales con functores y relatores cuya posición lia sido consagrada por el uso, adoptaremos inoficialmente esa posición, co

CONVENCIONES NOTACIONAI.ES 45

locando los paréntesis necesarios para evitar equívocos. Esto ocurre sobre todo con algunos functores y relatores diádicos. Por eso, a veces escribiremos :

8.4. A veces abreviaremos una fila de cuantificadores del misino tipo, escribiendo “Axi, ...,x „ ” en vez de “Ax1; Ax„” o “ \ /xu x , ” en vezde " V x i ,..., Vx„”.

Repitamos, finalmente, que esta relajación de nuestras convenciones notacionales se refiere únicamente a los nombres metalingüísticos de las expresiones del formalismo, y no a estas expresiones mismas.

1.9. Ejemplos de sustitución

9.1. Consideremos la fórmula A u (P x a H u —» Vx R x z) — es decir, la fórmula que de un modo oficial se escribiría Au —> a P x H u Vx R x z — . Se trata, de la generalización de un condicional, cuyo antecedente es P x a H u y cuyo consiguiente es Vx R x z . Supongamos que las variables u, x, y , z , w son todas ellas distintas entre sí. Evidentemente, la variable u está ligada en la fórmula A u (P x a H u —> Vx R x z ); la variable z está libre en dicha fórmula; la variable x está tanto libre como ligada en ella (libre la primera vez y ligada la segunda); las variables y , w , finalmente, no están en absoluto en la fórmula.

9.2. Dada la importancia del concepto de sustitución para la adecuada comprensión de los capítulos siguientes, ofrecemos aquí una serie de ejemplos en los que se indica el resultado de sustituir alguna de las variables antes citadas por un término en la fórmula considerada en el párrafo anterior. He aquí los ejemplos:

“(íi/2t2)” en vez de “( h P ‘% ) ” en vez de “ P - t , t A

5* Au(Px a Hu -* Vx Rxz) = A u (P x a H u —» Vx Rxz)5 /*M = A u (P x A Hu -> Vx Rxz)5*j; = A u (P x a Hu Vx Rxz)5 /®

X= A u (P fx a H u -> Vx R x z )

5 'e Au ( P fc a Hu —» Vx Rxz)5 í u P v

X= A u (P iy P y a H u —» Vx Rxz)

5 “X

= A y (P u a H y -> Vx R x z)

5* = A u (P x a Hu —> Vt/ Ryx)5 /* = Au (P x a Hu —> V;/ R y fx )


5 * ” — Au(Px a Hu —» Va: Rxfc)c¡tyPy

z” = Au(Px a H u —> V x Rxiy Py)

5 “ = Ay(Px a Hy —> Va fían)5®y = Au(Px a Hu Va Rxz)Efy Py

u= Au(Px a Hm —» Va ñaz)

Si 5® Au(Px a Hw —> Va; Zfaz) = Au(Px a Hm -> VxRxy)5 '° 5 ‘ = Au(Pfc a Hu —> Va f lx c )

5/.r 5 A! = Au(Px a Hu —> Vt/ ñyfa)5" 5»V r = Au(Px a Hu —> Va Rxc)5>° 5®,r z ” — Au(Pfc a Hu —> Ay Ryfc)5 /“ 5 ® ” = Aw(Pfu a Hw —> Vy Ryfu)

PARTE SEGUNDA

SINTAXIS:UN CALCULO DEDUCTIVO

4. — LÓGICA I>E PR IM ER ORDEN

II. I. Reglas primitivas de inferencia

1.0. Un cálculo (o algoritmo) deductivo es un conjunto de reglas. La aplicación de estas reglas a las fórmulas de un formalismo nos permite decir < n algunos ('asos que unas fómulas son deducibles de otras.

Kn el cálculo que aquí presentamos hay dos clases de reglas: reglas de inferencia, (pie nos permiten pasar de una o dos fórmulas a otra nueva, la fórmula inferida, y reglas de construcción, que nos permiten construir deducciones (o, como veremos, más generalmente, semideducciones).

1.1 Kn algunos casos diremos que una fórmula del formalismo í£ es inferióle en '£ de otra u otras fórmulas del mismo formalismo. Las reglas de inferencia determinan exactamente en qué casos esto ocurre.

A continuación ofrecemos una lista de las reglas de inferencia. A la izquierda aparece el nombre de la regla, en el centro, su abreviatura y, a la derecha, su formulación esquemática. En cada uno de estos esquemas .v, /, a, p, etc. representan una variable, un término, una fórmula, etc. cualquiera del formalismo del que se trate. La raya horizontal indica que la fórmula situada bajo ella es inferible de la o las fórmulas situadas encima.

1 .2 . Lista de las reglas primitivas de inferencia:

aIfegla de repetición R : ------

Ifegla del modos poneos MP:

a —» /3 a

Regla del modus tollens MT:O

7, —> ¡3->P

a

50 SINTAXIS: UN CÁLCULO DEDUCTIVO

—i —i a aReglas de la doble negación D N :----------- -----------

a “ i ~i a

a

Regla de introducción del conyuntor IC: —-----^ ( « A j S )

Reglas de eliminación del convuntor EC : —----- — —-----—" a /3

oc <xReglas de introducción del disyuntor ID: ^------- - -------- -

8 ' (a v /3) (/3 V ce)

(a v /3) (a v /3)/ —1 a —i /3

Reglas de eliminación del disyuntor ED : ----------- -----------/3 a

(/3 -» a)Regla de introducción del bicondicionador I B : ------------

(a •o- /3)

(a ■o- /3) (a •o- /3)Reglas de eliminación del bicondicionador EB: -7---------r- -------- r-

(a -> /3) (/3 -> a)

5 ' aRegla de introducción del particularizador IP: — -—

Ax aRegla de eliminación del generalizador EG: ^

Regla de introducción del igualador II: —r— --- ---------- ^ )n< c lt r*° est^& 6 Ax(x = t-><x) libre en t

o 1 j 1- • ■' j 1 • i i t-r A x (x = t —> a) donde x no estáRegla de eliminación del igualador E l : --------- ------------ , .0 a libre -en t

X

Regla de las descripciones propias DP: Ax ** x = Adonde y no está& 1 1 1 S ixa- a libre en a

X

—1 \J 1 i Ax ((x > x — ¡1) donde yRegla de las descripciones impropias DI: --------------------- - no esui

r tx « = iz z = z ’libre en a

Regla crítica de eliminación del particularizador EP: Vx aa

DEDUCCIONES 51

1.3. Reglas normales de inferencia son las reglas de inferencia distintas de EP. Regla crítica es EP.

Al inferir 5 “ cc de V ia por EP, decimos que u es la variable crítica de esta inferencia.

Obsérvese que EP sólo nos autoriza a inferir 5 “ a, donde u ha de ser una variable; a diferencia de EG, que nos autoriza a inferir 5* a de Ax a, donde / es un término cualquiera.

1.4. Ejemplos:

(A:c Px v x = y) es inferible de Ax Px por ID fcy. ..., cn := k es inferible de Ax (x = fcu ..., cn —» x = k) por El tx Gxk = ’.tv tv — w es inferible de —i Vi/ Ax (Gxk < -x — ij) por DI —i c, = Co es inferible de (cj = c2 —> Rcjx) y —i Rc¡x por MT (Ax Px <-> Pa) es inferible de (Ax Px —> Pa) y (Pa —» Ax Px) por IB a — ix Rxa es inferible de (Raa v a = tx Rxa) y ~i Raa por ED Rfc es inferible de Ay Ry por EG

11.2. Deducciones

2 .0 . Cuando alguien trata de probar algo, por ejemplo, cuando un matemático trata de probar un teorema, ¿qué hace? Procede paso a paso, utilizando las premisas de que parte o los datos ya probados. De vez en cuando se para a considerar qué es lo que en ese momento quiere probar. A veces trata de probarlo directamente, infiriendo unas sentencias de otras hasta que llega a la que buscaba. Otras veces encuentra más cómodo el ofrecer una prueba indirecta. Para ello, supone lo contrario de lo que quiere probar y trata de obtener una contradicción a partir de ese supuesto. Si lo que quiere probar es un enunciado del tipo “si A, entonces R”, es probable que inicie una prueba condicional, suponiendo que A y probando entonces B. Finalmente, si ha de probar algo para todos los elementos de una clase en general, puede limitarse a probarlo para uno cualquiera.

Esta manera de proceder se refleja en las reglas de construcción de deducciones del presente cálculo. Pero antes de presentar estas reglas, conviene introducir el concepto de línea.

2.1. Caracterización exhaustiva de las líneas de un formalismo S£ (en lo sucesivo diremos simplemente líneas, en vez de líneas de Jz?, y fórmulas, cn vez de fórmulas de ¿zf):

Una línea utilizable es la fila formada por una fórmula sola o una fórmula precedida de un interrogante tachado t : a, f a, ? /3, f y, ...

Una línea marcada es una fila formada por una línea utilizable precedida de n (n > 1) marcas |: [a, j [ ¡3, j f a, j 1 1 f /3, ...

Una línea interrogada es una fila formada por una fórmula precedida de un interrogante intachado ?: ? a, ? /3,...

Una línea es una línea utilizable o una línea marcada o una línea interrogada.

2.2. Como metavariable para referirnos indistintamente a líneas cualesquiera, introducimos la letra griega “A” (con subíndices de diferenciación, cuando sea necesario): Ai, A;;, As, ...

2.3. F sea un conjunto de sentencias del formalismo J5?. A continuación caracterizamos exhaustivamente las semideducciones en a partir de í .

Definición:

Una semideducción en -2' a partir de P es una sucesión finita de líneas obtenidas conforme a las siguientes reglas:

1. Para cualquier fórmula a. de ¡ £ , se puede escribir como línea

? «

2. Para cualquier a e P, se puede escribir como línea

a

3. Si ? a es una línea ya escrita, como línea inmediatamente siguiente se puede escribir

“ i a

4. Si ? a —»/3 es una línea ya escrita, como línea inmediatamente siguiente se puede escribir

a

5. Si a es inferible de líneas utilizables anteriores por medio de una regla de inferencia otra que EP, entonces se puede escribir como línea

<x

6 . Si a es inferible de líneas utilizables anteriores por medio de la regla de inferencia EP y la variable nueva (crítica) no está en ninguna línea anterior, entonces se puede escribir como línea

a

7. Si ? a es la última línea interrogada, entonces se pueden marcár todas las líneas siguientes y tachar el interrogante de ? <x, si uno de estos cuatrocasos ocurre:

DEDUCCIONES 53

(1) Una de las líneas utilizables siguientes es a.

(2) Una de las líneas utilizables siguientes es la negación de otra de ellas.

(3) a = (¿8 —> 7 ) >' una de las líneas utilizables siguientes es 7 .

(4) a s A í i , ...,Xnf3, ninguna de las variables xu . ..,* » está libre en las líneas utilizables anteriores a ?a, y una de las líneas utilizables siguientes es ¡3.

Las fórmulas de F que de acuerdo con 2 se introducen en la semidedue- ción como líneas se llaman premisas.

2.4. Nota. Para facilitar el control, conviene numerar por la izquierda las líneas de cada semideducción y anotar por la derecha el nombre abreviado de la regla de inferencia empleada y los números correspondientes a las líneas a las que se ha aplicado la regla.

2.5. a sea una fórmula de y F sea un conjunto de sentencias de

Definición:

Una deducción en de « a partir de F es una semideducción en a partir de F, tal que su primera línea es ? a y sus restantes líneas están todas marcadas.

2.6. Definición:

a es deducible en 5£ a partir de T si y sólo si hay una deducción en i ? de « a partir de F.

T t—j? a” sea una abreviatura para “a es deducible en 5£ a partir de F ”. Cuando la referencia a ^ no sea relevante, escribiremos simplemente T 1- a”.

“ai, ..., a„i— j?/3” sea una abreviatura para “ ja1; ..., an\ \—¡e ¡3”.

2.7. Una fórmula a de í f es un teorema lógico de si y sólo si a es deducible sin premisas en es decir, si y sólo si 4> a.

“1—5? a” sea una abreviatura para “<j> \—s a”.

2.8. Teorema de finitud para la deducibilidad:F \—<g a si y sólo si hay un número finito de fórmulas 7 1 , ..., 7 » de F, tales

que 7 1 , ..., 7 „ í-*. a.

Dicho en otras palabras:

F a si y sólo si hay un subconjunto finito A c T , tal que A ot.Esto se sigue de la definición dada en 2.3.

2.8. De la definición de la deducibilidad se sigue también:a) Si A i— a y A C F, entonces F \—x a.b) Si a \—z /3 y ¡3 \—s y, entonces a \—v y.c) Si i—& a, entonces F i—z a.En efecto, i— x a significa que 4> a, de donde se sigue que V cr.

por a), ya que <j> C T.d) Si 7 1 , ya i—i» a, entonces (71 a . . . a y„) a.En efecto, para deducir a en Jz? a partir de (71 a . . . a 7 „) empezamos por

introducir ía premisa (7 * a . . . a 7 ,,) y eliminar los conyuntores, obteniendo así n líneas 7 1 , ..., y„. A partir de ahí procedemos como en la deducción de a en .S? a partir de 7 1 , ..., ya, con la sola diferencia de introducir 7 » (1 < i < n ) por la regla de repetición cada vez que antes la introducíamos como premisa.

II.3. Reglas derivadas de inferencia

3.1. Las reglas primitivas de inferencia fueron enumeradas en 1.2. Llamamos reglas derivadas de inferencia a las reglas de inferencia que no nos permiten inferir nada que no fuese ya deducible a partir de las premisas correspondientes con ayuda de las solas reglas primitivas, pero que en cambio nos permiten abreviar las deducciones, haciendo en un solo paso lo que normalmente tendríamos que hacer en varios.

3.2. Justificar una regla derivada de inferencia significa mostrar que es superflua en el cálculo, es decir, mostrar cómo, por medio de las otras reglas de inferencia, puede obtenerse el mismo resultado.

3.3. Lista de algunas reglas derivadas de inferencia (expuestas según el esquematismo ya explicado en 1 .1 ), seguidas de sus correspondientes justificaciones:

Regla del paso de la negacióndel condicional a la con y unción NCC:

Justificación: 12

3456

78

910

f (a a ~~i /3)1 (a A 1 (3)

af p

{a a - 1 /3)— 1 (a a ~1 ¡3)

o (a -> /3)

ÍC. 5, 7 R, 3 R ,1

REGLAS DERIVADAS DE INFERENCIA 55

Regla del tertium non da tur TND;

Justificación: 12 — ( 2 v “ i a)34 — i a5 (a v ~i a) ID, 46 i ( í v u ) R ,27 (« v a) ID. 3

(a v ~i a)

Regla de introducción del disyuntoren el antecedente IDA

« -> /3 T~»/3

a v y —> /3Justificación: 1

2

345 0 -789

a ^ / 3 T ->j8 "? a v 7 —> j8

ot v 7

f/3-1/3“ I 3 MT, I. 6

ED, I. 7 MT, 2, 6

Regla de identidad I : t = t

Justificación: 1 ? t — t2 j f Ax(x = t-> x— t) ; x no esté en t3 =4 | x = t5 t = t E l , 2

Regla de la simetría de la identidad SI :

Justificación: 1 ty = U2 f U — t,3456

t-2 = t, IAx (x = i2 —> í;. = x) II, 3 ti — t-2-* u ~ ti EG, 4 f2 = ti MP, 5,1

Reglas de la transitividad de la identidad TI:

t, = UU = t i

x no esté en U

ti — t2t-2 = t-2t i

ti = t-2 til t-i ti = h

t-2 — íits = t3 ty = U

t-2 = h

til — t-2ti — t-2

Justificación: 1 h = í2

2 t, = #3

3 í.l = *34 Ax (x = í5 *1 = #2 ->6 t] — fu

x — í3) II, 2 = t3 EG, 4

MP, 5 ,1

x no esté en t-¿

De1 igual modo se justifican las otras tres reglas.

Reglas de negación del generalizado! NG :—. Ax a Vx ~i a

\/x —i a “ > Ax a

Justificación: —i Ax a f Vx ~i a

“ i Vx ~i a f Ax a

?<x— I (X

Vx a - . V x - .

Ax a

Justificación: 1 Vx

IP, 6

R, 3 R, 1

2 f —. Ax a3 —> —. Ax a4 Ax a DN, 35 —. 5 “ a EP, 1; it no esté en a6 5 “ a

XEG, 4

Reglas de negación del particularizador NP :Vx a Ax ■

Ax ■ Vx i

Justificación: 12n

4U67

Justificación: 123456

—> Vx <x ? Ax —. x

? u—i —i a aVx a —> Vx *

Ax —. a ? —> Vx a

—. “ . Vx ¡z Vx a 5 ” <x

X

- . 5 “ a

DN, 4 IP, 5 R ,1

DN, 3EP, 4; u no esté en a EG, 1

EJERCICIOS DE DEDUCCION 57

Para pasar de n líneas otj, a„ a una nueva línea (¾ a . . . a a„) necesitamos aplicar n — 1 veces la regla de introducción del conyuntor, 1C. Por medio de la gran regla de introducción del conyuntor, GIC (que a continuación introduciremos) realizaremos en un paso lo que hasta aquí sólo podíamos realizar en n — 1. Lo mismo sucede en otros casos. He aquí varias reglas derivadas, cuya corrección puede ser trivialmente mostrada, y que en determinadas ocasiones abrevian considerablemente las deducciones. Las designaremos anteponiendo una “G” a la abreviatura de la correspondiente regla simple.

Gran regla de introducción del conyuntor GIC :

Gran regla de eliminación del generalizado!- GEG :

Gran regla de introducción del par.ticularizador GIP

(<*i a .. . a a*)

Axu ..., x„5 f‘’a;i,

Sh,

Vxi, ..., x„ a

Gran regla de eliminación del particularizador GEP :Vxt, ..., x„ a 5«!. •••, «„ a

xx , .... »•„

donde u ly son variables distintas entre sí que no aparecen en línea anterior alguna.

Gran regla de negación del particularizador GNP :

—i V xt, ...,x„ a A*i, —i aAxj, x„—i a ’ —i Vx-i, . . . ,xn a

II.4. Ejercicios de deducción

Una de las principales finalidades prácticas de la lógica consiste en enseñar a deducir correctamente. Por medio de deducciones formales podemos probar que una determinada sentencia es un teorema de una teoría, que una determinada argumentación, presentada en el lenguaje ordinario, es correcta, etc.

Aunque las deducciones ya han sido definidas en 2.5, es necesaria alguna práctica para llegar a dominar el arte de deducir. Por eso ofrecemos al lector a continuación 35 ejercicios de deducción. Es conveniente que el lector trate de hacerlos por su cuenta y sólo mire las deducciones corres


pondientes después de haberlas hecho él mismo. La deducción que se le ocurra al lector puede ser correcta y no coincidir con la aquí presentada. Si F i— «, hay un número infinito de deducciones distintas de a a partir de T.

Ejercicio número 1.

ax s= Ax (a —> a)

Pruébese: i— ax.

N o t a : Obsérvese que ax no es una fórmula, sino un esquema de infinitas fórmulas.

Deducción correspondiente al ejercicio número 1.

13

3

? Ax (a -» a)

? (a —> a)


*i s Axy (Rxy v Ryx)

a-, = Ax fíxx

Pruébese: ax i— a2.


1 ? Ax fíxx

A xy (Rxy v Ryx)2

3

4

5

6

Rxx v Rxx

? fíxx

-i Rxx

Rxx

prem. ax

GEG, 2

ED, 3, 5


»i s Ax (Px Qx)

?.■> - - Vx Px > Vx Qx

Pruébese: ax i— a2.

1 t Vx Px -» Vx Qx

2 Vx Px

3 fu EP, 2

4 Ax (Px -» Qx) prem. «j

5 Fu Qu EG, 4

6 Qu MP, 5 ,3

7 Vx <?x IP, 6


a i = Vy (Fy —> Ax Fx)

Pruébese: i— at .


1 f Vy (Fy -> Ax Fx)

2 -i Vy (Fy —> Ax Fx)

3 Ay “ i (Fy —> Ax Fx) NP, 2

4 ? Ay (Fy a “ i Ax Fx)

5 —i (Fy Ax Fx) EG, 3

6 Fy a ~i Ax Fx NGC, 5

7 .> A x F x

8 Fx a —i Ax Fx EG, 4

9 Fx EC, 8

10 Fx a —i Ax Fx EG, 4

1 1 -i Ax Fx EC, 10


ax = Vy (Vx Fx —» Fy)

Pruébese: h- «i.



1 t Wtj (Vx Fx —» Fy)

2

3

4

5

6

7

8

9

10

—i Vi/ (Vx Fx —» Fy)

Ay ~i (Vx Fx -» Fy)

—i (Vx Fx —» Fy)

V/ x Fx a —i F ij

Vx Fx

Fz

f Vx Fx -> Fz

Fz

Vy (Vx Fx —> Fy)

Ejercicio número 6

ai = Vx (Rxx a ~i fíxx) v Axy (fíxy v Ryx) a2 = Ax Rxx

Pruébese: ai 1— «2.

Deducción correspondiente al ejercicio número 6 .

1 t AxRxx

2

3

4

5

6

7

8

9

10

11

12

13

f Rxx

—t Rxx

Vx (Rxx a —i Rxx) v Axy (Rxy v Ryx)

? —i Vx (Rxx a — Rxx)

—i —i Vx (Rxx a —i Rxx)

Vx (Rxx a —i Rxx)

Riw a “ i Ruu

Ruu

—i Ruu

Axy (Rxy v Ryx)

Rxx v Rxx

Rxx

NP, 2

EG, 3

NGC, 4

EC, 5

EP, 6

R ,7

IP, 8

prem. ai

DN, 6

EP, 7

EC, 8

EC, 8

ED, 4 ,5

GEG, 11

ED, 12, 3



a] = Ax (Vi/ (Lije a Cxy) —> —i Ai/ (Lym —» Cxy))

a2 ™ Vx Ay (Lyc v Lym —» Cxy)

a3 = Vi/ (Lyc —> Ax Vw Cx«)

Pruébese: ai, «2 1— «s-


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

t V y (Lije -> Ax V u Cxu)

Vx Ay (Lyc v Lym -> Cxy)

Ay (Lyc v Lym —> Cx„y)

Lwc v Lwm —> CxqW

f Lwc —» Ax Vw Cxu

Lwc

Lwc v Lwm

Cx„w

Lwc a Cx0w

Vy (Lyc a Cx0y)

Ax (Vy (Lyc a Cxy) -> —i Ay (Lym -> Cxy))

Vy (Lyc a Cx„y) -» —i Ay (Lym -> Cx0y)

—i Ay (Lym —> Cx„y)

? A y (L y m -^ C x 0y)

f Lym —» Cx0y

Lym

Lyc v Lym

Lyc v Lym —> Cx„y

Cx0y

Vy (Lyc —> Ax Vw Cxw)

prem. a2

EP, 2

EG, 3

ID, 6

MP, 4, 7

IC, 6 , 8

IP, 9

prem. «i

EG, 11

MP, 12,10

ID, 16

EG, 3

MP, 18,17

IP, 5

Ejercicio número 8 .

<x\ = Axy (Vu (Rxu a R í/ u) —> Rxy)

a2 = Ax Vy Rxy

oc:t = Axyz (Rxy a Ryz -> Rxz)

Pruébese: a(, a2 i— ®s-

Deducción correspondiente al ejercicio número 8 .

1 ? Axyz (Rxy a Ryz —> Rxz)

2 1 ? Rxy a Ryz -> Rxz

3 Rxy a Ryz

4 Rxy

5 Ryz

6 A xV yR xy

7 Vt/ Rzy

8 Rzto

9 Rzto

10 Rzw a Rzu;

11 Vu (Rzu a Rzu)

12 Axy (Vu (Rxu a Ryu) -» Rxy)

13 Vu (Rzu a Rzu) —> Rzz

14 Rzz

15 Rzz a Ryz

16 Vu (Rzu a Ryu)

17 Vu (Rzu a Ryu) —» Rzy

18 Rzy

19 Rxy a Rzy

20 Vu (Rxu a Rzu)

21 Vu (Rxu a Rzu) -» Rxz

22 ! Rxz

EC, 3

EC, 3

prem. a2

EG, 6

EP, 7

R , 8

IC, 8, 9

IP, 10

prem. ctj

CEG, 1 2

MP, 13, 11

IC, 14, 5

IP, 15

GEG, 12

MP, 17,16

IC, 4,18

IP, 19

GEG, 1 2

MP, 21, 2 0


«x = Ax (Acx Hx a Axx)a2 = Hea3 = —i Vx Acx

Pruébese: a2 i— a3.


N o t a : Este ejercicio puede interpretarse como una formalización de la siguiente argumentación: “Carlos afeita a todos los habitantes de Sitges que no se afeitan a sí mismos y sólo a ellos. Carlos es un habitante de Sitges. Por consiguiente, Carlos no afeita a nadie”.


1 f —i Vx Acx

2

3

4

5

6

7

8

9

1011

12

Ax (Acx Hx a — i Axx)

l íe

Acc H e a —i Acc

Acc —> H e a Acc

H e a Acc —> Acc

? Acc

—i Acc

He a — i Acc

Acc

He a Acc

—i Acc

prem. ai

prem. a2

EG, 2

EB, 4

EB, 4

IC, 3, 8

MP, 6 , 9

MP, 5, 7

EC, 11


«i = Ax (Ay (Fy -> ñxy) -> Ay (Py -> Rxy)) a2 = Vxy {Py a — ' Bxy) a3 = Vy (Fy a —i Ax Rxy)

Pruébese: ai, a2 i— a3.

N o t a : Este ejercicio puede considerarse como una formalización de la siguiente argumentación: “Quien desprecia a todos los fanáticos desprecia

5 . — LÓGICA DE PR IM ER ORDEN

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

2122

SINTAXIS: UN CALCULO DEDUCTIVO

también a todos los políticos. Alguien no desprecia a un determinado político. Por consiguiente hay un fanático al que no todo el mundo desprecia”.


V y (F y AxRxy)

Ax (Ay (Fy -> Rxy) Ay (Py Rxy)) prem. «i

Vxy (Py a - i Rxy) prem.

P u A 1 Rwu GEP, 3

Ay (Fy Rwy) -> Ay (Py -> Rwy) EG, 2

t —i Ay (Py Rwy)

—i —i A;/ (Py—> Rwy)

Ay (Py Rwy) DN, 7

Pu -» Rwu EG, 8

Pu EC, 4

Rwu MP, 9 ,10

—i Rwu EC, 4

~i A y (F y -*R w y ) MT, 5, 6

Vy -i (Fy -> Rwy) NG, 13

- i (Fy0 > Rwy„) EP, 14

Fy0 a " i Rwy0 NCC, 15

Fy0 EC, 16

—i Rwy0 EC, 16

Vx ~■i Rxy,, IP, 18

—i Ax Rxy„ NG, 19

Fy0 a h A i Rxy,, 'IC, 17, 20

Vy (Fy a h Ax Rxy) IP, 21


ofi = (Vx Px —» (Vx Gx -» Ax Hx)) <-* Axyz (Pz a Gy -> Hz)

Pruébese: i— otj.

1

2

3

4

5

6

7

8

9

101112

13

14

15

16

17

18

19

20

21

2223

24

25

26

27


65

(Vx Px —> (Vx Gx —» Ax Hx)) Axyz (Px a Gy —» Hz)

? (Vx Px —> (Vx Gx -> Ax Hx)) —> Axyz (Px a Gy —> Hz)

•Vx Px -> (Vx Gx -> Ax Hx)

Axí/z (Px a Gy —> Hz)

Px a Gy —» Hz

Px a Gy

Px EC, 6

Vx Px IP, 7

Vx Gx —» Ax Hx MP, 3, 8

Gy EC, 6

Vx Gx IP, 10

Ax Hx MP, 9 ,1 1

Hz EG, 12

Axyz (Px a Gy —» Hz) —> ('Vx Px —> (Vx Gx —> Ax Hx))

Axyz (Px a Gy -> Hz)

? Vx Px —> (Vx Gx —» Ax Hx)

Vx Px

? Vx Gx —> Ax Hx

Vx Gx

? A xH x

f Hx

Pu EP, 17

Gw EP, 19

Pu a Gw IC, 22, 23

Pu a Gw —» Hx GEG, 15

Hx MP, 25,24

(Vx Px -> (Vx Gx -> Ax Hx)) Axyz (Px a Gí/ -» Hz) IB, 2 ,14

66 SINTAXIS: UN CALCULO DEDUCTIVO


<Xx = Ax ( (Bx v N x ) a ~i (Bx a N x ))

o¡2 = Ax (fx — a —> Bx)

a3 = fa = o

a4 = -A Ax Nx

Pruébese: «i, a2, a3 l— a4.


1 ? —i Ax Nx

2 —i ~i Ax Nx

3 Ax Nx DN, 2

4 Na EG, 3

5 Ax (jx = a -» Bx) prem. s2

6 fa = a -+ B a EG, 5

7 fa = a prem. a3

8 Ba MP, 6, 7

9 Ax ((Bx v Nx) a ~i (Bx a Nx)) prem. 0¾

10 (Ba v Na) a —i (Ba a Na) EG, 9

11 i (Ba a Na) EC, 10

12 (Ba a Na) IG, 8, 4


Vx (Ay (y = a —> Py) —» Hx)

a2 ss Vx “ I Hx —» “ I Ax (P« A ~l Hx)

3;. SS Ax Iíx

Pruébese: a¡, a_. i— a:¡.

1

2

3

4

5

6

7

8

9

1011

12

13

14

15

16

Ax Hx

Vx (Ay (y = a ^ Py) —> Hx)

Vx —i Hx —> —i Ax (Pa a —i Hx)

Ax (Pa a —i Hx)

Ax - i (Ay (y = a —> Py) —> Hx)

(Ay (y = « py) Hx)

Ay (y = a —> Py) a —i Hx

Ay (y = o -> Py)Pa

—i Hx

Pa a —i Hx

—i —i Ax (Pa a —i Hx)

Vx - i Hx

Ax ~i —i Hx

—i Hx

Hx

prein. at

prem. aL>

NP, 2

EG, 5

NCC, 6

EC, 7

E l, 8

EC, 7

IC, 9 ,1 0

DN, 4

MT, 3 ,1 2

NP, 13

EG, 14

DN, 15


«i = Ayz (Ax (xey xez) -> y = z)a2 = Auw (Ax (xea Ex a a) a A x (xetu <-» Ex a a) —» u = tv)

Pruébese: ai i— a2.

N o t a : a ! se puede interpretar como el axioma de extensionalidad de la teoría de conjuntos. a2 se puede interpretar del mismo modo como el teorema de la teoría de conjuntos (tipo Quine) que dice que para cada condición a hay a lo sumo una clase de todos los elementos que satisfacen a.

1

2

3

4

5

8

7

8

9

10

11

1213

14

15

16

17

18

19

20

21

2223

24

25

s in t a x is : u n c a l c u l o d e d u c t iv o


A uw (Ax (xeu o & a í ) a A x (xew -o- Ex a a) —> u = w)

Ax (xeu <-» Ex a a) a Ax (xew ++E x a a) u = w

Ax (xeu o Ex a a) a A x (xew <-> Ex a a)

Ax (xeu <-» Ex a a ) EC, 3

Ax (xew <h> Ex a a ) EC, 3

Ax (xeu ** xew)

xeu <-> xea>

xeu -o- Ex a a EG, 4

xeu; -o Ex a a EG, 5

xeu —> Ex a a EB, 8

Ex a a —> xeu EB, 8

xeu> —» Ex a a EB, 9

Ex a a —» xeu> EB, 9

xeu -» xetü

xeu

Ex a a MP, 10,15

xew MP, 13,16

xew —> xeu

xew

Ex a a MP, 12,19

xeu MP, 11, 20

xeu -o- xeu; IB, 14,18

Ai/z (Ax (xeij <-> xes) —» y — z) prem.

Ax (xeu <-> xeu;) —> u = u> GEG, 23

u = w MP, 24, 6

Ejercicio número 15.«i = a = hfcc v Ax Bxx a2 = Ax /ex - c

«3 = —1a — he«4 = 1Rcc —» Rcc

Pruébese: cu, <*2, «3 ¡—Deducción correspondiente al ejercicio número 15.

1 —i Rcc —> Rcc

2 a = hfec v Ax Rxx prem. aj

3 Ax fcx — c prem. a2

4 —i a = 7¡c prem. a3

5 /cc = c EG, 3

6 Ax (x = c - > i ® = hx) 11,4

7 /cc = c -» —i a = hfee EG, 6

8 ~i a — /i/cc MP, 7, 5

9 Ax Rxx ED, 2, 8

10 Rcc EG, 9


<z¡ = ~i (—i fa = fb v “ i Hfa) —> Hfb Pruébese: i— aej.


1 f ~i (~i f a ~ fb v Hfd) —> Hfb

23

4

5

6

7

8

9

10111213

1 4

~ i (—i fa ~ fb v ~i Hfa) —> Hfb

— i (~i fa ~ fb v ~i Ufa)

f fa = fb

—i fa — fb

(— ifa — f b v ~ i Ufa) ID, 4

J 1 II < j 3 R, 2

f Hfa

“ i Hfa

(—i fa ^ f b v — i Hfa) ID, 8

i (—i fa = : fb v i Hfa) R, 2

Ax (x = fa^> Hx) 11,7

fb = /a -» Hfb EG, 11

fb = fa SI, 3

Hfb MP, 12,13

«i = Pa +* Vy (a = y a Py)

Pruébese: h- «i-



1 f P a Vi/ (a — y a Py)

2 ? P a Vy (o = y a Py)

3 P a

4 a = a I

5 a = a a P a [ = 5® (a = y a Py)] IC, 3, 4

6 Vy ( a — y a P y ) IP, 5

7 p Vy (a = y a Py) —> Pa

8 V y(a = i/APy)

9 a = u a P u EP, 8

10 P u [ = 5* Px] EC, 9

11 a — u EC, 9

12 A x (x = u -> Px) II, 10

13 d = u -» Pa EG, 12

14 P a MP, 13,11

15 Pa ^ Vy ( a = y a Py) IB, 2, 7


a, = Ax (x = c <-» —i Vy (Py a Myx))

a2 = —i Ge -» —i Ay (Py -» —i Myc)

a 3 ^ CtC

Pruébese: al5 a2 (— a3.

EJERCICIOS DE DEDUCCION 7J


1 ? Ge

2 “ i Ge

3 Ax (x = c +* ~i Vy (Py a Myx)) prem. a,

4 c = c «-» —i Vy (Py a Myc) EG, 3

5 c = c —» —i Vi/ (Py a Myc) EB, 4

6 c — c I

7 —i Vy (Py a Myc) MP, 5, 6

8 —i Ge —> —i Ay (Py —» —i Myc) prem. «2

9 Ay (Py -» —i Myc) MP, 8, 2

10 Myc) NG, 9

11 (Pu —> —i Muc) EP, 10

12 Pu A ~ l ~ l Muc NGC, 11

13 —i Muc EC, 12

14 Fu EC, 12

15 Muc DN, 13

16 Pu A Muc IC, 14,15

17 Vy (Py a Myc) IP, 16


a, = A yz (Ax (Exy —» Exz) -» y = z)

a2 = Ax (Exu Av Rvx) a A x (Exw Vy Ryx) —» u = te

Pruébese: a, i— a2.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

18

17

18

t Ax (Exu <-> Av Rvx) a Ax (Exw Vy Ryx) -> u = io

Ax (Exu <-» Au Rux) a Ax (Exu; -o- Vy Ryx)

Ax (Exu <-» Av Rvx) EC, 2

Ax (Exw <-» Vy Ryx) EC, 2

Ai/z (Ax (Ext/ -» Exz) -> y = z) prem. at

Ax (Exu —»■ Exw) —»u = tu GEG, 5

Ax (Exu —> Exu;)

Exu -o- Av Rvx EG, 3

Exu -*■ Av Rvx EB, 8

Exw o V y Ryx EG, 4

Vi/ Ryx -> Exw EB, 10

Exu —» Exu;

Exu

Av Rvx MP, 9 ,13

Rvx EG, 14

y y Ryx IP, 15

Exw MP, 11,16

u — w MP, 6 , 7


fltt = Axyuw (fxu = y a fxw = y -^ u — w) a2 Vz Ax (fxz = x a Vy fxy = z) z:¡ -.-s Vz A tu (Ax fxw x <-» w - _ z)

Pruébese: a¡, a¡. i— a».

N o t a : ai y c:;. son dos teoremas de la teoría de grupos, que en los ejercicios 23 y 22, respectivamente, son deducidos a partir de los axiomas de esa teoría. a:, es el teorema de la teoría de grupos que afirma la existencia unívoca de un elemento neutro.

1

2

3

4

5

6

7

8

9

10

11

1213

14

15

16

17

18

19

20

212223

24



Vz A w (Ax f x w = x <r>iv = z)

Vz Ax (fxz = x a V yfxy = z) prem. «•>

Ax (fxz0 — x a Vy fxy = z0) EP, 2

Aw (Ax / xiü = r-r> tr= :Z o)

w = z0 —> Ax fxw = x

in = z0

f Ax fx w — x

fx z0 = x a Vy fxy = z0 EG, 3

fx z0 = X EC, 8

Aw (m = z0 -> /xw = x) 11,9

tD = Z0 —> fxw - X EG, 10

fxw = X MP, 11 ,6

A x fxw — X —> tD = z 0

Ax fxw = x

XII3X EG, 14

fx z0 = x a Vy fxy = z0 EG, 3

XIIHX EC, 16

A x y u w (fxu — y a fxw — y - > u = w ) prem.

/xzo — x a fxw = x ^ z » = w GEG, 18

fxz0 = x a fxw = x IC, 17,15

z0 = w MP, 19, 20

w = z 0 SI, 21

Ax fxw = x <-» mj = z0 IB, 13, 5

Vz Au> (Ax fxw = x <-» 1« i= z) IP, 4


a, = Axyz ffxijz = fx fyz

<x2 = Ax fxhx — k

74 sintaxis: un cálculo deductivo

ot3 = Ax fkx = x Xi = Ax?/ Vz fxz = y

Pruébese: xu a2, xs h- o¡4.

N o ta : « i , a2 y x?, constituyen una axiomatización posible de la teoría de grupos. a 4 sería en esta interpretación el teorema que dice que siempre hay un cociente por la derecha.


1 f A xy V z fxz = y

2 A xyz ffxyz = fx fyz prem . «!

3 Ax fxhx = k prem . a2

4 Ax fkx = x prem . a3

5

j:

¿e a LT11! EG, 4

6 A x(x = k -+ fxy = y) 11,5

7 fxhx = k~* ffxhxy = y EG, 6

8 fxhx = k EG, 3

9 ffxhxy = y MP, 7, 8

10 A z ffxhxz = fxfhxz GEG, 2

1 1 ffxhxy = fxfhxy EG, 10

1 2 fxfhxy = y TI, 9 ,11

13 < '-k 8 II IP, 12


a, = A xyz fxfyz = ffxyz00= A xy Vz fxz = ya-< = A xy Vz fzx = ya4 = Vz Ax (fxz — x a Vy fxy = z)

Pruébese: a,, <z->, «:t 1—«4-

N o ta : ax, a2 y son los axiomas de Hamilton para la teoría de grupos. 24 es el teorema de la teoría de grupos que dice que hay un elemento neutro y que para cada elemento del grupo hay un inverso.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23


Vz Ax (fxz = i a V;/ /xy z)

Axy Vz fxz — y

Vz/yz = y

prem. <z2

GEG, 2

fyu = y

? Ax (fxu = x a Vy /xy = ti)

EP, 3

Axy V z fzx = y

V z/zy = x

prem. a3

GEG, 6

II3 EP, 7

Au (u = y —> fwv = x) 1 1 , 8

fyu = y f w f y u = x EG, 9

fwfyu — x MP, 10,4

Axyz fxfyz — //xyz

fwfyu = ffwyu

prem. «i

GEG, 12

ffwyu - x TI, 13,11

Au (u = fwy -» fvu = x) II, 14

x = fwy —*■ fxu - x EG, 15

x = fwy SI, 8

fxu = X MP, 16,17

ií41>

GEG, 2

fxz0 = n EP, 19

V y/xy = n IP, 20

fxu = x a Vy /xy = « IC, 18,21

Vz Ax( fxz = x a Vy /xy = z) IP, 5


= Axyz fxfyz = ffxijz a2 = Axy Vz fxz = y o¡¿ = Axy V Z fzx = yo¡4 = Axyuw (fxu — y a fxw — y -± u = m)

1

2

3

4

5

6

7

8

9

10

1112

13

14

15

16

17

18

19

20

21

2223

24


Pruébese: a->, «3 i— a*.

N o ta : 04, a2 y 0 :3 son los axiomas de Hamilton para la teoría de grupos a t es el teorema de la teoría de grupos que dice que para cada dos elementos del grupo hay a lo sumo un cociente por la derecha.


Ax y u w (f x u = y a f x w = y - > u ~ w )

f f x u = y a f x w = y —> u — w

f x u ~ y a f x w = y

f x u = y EC, 3

f x w = y EC, 3

f x w — f x u TI, 5, 4

Ax y V z f z x = y prem. a:¡

Vz f z u = u GEG, 7

f z xu = tí EP, 8

11ah*>

GEG, 7

fz-vx = s j EP, 10

Axy V z f x z = y prem. a2

V z /uz = w GEG, 12

f u z s = U) EP, 13

Au (0 = Z] -> f v u — u ) 11,9

f z 2x = Zx -> f fZtXU = u EG, 15

f f z 2x u = u MP, 16, 11

Ari/z f x f y z = f f x y z

fz-> f x u — f f z ¿ x u

prem. x ,

GEG, 18

f z 2 f x u = u TI, 19, 17

A v (v = f x u - » f z 2v = u) 1 1 ,2 0

/xu) = f x u —> /z2 f x w — u EG, 21

f z 2 f x w — u MP, 22, 6

PS K H s II H s GEG, 18

3= Vy (Ax (Sx a Gx <->x = y) a y = r)

a2 = Ax (Sx a i x = c —> Arx)

a3 = Vx (Sx a Gx a Apx)

a4 - Axy (Axy —> —i Ayx)

ar, = ~> Sp.

Pruébese: o¡¡, a2, *:•„ a* t- * 5.

25 ffz2xw = u TI, 24,23

26 Av (v = fz2x -> fvw = u) II, 25

27 Zj — fz2x -> fztw = u EG, 26

28 Zj = /z2x SI, 11

29 fzxW ~ u M P,27,28

30 Ao (v — w -> /Zjü = u) II, 29

31 fuz3 = w -> fz,fuza = « EG,30

32 fzi fuza = u MP, 31,14

33 /Z] fuz3 = //z,uz;i GEG, 18

34 //zi«z3 = « TI, 32, 33

35 Ao (v — fziu -> fvz-i — u) II, 34

36 u — fz^u -> fuza = u EG, 35

37 u = fz-¡_u SI, 9

38 fuza = u MP, 36,37

39 u = w TI, 38,14

N o t a : Este ejercicio puede considerarse como una ÍOrmalización de la siguiente argumentación: “Sólo hay un sofista que enseña gratuitamente, y éste es Sócrates. Sócrates argumenta mejor que ningún otro sofista. Platón argumenta mejor que algún sofista que enseña gratuitamente. Si una persona argumenta mejor que otra segunda, entonces, esta segunda no argumenta mejor que la primera. Por consiguiente, Platón no es un sofista”.

1

2

3

4

5

6

7

8

9

10

1112

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27


—i Sp

—i —i Sp

Sp DN, 2

Vx (Sx a Gx a Apx"1 prem. a3

Su A Gu A Apu EP, 4

\Jy (Ax (Sx a G x <^x = y) Ay = r) prem.

Ax (Sx a Gx x = w) a w = r EP, 6

Ax (Sx a G x o x = «;) EC, 7

Su a Gu <r*U = w EG, 8

Su A Gu —MI = w EB, 9

Su a Gu EC, 5

u = w MP, 10,11

w — r EC, 7

r = u TI, 13,12

Apu [ = 5" Apx] EC, 5

Ax (x = u —>■ Apx) II, 15

r — u —> Apr EG, 16

Apr MP, 17,14

Axy (Axy —> Ayx) prem. a 4

Apr —> —i Arp GEG, 19

—i Arp MP, 20,18

Ax (Sx a i x ~ r —> Arx) prem. a2

P —i p — r

J J II -4

p — r DN, 24

p — u TI, 25,14

p = w —> App EG, 16

28 App MP, 27,26

29 App —» —i App GEG, 19

30 —i App MP, 29, 28

31 5p a —i p = r —> Arp EG, 22

32 Sp a ~i p — r IC, 3, 23

33 (Sp a ~i p = r) MT, 31,21


«i = Ax (Px « r = a ) ^ i x P r = a

Pruébese: \— o.x.


1 f

2

Ax (Px <r+x = a)

Ax (Px <-» x = a)

—> i x P x ~ a

3 Vt/ Ax (Px ** x = y) IP, 2

4 PlX Px DP, 3

5 P IX Px ** tx Px — a EG, 2

6 Ptx Px —> tX Px = a EB, 5

7 [X Px = 0 MP, 6 ,4


«i == —i Vx a —» ix a = im u = u

Pruébese: i—

6 . ----- L Ó G I C A D E P R I M E R O R D E N

1 f ~i Vx a ’.x a = >.u u = u

2 J <3 ? —i Vy Ax (a -o x = y) *

4 —i —i Vy Ax (a x = y)

5 Vy Ax (a -o x = y) DN, 4

6 5^a a DP, 5

7 Vx a IP, 6

8 —i Vx a R, 2

9 tx a = tw u — u DI, 3

" Donde y es una variable que no está libre en a.


= R cfa= Ax (Rxfa —» x = c)

a3 = R tx Rx/fl /a

Pruébese: al; a2 l— «3-


1

2

3

4

5

6

7

8

9

10

R ix Rxfafa

Rcfa

Ax (x = c Rx fa)

Ax (Rxfa - * x = c)

f Ax (Rxfa <-» x = c)

x = c -» Rxfa

Rxfa —>x = c

Rxfa <-> x = c

Vy Ax (Rx/a <-» x = y)

R >.x Rxfafa

prem. ai

1 1 , 2

prem. a2

EG, 3

EG, 4

IB, 6 , 7

IP, 5

DP, 9

a! = Vi/ (Ax (Hx <-> x = y) a By) B tx Hx

Pruébese: at.


1 ? Vy (Ax (Hx <-> x = y) a By) -» B ix Hx

2 Vy (Ax (Hx <-> x = y) a By)

3 Ax (Hx <-> x = tt) a Bu EP, 2

4 Ax (Hx<-> x = u) EC, 3

5 Vy Ax (Hx <r>x = y) IP, 4

6 H ix Hx DP, 5

7 H tx Hx ix Hx — u EG, 4

8 H tx Hx - * tx Hx = u EB, 7

9 tx Hx = u MP, 8, 6

10 Bu [ = 5 " B x ] EC, 3

11 Ax (x = u -» Bx) II, 10

12 tx Hx = u -» B tx Hx EG, 11

13 B tx Hx MP, 12, 9


ai = Vi/ (Ax («<-> x = y) a By) -» B tx a, donde y no está en a.

Pruébese: i— ax.


1

2

3

4

5

? Vi/ (Ax (a x — y) a By) B tx a

V y (Ax (<x+>x = y) a By)

Ax (<x x = u) a Bu

Ax (a <-> x = «)

Vi/ A x (a x = y )

EP, 2

EC, 3

IP, 4

6 5'-ca aX

DP, 5

7 5'®“ a ex a = u EG, 4

8 5 Icla! a —> tx a = uX

EB, 7

9 t xa = u MP, 8, 6

10 Bu [ = 5 ” Bx] EC, 3

11 Ax (x = u —> Bx) II, 10

12 tx a = u —> B ix a EG, 11

13 B tx a MP, 12, 9


«i = Ax (Px <-> x = ¡x Px) <-* Vy Ax (Px <r+x = y)

Pruébese: i— ai.

12

3

4

5

6

7

8

9

10

11

12

13

14

15

Ax (Px <-> X = ¡X Px) <-» Vi/ Ax (Px x = !/)

? Ax (Px X II Vf/ Ax (Px * = !/)

Ax (Px <-> x = tx Px)

y y Ax (Px <-» x = i/) IP, 3

* y y Ax (Px x = y) -> Ax (Px <-> x == tx Px)

y y Ax (Px <r+x = y)

Ax (Px <-» x = «) EP, 6

P a Px DP, 6

P ¡X Px <-» IX Px = u EG, 7

P (X Px —» !X Px = U EB, 9

IX Px = u MP, 10, 8

Aw (w = u -» Ax (Px *-> x = i d ) ) 11,7

t x Px = U —J Ax (Px <-> x = tx Px) EG, 12

Ax (Px x — t X Px) MP, 13,11

Ax (Px <-> x = !X Px) <-» V í/ Ax (Px <-» x = í/) IB, 2, 5

o:, = Vy Ax (Amx <r>x — y)7.-2. = ix Amx — tx Aax «s = ix Aax — p o¡4 = Am ’.x Axa a 3 = tx Axa = p

Pruébese: a4, a2, a;¡, a4 1— a6.

N o ta : Este ejercicio puede considerarse como una formalización de la siguiente argumentación: “María ama solamente a un hombre. El hombre amado por María es aquel a quien Apolonia ama. Pituso es el hombre a quien Apolonia ama. María ama al hombre que ama a Apolonia. Por consiguiente, el hombre que ama a Apolonia es Pituso”.


1 Y ix Axa — p

2 Am ix Axa prem. a4

3 V í/ Ax (Amx <->x = y) prem. ax

4 Am tx Amx DP, 3

5 Ax (Amx <-» x = u) EP, 3

6 Am ix Amx tx Amx = u EG, 5

7 Am tx Amx —> tx Amx = u EB, 6

8 tx Amx = u MP, 7, 4

9 Am tx Axa <-» tx Axa = u EG, 5

10 Am tx Axa —» tx Axa — u EB, 9

1 1 tx Axa = u MP, 10,2

12 tx Amx — tx Axa TI, 8 ,1 1

13 tx Amx — tx Aax prem. a2

14 tx Axa = tx Aax TI, 12, 13

15 tx Aax = p prem. 7¿

16 tx Axa = p TI, 14, 15

84 sintaxis: un cálculo deductivo


ai = t = tx Axc a2 = ~ ' S rka3 = Ax (—i Sxk Axc) a4 = Vy Ax (Axc <-» x ~ y) a5 = t = r

Pruébese: a1; a2, a8, a4 i— a 5.

No ta : Este ejercicio puede considerarse como una formalización de la siguiente argumentación: “Toribio es el hombre que ama a Clotilde. A Roberto no le cae simpática Carina. Todo el mundo que no simpatiza con Carina ama a Clotilde. Únicamente una persona ama a Clotilde. Por consiguiente, Toribio y Roberto son la misma persona”.


1 t — r

2 Ax (~i Sxk - * Axc) prem. a8

3 ~i Srk Are EG, 2

4 —i Srk prem. a2

5 Are MP, 3 ,4

6 Vy Ax (Axc <7±x = y) prem. a4

7 A i x Axcc DP, 6

8 Ax (Axc <r*x = u) EP, 6

9 A t x Axc c -o- t x Axc — u EG, 8

10 A t x Axc c —» t x Axc = u EB, 9

1 1 t x Axc = u MP, 10, 7

1 2 Are * * r = u EG, 8

13 Are —>■ r = u EB, 12

14 r — u MP, 13, 5

15 t x Axc = r TI, 11,14

16 t = t x Axc prem. «i

17 t = r TI, 16,15

«i = Vxy (Px a Py a ~ i x = y) -> ix Px = iz z = z

Pruébese: i— ax.


1 ? Vxy (Px APy a ~ i x = tj) —> tx Px — iz z = z

2 Vxy (Px a Py a —i x ~ y)

3 Pu A PlO A ~ 1 U = W GEP, 2

4 t —i V y Ax (Px <->x = y)

5 —i —i Vy Ax (Px <->x = y)

6 Vy Ax (Px <-» x = y) DN, 5

7 Ax (Px <-» x = o) EP, 6

8 Pu<r>u = v EG, 7

9 Pu —> u = V EB, 8

10 Pu EC, 3

1 1 U = V MP, 9 ,10

1 2 Pw <H*W = V EG, 7

13 Pto —> t ü — V EB, 12

14 Pw EC, 3

15 W = V MP, 13,14

16 M = W TI, 11,15

17 —I U — W EC, 3

18 tx Px = IZ z = z DI, 4


«i = tx ~i Vy (Py a Myx) = d

a2 - - Pd

0¡3 - Vx (Px A Ex)


a4 — Ax (Px a Ex Ay (Py A~>Ey Mxy))0:5 = ^1 E d -> Vz (Pz a Mz ix —i Vi/ (Py a Myx))

Pruébese: a1; a2, a3, a4 i—as.

N o ta : Este ejercicio puede considerarse como una formalización de la siguiente argumentación: “Dios es el ser mayor que el cual nada puede ser pensado. Dios puede ser pensado. Algún ser puede ser pensado y existe. Cualquier ser que pueda ser pensado y exista es mayor que cualquier otro que sólo pueda ser pensado, pero no exista. Por consiguiente, si Dios no existe, entonces hay un ser que puede ser pensado y que es mayor que aquel mayor que el cual nada puede ser pensado”. Obsérvese que en esta formalización la existencia se considera como un predicado y no como un cuantificador.


1 ? — 1 E d - * V z (Pz a Mz íx - i V y (Py a Myx))

2 —1 Ed

3 Vx (Px A Ex) prem. at3

4 Pu A Eu EP, 3

5 Ax (Px a E x -> Ay (Py A~>Ey - » Mxy)) prem. «4

6 Pu a Eu -> Ay (Py a ~ 1 Ey —»• Muy) EG, 5

7 Ay (Py a ~ 1 Ey —> Muy) MP, 6 ,4

8 Pd a 1 Ed —> Mud EG, 7

9 Pd prem. a2

10 Pd a 1 Ed IC, 9, 2

1 1 Mud MP, 8 ,1 0

12 Aw (w = d - ± Muw) II, 11

13 ix ~i Vy (Py a Myx) = d prem. ai

14 tx —i Vy (Py a Myx) = d —> Mu ¡x —1 Vy (Py a Myx) EG, 12

15 Mu ix —1 Vy (Py a Myx) MP, 14,13

16 Pu EC, 4

17 Pu a Mu ix — 1 Vy (Py a Myx) IC, 16,15

18 Vz (Pz a Mz ix —1 Vy (Py a Myx)) IP, 17

ai " Vz Ax fxz = xa2 = Axyuw (fxu — y a fxw = y —>u ~ w ) <*3 = Ax fx iy Ax fxy = x = x

Pruébese: ai, a2 i— <xg.


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1819

20

21

f Ax fx iy Ax fxy -= x — x

Vz Ax fxz - - x

Ax fxz0 = x

? Ay (Axfxy = x * * y = z0)

? Ax fxy = x <-> y = z0

? Ax fxy = x -» y = z0

Ax fxy = x

fxy = x

fxzt) = x

Axyuw (fxu = y a fxw = y —> u = w)

fxy = x a fxz0 — x -> y -- z0

fxy = x a fx%o = *

y = z0

t y = z0 -* Ax fxy = x

y = z0

Au (u = z0 -» Ax /xm - x)

t/ = z0 —» Ax fxy - x

Ax fxy = x

Ax fxy = x y = z0

Vz Ai/ (A xfxy = x<r>y = z)

Ax fx ty Ax fxy = x — x

prem. ai

EP, 2

EG, 7

EG, 3

prem. a2

GEG, 10

IC, 8 ,9

MP, 11,12

11,3

EG, 16

MP, 17,15

IB, 6 ,14

IP, 4

DP, 20

II.5. Teoremas sintácticos sobre la deducibilidad

5.1. Primer teorema de la deducción: a sea una sentencia de S£. Si « h-a /3, entonces v - ? (a /3).

Prueba: Sea a \—z /3, es decir, haya una deducción 3)x en SÉ de ¡3 a partir de a, y tenga esta deducción n líneas. Entonces, consideremos la deducción 3)2\ 1 f (a -»/3)

2 a2 + l ? /3

2 + n

cuyas líneas 2 + 1 , _, 2 -f- n sólo se diferencian de las n líneas de 3>\ enposeer una marca más. En los lugares de 3>2 correspondientes a aquellos de Sdx en que a había sido introducida como premisa obtenemos a por aplicación de la regla de repetición a la línea 2. Así, pues, es una deducción sin premisas y, por tanto, \—z (a —* /3).

5.2. Segundo teorema de la deducción: T sea un conjunto de sentencias. Si F i—% a, entonces hay un número finito de fórmulas 7 1 , ..., y„ e F, tales que (71 a . . . a -> a).

Prueba: Sea T \—z a. Por 2.8, hay un número finito n de fórmulas 7 7 , ..., 7 „ e T, tales que 7 1 , ..., yn t - z a. Por 2.9 d), (71 a . . . a y») z a. Y por 5.1

(71 A . . . A y» ->a).

5.3. Teorema: Sea a una sentencia de Jz?.(1) Si r U jal a, entonces T i— 1 a.(2) Si F U j —1 ají—*’ a, entonces Tv-^a.

Prueba: Sea P U jaj 1—% 1 a , e s decir, haya una deducción 3 )\ en <2? de - i a a partir de Y U ja j , y tenga esta deducción n líneas. Entonces, consideremos la deducción S>2: 1 ? n

2 t u3 a DN, 23 + 1 ? 1 «

3 + n

cuyas líneas 3 + 1 , ..., 3 + n sólo se diferencian de las n líneas de en poseer una marca más. En los lugares de 3¡2 correspondientes a aquellos

TEOREMAS SINTACTICOS SOBRE LA DEDUCIBILIDAD 89

de en que a había sido introducida como premisa obtenemos a por aplicación de la regla de repetición a la línea 3. Así, pues, las únicas premisas introducidas en S)< son las que provienen de T y, por tanto, T v-x ~i a.

Con lo que (1 ) queda probado. De igual modo se prueba (2),

5.4. Teorema:

Si t es un término de P£, entonces j— s V x x — t.

Prueba:

12345

f V xx = f —\ V x x — t Ax x = t

—it = t t — t

5.5. Teorema:

NP, 2 EG, 3 I

Si x no está libre en <x y (a -> /3),entonces i— ¡e (a -> Ax /3).

Prueba: x no esté en a. Sea (a -> /3).

1234

? (a -» Ax /3)I a

•? A x/3 '? a —> /8 pues i—ar (a —> >3)

m P

Luego ¡—2 (a Ax /3).

MP, 4,2

5.6. Teorema: Sean A, A y /A, ..., t„ términos de Jz?, en los que ninguna de las variables x, y, xí ... xn esté libre. Sea Pt%, ..., t« una fórmula de f£ . Entonces:

a) i-s;Ptu . . . ,t n*+ V xu ...,Xn(xí = h a . . . a x » = í » a Pi 1 , . . . , x»)

b ) 1—¡c 'X = /ti, - - tn -oVXj., . . . , xn (Xj. = A A . . . A Xn = f„ A x — fxl t . . . , x„)

c) i-a, A = #2 -<-» V xy (x = A a y = f2 a x = t/)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

2021

Prueba de c) :

t x = t . < ^ > V x y (x — t x a y = U a x = y )

'? ÍJ = t 2 - * \ /x ij (x = #, A IJ = t¿ A X = y)

t , = ío

? V xy (x = #i a y = t2 a x = y)

V xy (r = ¢, a (/ = a x — y)

Axy —i (x = fj a i/ = t2 a x = y ) GNP, 5

—i (íj = t¡ a t2 = t-2 a íi = G) GEG, 6

íj = Í! I

#2 = ¿ 2 I

fi = fj a t2 = t-> IC, 8 , 9

(fi = ti a i2 = fi> a b = G) IC, 10, 3

? V xy (x = tx a y = G. a x = y) —» í, = t2

V x y (x - fi a y = f2 a x = y)

u = t t a w = t 2 a u = w GEP, 13 «, no estén en f(, í.,

u — t x a w = t 2 EC, 14

u = tx EC, 15

u = w EC, 14

ti = w TI, 16,17

w = t-> EC, 15

t i = U TI, 18,19

t i = t -> <-» V x y (x = t j a y = t 2 a x = y ) IB, 2 ,12

De igual modo se prueban a) y b) de 5.6.

5.7. Teorema: Sean a y / ? fórmulas de V£. Entonces:

/ \x (a 0)\—x Ax a <-> Ax /3.

12

3

4

5

6

7

8

9

10

1112

13

14

15

16

17

18

19

20

Prueba:

A x a o A x / 3

A x ( x < - » / 3 )

? A x x - * A x / 3

A x a

? Ax/3

a

a < - » /3

a — > /3

0

f Ax / 3 - * A x a

A x /3

? A x x

— i A x a

V x a

- i 5 " aX

5” x ^ 5 “/3

5 « / 3 - » 5 " x

- > 5 “ /3

s ; /3

A x x A x /3

premisa

EG, 4

EG, 2

EB, 7

MP, 8, 6

NG, 13

EP, 14

EG, 2

EB, 16

MT, 17,15

EG, 11

IB, 3, 10

5.8. Teorema: Sea x una fórmula de ¡ £ . w no esté en tz x.

Entonces:

i—y x = :z x < > (A z (a <-» z = x) v (“i Vtu Az(a^> z — w ) a x = iy y = y)).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

2223

Prueba:

i = ! z s e (A z (a z — x) v (—i Vto Az (a z = w)A X = t y y = y) )

x = tz a -> (Az (a <-» z = jc) v (—i Vin Az (a <-> z = w)Ax = iijtj = y))

x = iza

—i Vw Az (a <-> z = tn) -»(Az (a <-»z = x) v (—i Vw Az (a ^ z — w) a x — iy y = y))

~i Vw Az (a<->z = w)

iz a = u y y = y DI, 5

x = iy y = y t i , 3 ,6

—1 Vw Az (a •<-» z — w) a x — ly y = y IC, 5 ,7

Az (a •<-> z = x) v (—i Vw Az (a ** z = w) a x = - uj y = t/)ID, 8

Vw Az (a «-» z = w) ->(Az (a -*-» z = x) v (—i Vw Az (a z = w) a x = iy y = y))

Vw Az (a « -> z = w)

5 ‘ot a DP, 11

Az (a z = t«) (donde u no está en a y w # z),pues 5 “ a = a, ya que w no está en a EP, 11

5 ‘/ a t o i z a = « EG, 13

5 ‘m a —> iz a = u EB 14Z >tz a = u MP, 15,12

u = x TI, 16, 3

A z (a <-» z = x)

- i A z ( « o z = r) [ = 5 J “ i Az (a <->z = «),ya que 5* a = a, porque w no está en «]

Au (u = a; —i Az (a <-» z = tt)) II, 19

u = x —» —i Az (a z = «) EG, 20

—i Az (a <-> z = «) MP, 21,17

Az(a<->z = u) R, 13

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

CUASIELIMINACION DE DESCRIPTOBES 93

A z (a z = x) v (—i V id Az (a <-> z = w) a x = nj y •_= y)ID, 18

V w Az (a <-> z = id) v —i V id A z (a <-»z = id) —» (Az (az = x) v (—i Vw Az (a -o- z = id) a x = uj y — y)) IDA, 10, 4

V id A z (ot <-» z = w) v —i V id A z (ot <-> z = id) TND

Az (a <-> z = x) v (—i V id Az (<x+* z = w) a x = ty y = y)MP, 25, 26

f Az (ot <r> z = x) -» x = tz a

Az (ot <-» z = x)

V id A z (a -o z = id) IP, 29

5 ‘“ a DP, 30

5 ‘za í « [ z « = x EG, 29

a —> iz a = x EB, 32

tz ot = x MP, 33,31

x = tz ot SI, 34

~i V id A z (a <-> z — id) a x = ’.y y = y —> x = tz a

—i Vw Az (a <->z = w) a x = tyy = y

—i Vw Az (ot <-» z = i d ) EC, 37

tz ot = 11/ y — y DI, 38

x = , y y = y EC , 37

x = tz a TI, 39, 40

(Az (a <-> z = x) v (—i Vw Az (a <-» z = id) a x = iy y = y)) x — iza IDA, 28, 36

x = tz a <-> (Az (ot <-> z = x)v (—i V id Az (a <-> z = id) a x = ty y — y)) IB, 2,42

11.6. Cuasieliminación de descriptores

6.0. En los lenguajes que posean al menos una constante individual podemos hallar fórmulas y términos sin descriptores en cierto modo equivalentes a cualesquiera fórmulas y términos dados, identificando para ello

una de las constantes individuales con una descripción impropia. El teorema siguiente expresa esto con más exactitud.

6.1. Teorema: Sea c una constante individual del formalismo SC. Entonces :

a) Para cada fórmula a de í£ hay una fórmula sin descriptores <x' de 2 , con las mismas variables libres que a y tal que c = uj y = y i— z a a'.

b) Para cada término t de í£ y cada variable x que no esté en t hay una fórmula sin descriptores 9 de con las mismas variables libres que x = t y tal que c = ’.y y = y \—j¿ x = t y.

6.2. Demostración de 6.1 por inducción semiótica simultánea:

Sea t = v.x no esté en t, e. d., x # v

\ - z i = t > o i = rc = '.y y ~ y 1—x x = v -o- x = v por 2.9, c)

Luego hay una fórmula sin descriptores 9 de S6, con las mismas variables libres que x = o y tal que c = ty y — yt— x = t<r^<f; a saber,

9 = x = v.Sea t = a.x no puede estar en t, pues una variable nunca está en una constante

individual.1—z x — a x = a

c = iy y — y ^ ^ x = a <^>x — a por 2.9, c )

Luego hay una fórmula sin descriptores 9 de 3?, con las mismas variables libres que x = a y tal que c = ’.y y — y \—¡e x = # <-» 9 ; a saber,

tf = x = a .

Sea t = ft1, ..., t„. x no esté en t.

Ti, ..., x„ sean n variables que no estén en t.

Por hipótesis inductiva, hay n fórmulas sin descriptores 91, ..., <p„ de Jzf, tales que para cada i (1 VXj, . . . , X n (* , = i] A .. . A X„ = t„ A X = f x u . . . , X„)

CUASIELIMINACIÓN d e d e s c r ip t o r e s 95

Por 2.9, c ) obtenemos

c = iy y = y x = fh , V x , , x „ (x, = í t a . . . a x „, = tn a x =f x x,

De aquí podemos pasar ac = ay y = y v - z x = f a , . . . , £„<-» V x u . . . , x * (<pL a . . . a <pn a x = f x u . . . ,x „ )

Este último paso está justificado porque de lo que damos por supuesto para <p1; ..., <pn se sigue quec = aj y = y ( -* Vx1; ...,x„ (x2 = *1 a ... a i , = tn) <-»Vxu ...,xn (9! a ... a o„)

Luego hay una fórmula sin descriptores 9 de Jz?, con las mismas variables libres que x = f t l t t n y tal quec — aj y = y \—z x = ftlt ..., f„ -o- 9; a saber,9 = V x 1; . . . ,X „ (9 i A .. . A <p„ A X = f x u . . . , X n)

Sea a = P t lt ...,Xi, ...,x„ sean n variables distintas que no estén en a.

Por hipótesis inductiva, hay n fórmulas sin descriptores 9,, <pn de <2?, tales que para cada i (1 <2 i < n), 9,; tiene las mismas variables libres que Xi — ti y c = iy y = y \ - z xt = í¡ <h>- 9¡.

Ahora bien, por 5.6, a)|-^Píl, ...,# „-CA- Vxi, ..., X» (Xi = t, A ... A X,, = tn A PXj, ..., X»)Por 2.9, c ) obtenemos

c = iy y = y i—^ ^*1,..., Vxi,..., x„ (x* = l a ... a x„ = Px^ ..., x„)De aquí podemos pasar a

c = iy y = y ...,*»<->• Vx1 ;..., x„ (91 a ... a 9* a px1? . . . , x„).

Este último paso se justifica como en el caso anterior.

Luego hay una fórmula sin descriptores <x' de i*?, con las mismas variables libres que Ptu ...,tn y tal quec — ty y = y \ - x <*<-»• a'; a saber, a' = Vxí,..., x„ (9! a ... a 9« a P x i , ..., x„).

Sea a = - 1 j8.

Por hipótesis inductiva, hay una fórmula sin descriptores /3 ' de Jz?, con las mismas variables libres que /3 y tal quec = ly y = y t - x P + * / 3 '.

Entonces, c — iy y = y \ - z —1,8 <-» —1Luego hay una fórmula sin descriptores a' de con las mismas varia

bles libres que —1 ¡3 y tal que c = ¡y y = y a * * a'; a saber, a' = —1 ¡3 '.

Sea a = (J3 A y ).

7 . ----LÓGICA DE PR IM ER ORDEN

Por hipótesis inductiva, hay dos fórmulas sin descriptores /3' y 7 ' de üf, con las mismas variables libres que /3 y 7 , respectivamente, y tales que c — ty y = y i— /3 <h> ¡3' c = ny y = y \—z 7 -o- 7 '. Por tanto,c = ty y = y ^ 0 a j ^ / 3 ' a Y-

Luego hay una fórmula sin descriptores a' de .5?, con las mismas variables libres que (/3 a 7 ) y tal que c = ay y — y \-z a saber, a' = (¡3' a 7 ').

De igual modo se prueba el teorema para « = O3 v 7 )« = 03 7) ycc = (J3<h> 7 ).Sea a = Ax /3.Por hipótesis inductiva, hay una fórmula sin descriptores f3' de J2?, con

las mismas variables libres que /3 y tal que c = ly y = y (3 /3'- Por tanto,c = 1 y y = y (J3 /3') por 5.1

i—i? c = ty y = y —> Ax ((3 <-> ¡3') por 5.5c ~ ty y = y Ax (J3 /3')

Ax (J3 <-> ¡3') i—# Ax 13 <-> Ax ¡3' por 5.7c = tyy = y \-z Ax ¡3 <-> Ax /3' por 2.9, b)Luego hay una fórmula sin descriptores a' de ¡ £ , con las mismas varia

bles libres que Ax (3, y tal que c = iy y = y \—x a <-» a' ; a saber, a' = Ax /3'.

De igual modo se prueba el teorema para a = Vx /3.Sea t = tz a. x no esté en tPor hipótesis inductiva, hay una fórmula sin descriptores a ' de S £ ,

con las mismas variables libres que a y tal que c = tí/ y = y \—z. a <-> a'.

Ahora bien, por 5.8,\—z x = iz a <-> (Az (a «-> z — x) v (- 1 V id Az (a «-> z = tu ) a x = ty y — y))

Por tanto,

c = t y y = yí-s? x = tz a <-> (Az (a <-» z = x) v (—1 Vio Az (a <-> z = tu) a x = iy y = y))

c = t y y = yx = tz a <-> (Az (a <-> z = x) v (~ 1 Vio Az (a <-> z = w) a x = c))

c — ty y = yX = tza<r> (Az ( d ' « z = : l ) v (m VlO Az (</<-> Z = tu) A X = c))

CONSISTENCIA Y CONTRADICCION 97

Luego hay una fórmula sin descriptores <j> de S£, con las mismas variables libres que x — iz a, y ta l . que

c — iy y = y N x = t f;

a saber, cp = Az («' z — x) v (~i Vw Az (a' •<-> z = w) a x = c)q.e.d.

II.7. Consistencia y contradicción

7,0. Consistencia y contradicción son propiedades de fórmulas o de conjuntos de fórmulas. Supongamos que Y es un conjunto de fórmulas de un formalismo 2 '. Si una de las fórmulas de Y es la negación de otra de las fórmulas de F, diremos que Y es contradictorio. Si ése es el caso, entonces todas las fórmulas del formalismo 5£ serán dedueibles a partir de F.

Cuando se descubre una contradicción en una teoría de la matemática o de alguna ciencia empírica, inmediatamente es rechazada la teoría, pues carece de todo valor, ya que cualquier cosa se sigue de ella, tanto una afirmación cualquiera como su negación.

Para definir la contradicción de un conjunto de fórmulas eligiremos precisamente la propiedad de que cualquier fórmula sea deducible de él.

7.1. Definición:

Un conjunto F de fórmulas de Jz? es contradictorio en S£ si y sólo si cada fórmula de S£ es deducible de F.

Un conjunto F de fórmulas de Jz? es consistente en 2? si y sólo si Y no es contradictorio en Jz?.

Es decir, un conjunto F de fórmulas de Jz? es consistente en S£ si y sólo si hay alguna fórmula de Jz? que no es deducible de F.

Una fórmula a de Jz? es contradictoria (resp., consistente) en Jz? si y sólo si jaj es contradictorio (resp., consistente) en ü?.

7.2. Teorema:

a) Si T es consistente en 2? y A C F, entonces A es consistente en [£ .h) Si F es contradictorio en 2? y F C A, entonces A es contradictorio

en S£.

Prueba de a): Sea Y consistente. Si A fuese contradictorio en S€. entonces toda fórmula de S£ sería deducible a partir de A y, por 2.9, a) a partir

de F, con lo que F sería contradictorio. Pero F es consistente y, por tanto, también A.

De igual modo se prueba b).

7.3. Teorema: F e s c o n t r a d ic t o r io e n Jz? si y s ó lo s i h a y u n a f ó r m u la a

d e t a l q u e T \-<e (a a a).

Prueba: F sea contradictorio en í £ . Entonces, cualquier fórmula de .'£ es deducible a partir de F. En especial, la fórmula de Jz? (a a —• a) es deducible de T: T (a a ~ i a).

Sea r i— ¡s (a a ■ a). Entonces, cualquier fórmula /3 de i í es deducible a partir de F. En efecto,

1 r p2 ? (a. a “ i a)

a

—i a

p u e s r i— z ( « a u )

EC 2 EC 2

es una deducción en Jzf de /3 a partir de F.

7.4. Teorema: Sea a una sentencia de Jz?.

(1 ) a es contradictoria en üf si y sólo si i— # a.(2 ) a es contradictoria en Jz? si y sólo si i— \ a.Prueba de (1): Sea a una sentencia contradictoria en ¡£ . Entonces,

I Gf |— ccU J—i oej a

<l> l—se a por 5.31—sg a

Sea a. Entonces a es contradictoria, pues para cualquier fórmula /3 de ¡£ , —i <x i—s /3- En efecto,

1 ? /32 f a pues i—s a

2 -)- n “ ict premisa

es una deducción en ¡£ de /3 a partir de a, en la cual la única premisa introducida ha sido —i a.

Con lo que (1) queda probado. De igual modo se prueba (2).¿Es necesaria la restricción a sentencias en la formulación del teorema

7.4? En la dirección de izquierda a derecha, sí, pues la prueba se basa en

CONSISTENCIA Y CONTRADICCION 99

el teorema 5.3, que a su vez está restringido a sentencias. En la otra dirección, no, pues la prueba no hace uso para nada del hecho de que a sea una sentencia. Es decir, para cualquier fórmula a : si i—& a, entonces —i a es contradictoria en Jz?. Y para cualquier fórmula m a: si i— u , entonces a es contradictoria en Jz?.

7.5. Dado un formalismo =S? al que posiblemente no pertenece la constante individual c, designemos mediante “££ U \c\” al formalismo que resulta de añadir a ££ la constante c.

Teorema:

Si c no está en a

1— J 5 ? U { C } 5 ”, a

entonces: a

Con ayuda de este teorema, que aquí no probamos, podemos pasar a demostrar el siguiente teorema 7.6.

7.6. Teorema: Si T U jVx aj es consistente en y c no está en f ü ¡Vx aj entonces T U {V xa} U {5 ja } es consistente en Jz? Ujcj.

Prueba: T U (Vx a} sea consistente en =S?; c no esté en P U (Vx a}. Probaremos el teorema indirectamente. Supongamos que P U ¡Vxaj U {5® a} fuera contradictorio en Jz? U {c}. Entonces,P U j Vx aj U j5®,aj \-xutc)~i aT U {Vx a} 1- - 1 5^* por 5.3.T U {Vx a} 1— euici 5® 5 “ m a; tí no esté en T U {Vx a}

pues 5® 5 “ m a = 5 ® m a = — 1 5®. a

1-vuia T i a . . . a 7 » a V x a —»5® 5 “ ~ 1 a p o r 5 .2

l sí'j ¡ (*} 5® (7 , a . . . A 7 „ A V x a —» 5 “ — l a )

pues u no está en 7 ,, . . . , 7 «, Vxa 1— i- ( 7 1 A . . . a 7 „ A Vx a —>5 “ ■ — 1 a) por 7.5r U jVxaj »— —1 5« a pues 5 “- i a = - i 5 “ a

Sea /3 una fórmula de ¿z? en la que no esté u. Entonces,T U j Vx aj 1 - ^ - ( / 3 A /3). En efecto, 1 t (/3 a 1 /3)

2 V xa Premisa3 5£ «. EP, 24 f ~1 5" a Puesto que

T U j Vx aj 1— ^ — 1 5 “ a

Luego, por 7.3, F U j Vx a\ es contradictorio en contra la hipótesis. Luego F U {Vx aj U j Bj j a j es consistente en S6 U j c j .

7.7. Teorema: Si el conjunto F de fórmulas de ü? es consistente eny c no pertenece a Jz?, entonces T U je = >.y y = t/j es consistente en en Ü? U jcj.

Prueba: Sea F consistente en Jzf y c <? Jzf. Prueba indirecta. Supongamos que F U je = tí/ y ~y\ es contradictorio en S£ U jcj.

F U je = iy y = y\ y-zvíc) ~i c = i y y = yr - t c — iy y ~ y por 5.3

Por 5.2, hay y i , ..., e T, tales que

y -xu ic ) (Ti A ... a T ic = I.y y - y )

u no esté en Ti, • ••, T»•t-ifuíc} (Ti A ... A T« 5 “-i M = !!/ =

pues 5 « - i u■ = tí/ y — y 3= - i c = ty t/ = y y-s uto 5 ; ( ti a ... A - T n ^ - i ü - ty t/ = y)pues 5° (ti a . . .A ^ n - * - iu = i y y = y) = ('¡l A ...A - {n ~ *S l~ iu = t y y = y )

y-sr (ti A ... A f . - ^ - i u = ly y = i/) por 7.5i—js» (Ti a ... A t» -> Att —i tí — y = y) por 5.5r Aíí —i u = iy y = yi-a. —i Au —i u = iy y = y-

En efecto, 1 2345

Au —iu = iy y = y —i —i A ti —\u — iy y = y

Au —i u = iy y = y - n y y = y = ty y = y

iy y = y —, iy y = y

DN, 2 EG, 3 I

F y-x —i A u —i u = iy y = y por 2.9, c)T h » A u —iu = tt/ y ~ y A u —tu = ity y = y por IC

Luego r sería contradictorio en jz?, por 7.3, contra la hipótesis. Por consiguiente, r U je = ly y = y\ es consistente e n ¿ ? U jcj.

q.e.d.

II.8. Consistencia máxima y ejemplificación

8.1. Definición: Sea F un conjunto de sentencias de jz?.T es máximamente consistente si y sólo si F es consistente y para cual

quier sentencia a de Jzf: si a í F, entonces Y U jaj es contradictorio.

CONSISTENCIA Y MAXIMA EJEMPLIFICACION 101

r es ejemplificado si y sólo si para cualquier sentencia Va a de ¡£\ si V a a e T, entonces hay un designador t de tal que 5* a e T.

8.2. Teorema: Si T es un conjunto máximamente consistente de sentencias de ,5?, entonces para cualesquiera sentencias a y j3 de =£?:

(1) Si r i— a, entonces a e F(2) Si i— a, entonces a e T(3) a e r si y sólo si a <$. T(4) (a a j3) e r syss a e T y /3 e F(5) (a v /3) e T syss a e T o j3 e F(6) (a -^/3) e T syss si a e T, entonces ¡3 € T(7) ( a * * / 3 ) € r syss: a e T syss ¿3 e T

Prueba de 8.2: Sea T un conjunto máximamente consistente de sentencias de jz?.

Prueba de (1): Sea T i - a.

Supongamos que a $ T.

r U jaj es contradictorio F U {«j i— «

T i— (a A > o¡)

pues T es máximamente consistente

por 5.3

Entonces, T sería contradictorio, por 7.3, contra la hipótesis. Luegoa e r.

Prueba de (2): Si i— a, entonces T i— o¡, por 2.9, c). Luego a € T, por (1).

Prueba de (3): Sea ~i a e T.

Si a € F, T sería contradictorio, contra la hipótesis. Luego a $ T.Sea ct í r .Si —i« i T, entonces T U j—i aj es contradictorio, pues T es máximamen

te consistenter u {—iotj i- <x

” T y - a por 5.3” a e T por (1 )

en contradicción con <x i F. Luego ~i ae T.

Prueba de (4): Sea (a a /3) e T.

(o¡A/3)y-<x y (<x a /3) y-¡3T i — a y r I— ¡3 pues (a a ,8) e Ta e T y /3 e T por (1)

102 s in t a x is : u n c á l c u l o d e d u c t iv o

Sea a g F y /3 e T»,i3h(«A|3)

T i— (a a /3) pues a, /3 e T(a a /3) e F por (1)

De igual modo se prueban (5), (6) y (7). q.e.d.

8.3. Teorema: Si V es un conjunto máximamente consistente y ejemplificado de sentencias de 5£ y a es una fórmula de í£ en la cual a lo sumo la variable x está libre, entonces:

(1) V.T a e T syss hay un designador t de Jzf, tal que(2) A x a e T syss para cada designador t de S£\ 5 J , a e r

Prueba de 8.3: 1’ sea un conjunto máximamente consistente y ejemplificado de sentencias de ¡ £ .

Prueba de (1): Sea V.r a e T.Hay un designador t de ,5?, tal que 5'. a e P, pues P es un conjunto

ejemplificado.

Sea 5 ‘. a e T , para algún designador t de í £ .5* a i— Vx a por IP

T i— V x a pues 5* x g FV x a e T por 8.2, (1), pues P es máximamente consistente

Prueba de (2): Sea Ax a e T.

Ax a i— 5* a para cada designador t de jz?, por EGT i— 5 ‘ a ” ” ” ” pues Ax a e T

5 ‘ a e T ” ” ” ” por 8.2, (1)Sea 5*. a e T pafa cada designador t de 5£.

No hay ningún designador t de ,SÚ, tal que 5J. ot ? P—i 5* a e T por 8.2 (3) 5*. _i a e T

Vx —i a í r —i Vx —i a e r —i Vx n a i - Ax a

T i— Ax a Ax a e r

por 8.3 (1) por 8.2. (3) por NPpues —i Vx —i a e T por 8.2 (1)

q.e.d.

8.4. Teorema: Para cada conjunto consistente T de sentencias de «§? sin descriptores hay un conjunto P ° máximamente consistente y ejempli-

CONSISTENCIA Y MAXIMA EJEMPLIFICARON 103

ficado de sentencias sin descriptores de Jzf U £ , donde 7? es una clase numerable y disjunta con Jzf de constantes individuales, tal que T C T '.

Prueba de 8.4: P sea un conjunto consistente de sentencias sin descriptores de Jzf.

7? sea un conjunto infinito numerable de constantes individuales, tal que Jz? C rfo = 4>. Las constantes de £ estén numeradas.

Partimos de una enumeración a0, cti, a2, a 3, ..., de todas las sentencias sin descriptores del lenguaje Jzf U £ . (Una tal enumeración existe, pues el conjunto de las sentencias sin descriptores, que es un subconjunto del conjunto de las fórmulas, de un lenguaje es numerable.)

Por inducción aritmética definimos en función de P una sucesión T_,- de conjuntos de sentencias de la siguiente manera:

r 0 = r

! r ¡ , si r 3 U ¡0 ,-j es contradictorio( r , U j <x¡\ es consistente

^ | <Xj no es una particularizacióní T,- U jctjj es consistente

P; U N U ¡5®«;!, si ) ,1 c es la constante de mínimo menee' de 7 ? , que no está en r_,- U \ocj\.

A la unión de todos los conjuntos que forman esta sucesión le llamaremos r * .

r * = u r ,}=0

a) T C r * .

En efecto, T = r 0 y T0 C U T; = r * . Luego T C T*.i-o

h) Para cada /, T, es consistente.Prueba por inducción aritmética sobre /.To es por hipótesis consistente, ya que I’,, = P.

Supongamos que P_¡ es consistente. Entonces, también lo es T_,+1. En efecto, distingamos los tres casos de la definición de r_,+J. En el primer caso, ., — Pj. Luego Ty+i es consistente, pues Py lo era. En el segundo caso, r_;+1 = Ty U jayj, y Fy U jayj es por construcción consistente. Luego Pj.j es consistente. En el tercer caso, r í+1 = U jV xa'j U j5jj,a'j, I’y U jV xa'j es por construcción consistente y c no está en P, U jVx a'j. Luego Ty+i es consistente, por 7.6.

Así, pues, para cada j, Py es consistente.c) r e es consistente.Prueba indirecta. Si T® fuese contradictorio, entonces habría por 7.3 una

sentencia <x de U ‘g', tal que r® i— (a a —i a). Por 2.8, habría n sentencias Ti, . . . , 7 » e r 4, tales que

Tu T« i— (a a "t ce)I\ sea el r 3 de mínimo subíndice, tal que Ti, . . . , j n e r 3.

P* i— (a a i a)r k sería contradictorio, por 7.3, contra lo que hemos probado en b). Luego P® es consistente.

d) Sea a una sentencia de <2? U 9?. Si a i r®, entonces T® U jaj es contradictorio.

Sea a £ T*.ce es una sentencia de 5S U ís . Por tanto, a ocupará un lugar en la suce

sión dé que partimos. Sea a = a¡.ce¡ $ r®<x¡ i T)+1, pues si no, <xj e r * .

Vj U ¡ <xj\ es contradictorio, pues si no, ce¡ e r í+i .r ° U ja,-} es contradictorio, por 7.2, b), pues Pj U ja;-¡ C P* U \a¡\ r * U ja¡ es contradictorio, pues a¡ = a.

e) r® es máximamente consistente.Se sigue de c) y d), por definición.

f) r * es ejemplificado.Sea «: = Vx a una sentencia de =§? U fé.Sea Vx a e T®.Tj U jV xaj es consistente, por 7.2, a), pues r ;- U j Vx aj C T* y T* es

consistente.Vx ae r m , por construcción de T¡+1, en el tercer caso. Para algún c,

5" a e r í+i, por construcción de r ;+i, en el tercer caso de la definición.Luego hay un designador t de S£ U ^ (a saber, t = c), tal que 5* a e F3+i ,

y, por tanto, tal que S^oteT®, pues P3+i C T®.Así, pues, P* es ejemplificado.En r® no hay descriptores, pues no los había en r o ni se han introducido

en la sucesión de los Pj. Con esto y con a), e) y f) queda probado que T* es un conjunto máximamente consistente y ejemplificado de sentencias sin descriptores de ,5? U c€ , donde í? es una clase numerable y disjunta con de constantes individuales, tal que T C T®.

PARTE TERCERA

S E M A N T I C A

III.1. Interpretaciones

1.0. El alfabeto de los formalismos está constituido por un conjunto ele signos. Colocando unos signos detrás de otros formamos filas de signos. Y de entre las filas de signos elegimos algunas —los términos y las fórmulas— y les prestamos especial atención. Con ayuda de las fórmulas formamos líneas. A determinadas sucesiones de líneas les llamamos semideducciones, y a determinadas semideducciones, deducciones. Así establecemos la relación de deducibilidad entre fórmulas. Hasta aquí todo ha sido, pues, como un juego — más o menos complicado— con figuras gráficas.

Ahora, gracias a la introducción de las interpretaciones, nuestros formalismos se convertirán en lenguajes formales, nuestro juego con figuras adquirirá una dimensión significativa o, al menos, referencial.

Interpretar un formalismo consiste principalmente en indicar un universo o conjunto no vacío de individuos, al que se referirán nuestras variables, y en asignar a cada constante individual del formalismo un individuo del universo, a cada functor n-ádico del formalismo una función n-ádica en el universo, y a cada relator n-ádico del formalismo una relación n-ádica en el universo. La interpretación de un formalismo consta, pues, fundamentalmente, de dos partes: la indicación de un universo al que se refieran las variables y la asignación de significados o referencias adecuadas a los signos peculiares del formalismo.

Además, habrá que elegir en cada caso un individuo cualquiera del universo como “cabeza de turco” al que atribuir todas las descripciones impropias que propiamente no designarían nada, a fin de que cada designador del formalismo designe efectivamente un individuo del universo.

Con estos tres elementos (determinación de un universo, asignación de referencias a los signos peculiares y elección arbitraria de un individuo

108 SEMANTICA

como referencia común de todas las descripciones impropias) queda definida una interpretación. Por conveniencias técnicas añadiremos a la interpretación una asignación de un individuo del universo a cada variable.

El concepto de interpretación es el concepto básico de la semántica lógica.

1.1. Definición:

17 es una interpretación del formalismo i ? si y sólo si 17 — <°U, 9 7 , a>, donde

1. ° 91 es una clase no vacía, es decir, 91 7=- </>.2. ° W€ es una aplicación o asignación tal, que a cada constante indivi

dual de Ü? le asigna un individuo de 91, a cada functor n-ádico de ¡£ le asigna una función n-ádica en 91, a cada relator n-ádico de ! £ le asigna una relación n-ádica en 91, y a cada variable le asigna un individuo de 91.

3. ° a es un individuo de 91, a e 91.

1.2. De ahora en adelante, para referirnos al individuo de 91 que laaplicación asigna a una constante a de o a una variable x, en vez de escribir “W€(á}” o “W (x)” escribiremos “17 (a)” e “17ix)”. Igualmente, en vez de o “ffl(P)”, escribiremos “17(f)” e “17(P)”. No hay confusiónposible.

1.3. Si ■ 17 es una interpretación del formalismo Jz?, mediante (donde x $ 9 / ) designaremos la interpretación que coincide con 17 absolutamente en todo, con la posible excepción del individuo que asigna a la variable x. 17* asigna a la variable x el individuo x en cualquier caso, y cualquiera que sea la asignación que 17 le atribuya. Es decir, para toda variable z:

J 17(z), si z # x j x , si z = x

Con “!7 xjy” designaremos a

Con' “17***” designaremos a ( ( .7 ^ )5 etc.

1.4. De 1.3 se desprende que:

(1) Si x # z, entonces 17xz 177X

(2) Para todo x: J"*7 ~ ,7 7-

DENOTACIÓN Y SATISFACCION 109

III.2. Denotación y satisfacción

2.1. Dada una interpretación 7 de ¡£ , cada término de «2? denota en 7 un elemento del universo °ll de 7 . Para indicar que t denota x en 7 , escribiremos “7 (t) — x ”.

Dada una interpretación 7 de 7 , cada fórmula de 7 es satisfecha o no satisfecha por 7 ■ Para indicar que 7 satisface <x, escribiremos, abreviadamente, “7 sat a ’.

2.2. Definición por inducción semiótica simultánea de la denotación de un término de 7 en 7 y de la satisfacción de una fórmula de 7 por 7 , donde 7 e s una interpretación cualquiera de 7 . Sea 3 ' — <pll, 7 € , a>.

7 (x ) = 7 (x )7 (a) = 7 (a)7 (fnh , ..., tn) = 7 (fn) 7 ( h ) , ..., 7 ( Q7 s a t Pnti,

(e n e s p e c ia l , 7 s a t #i = t2 7 s a t ~ i a 7 s a t (a a /3) 7 s a t (a v /3) 7 s a t (a - » /3) 7 s a t ( a -«•/3) 7 s a t Ax a 7 s a t Vx <x

tn syss < 7 {tx) , ..., 7(t„)y e 7 (P”) syss 7 (#0 = 7 (t2)) syss no 7 sat a syss 7 sat a y 7 sat /3 syss 7 sat a o 7 sa t./3 syss (si 7 sat a, entonces .7 sat /3) syss ( 7 sat a syss 7 sat /3) syss para todo x e 611:7* sat a syss para algún x e 91-.7^ sat a

!el único x e °ü, tal que 7 * sat os, si hay un tal xy sólo uno

a , si no2.3. La definición de satisfacción es al mismo tiempo una definición

precisa del concepto semántico de verdad en los lenguajes formales. Una sentencia a es verdadera en una interpretación 7 si y sólo si 7 satisface a.

2.4. Teorema;

Si x no está libre en t, entonces 7 * (t ) = 7 (i)

Si x no está libre en a: 7 x sat os svss 7 sat aX

110 SEMANTICA

2.5. Demostración de 2.4 por inducción semiótica simultánea. En cada paso suponemos que x no está libre en el término o fórmula considerado.

.7 *(2 ) = J (z) [pues z # x, ya que x no está libre en z] j\ (a ) = J ( a )

= -7 * (f ) J f r ) , ...,= J (/") J ( t i ) , . . . , J ( t n) [supuesto inductivo] = J l f nty,

J * sat Pntx, ..., t„ syss ..., .7*(í„)> e .7*(P")syss C7(A), e J7(P") syss .7 sat Pntu . . . , t n

[sup. induct.]

(en especial, J '* sat A = f2 syss . 7 ^ ) = -7*(f2)syss J (#1) = .7 (#2) syss ,7 sat = í2)

[sup. induct.]

.7 X sa t—1 aX

syss no 7 * sat asyss no .7 sat a syss .7 sat —1 a

[sup. induct.]

J * sat (a a 0) syss .7 * sat a y .7 * sat /3

De igual modo:

syss J sat a y 7 sat /3 syss J sat (a a /3)

[sup. induct.]

.7 * sat (a v /3) syss J sat (a v./3)•7* sat (a -»/3) syss J sat (a -» /3).7 * sat (a <-> y8) syss J sat (a <-»/3)

Para mostrar que el teorema vale para las generalizaciones Az a, distinguiremos dos casos posibles: que z ^ i y que z = x.

a) sea z=k x

sat A z a syss para todo z e 1?/: J sat asyss ” ” ” J “ sat a [por 1.4.(1)]syss ” ” ” J * sat a [sup. induct.]syss .7 sat A z a

b) sea z = xJ * sat Az a syss para todo z z°U\ J ** sat a

syss ” ” ” J7* sat asyss CT sat Az a

[por 1.4.(2)]

INTERPRETACIÓN Y SUSTITUCION 1 1 1

De igual modo:.7 * sat V% a syss J sat Vz a

Finalmente veamos que el teorema también vale para las descripciones.

a) Sea z # * y haya un único z con .7** sat a.

■7x(¡z a) = el único z, tal que sat a= ” , tal que J “ sat a [por 1.4.(1)]= ” , tal que J * sat a [sup. induct.]= J (tz <x)

b) Sea z = x y haya un único z con .7** sat a ■7x(t;Z a) — el único z, tal que .7*5 sat a

= ” , tal que J * sat a [por 1.4.(2)]= J7(t% a)

c) Sea 2 # r y n o haya un único z tal que J'™ sat a.

J H íz a) = a

No hay un único z, tal que .7** sat a

, tal que .7** sat a [por 1.4.(1)], tal que J * sat a [su. induct.]

7 (iz a) = a = 7 x(tz a)

d) Sea * = t y no haya un único z tal que .7 “ sat a.7 x(iz a) = aNo hay un único z, tal que ¡7™ sat <x

, tal que J zz sat a [por 1.4.(2)]\7(tz a) = a = ,7 x(iz a)

q.e.d.

III.3. Interpretación y sustitución

3.1. Teorema:

Para todo término t0: .7;[[(í,(fo) = .7(5[to)Para toda fórmula a: sat a syss J sat S*a

3.2. Demostración de 3.1 por inducción aritmética sobre la longitud de las expresiones.

8 . ----LÓGICA DE P R IM E R ORDEN

112 SEMÁNTICA

El teorema vale para las expresiones de longitud 1:Sea f0 = z. Distinguiremos dos casos posibles: que z ^ r y que z = x.a) Sea z # x.

b) Sea z = x.y'«>(z) = y (t ) = J ( S * z )Sea t0 = a.J ^ ( a ) = J ( a ) = J\ S\ a)

El teorema vale para las expresiones de longitud m, suponiendo que valga para las expresiones de longitud menor que m (supuesto inductivo):

y ^ ( f nh , ..., tn) = y ^ > ( f ) y™ >(*i),— ^ ( / " ) * 7 ( 5 ^ t i ) , C T ( 5 * t „ ) [ s u p . i n d u c e ]

= . 7 ( f 5 ^ . . . 5 > )= .7 (5 ‘ f t i , . . . , t ft)

sat pntl, . . . , t n syss < ^ (í> ( f i ) , . . . , ^ (<)(íB)> e y ( P n)syss KJT(5^fi),..., y (5‘ tn)> e y (P*) [sup. ¡nduc syss y sat P "5 *fi ,..., 5* f„ syss J7" sat 5 *P“fi, ..., t„

(en especial, sat ti = t2 syss J ^ (í' (ti) = y ^ V ffo)syss .T (5* i.) = .7 (¾ í2) syss .7 sat 5* (ti = t2))

[ s u p . i n d u c t . ]

j-j(t) sat syss no y J(t) sat « syss no y sat 5 , a syss y sat —i 5* <z

r' ‘ i a

[ s u p . i n d u c t . ]

svss J sat 5*

saf (a A y3) syss sat a y y * w sat /3

syss J sat 5^« y .7 sat 5*j8 [sup. Jnduct,syss J sat (5* a a 5(^)syss y sat 5* (a a /3)

Del mismo modo se prueba:«7^(í) sat (a v /3) syss .7 sat 5* (a v /3)y ^ (t> sat (« -* /3 ) syss .7 sat 5* (« - » /3)

sat (a -o-/3) syss J7 sat 5* (a <->/3)

INTERPRETACION Y SUSTITUCION 113

Para mostrar que el teorema vale para las generalizaciones Az a, distinguiremos los tres casos posibles: l.°: que x no esté libre en Az a; 2.°: que x sí esté libre en Az a, pero z no esté en t; 3.°: que x sí esté libre en Az a y z esté en t. En cada uno de los tres casos probamos lo que afirma el teorema:

J rJr(t> sat Az a syss CT sat 5* Az<x

syss

syss

1. " caso: x no está libre en A za.

sat Az a syss J sat Az a [por 2.4]syss CT sat 5* Az a [pues 5^ Azi a = Az a]

2. ° caso: x está libre en As a; z no está en t,

sat A s a syss para todo sat a

: sat a [por 1.4.1, ya quex # z]

: sat «[pues =por 2.4, ya que s no está en f]

syss ” ” : jT% sat 5*, a [sup. induct.]

syss J sat A s5 *«

syss J sat 5* As a

r caso: x está libre en As a; z está en t; v no esté en Az a ni en t.

sat A z a syss para- todo z z°ll\ sat a

syss ” ” : sat aJ X VZ

syss

syss

syss

syss

[por 2.4, ya que o no está en a]

^ 1 sat «

[pues J r^(t^(v) = z]

sat 5" a [sup. induct.]j z j h ) sat 5 » a

V X Z

[por 1.4.1, pues u # z]

sat 5 V aV X z

[pues J l { t ) = J ( t ) , por 2.4, ya que v no está en f]

114 semántica

syss para todo z€.°ll: 7 zr sat 5 * 5 ” a [sup. induct.]

syss 7 sat Av 5[,5” a syss 7 sat 5* A za

Del mismo modo se prueba:

7 x (t> sat Vz a syss 7 sat 5 ‘ V za

Para mostrar que el teorema vale para las descripciones iza, distinguiremos los tres casos posibles: l.° que x no esté libre en iza; 2.°: que x sí esté libre en iz a, pero z no esté en t (en cuyo caso distinguiremos las dos posibilidades de que haya o no haya en el universo de la interpretación 7 un único individuo z, tal que 7 x (t>zz sat a); 3.°: que x esté libre en iza y z esté en t (en cuyo caso volveremos a distinguir las dos posibilidades indicadas). En cada uno de estos casos probamos lo que afirma el teorema:

7 Jx w (iz a) = J (5* iz a)

1. " caso: x no está libre en iz a.

7 x (t) (tz a) = J (tz a) [por 2.4]

[pues iz a = 5* iz a, ya — 7 (5* iz a) que x no está libre en

tz a]2. a caso: * está libre en iz a; z no está en t.

a) Hay un único z, tal que 7 ' {t,z: sat a.

7 Jx {t) (iz a) = el único z, tal que 7 ^ .(t>l sat a

= ” , tal que 7 ^ Tx{t) sat a [por 1.4.1, pues z ^ r ]= ” , tal que 7 Z sat 5* a [sup. induct.]

= y ( iz 5 > )

= 7 ( ¥ t z a )

h) No hay un único z, tal que 7 x (t,z sat a. 7 - 7xw (tz a) = aNo hay un único z, tal que 7 x (t>z sat a

, tal que 7 zfx{t) sat a

tal que 7 Z^ sat a

tal que 7 Z sat 5* aT. Z X

7 (iz 5* a) — a7 (5‘ tz a) = a = .7^<‘> (tz a)

[por 1.4.1, pues z # x]

[pues 7 zx (t) = 7 (t), ya que z no está en t] [sup. induct.]

SATISFACIBILIDAD, VALIDEZ Y CONSECUENCIA 115

3.c‘ caso: x está libre en iz a; z está en-t; v no esté en iz ¡x ni en t.a) Hay un único z, tal que 7 y<t)* sat a-

7 J (í) '.z a )= e l único z, tal que 7 y{t)* sat a = ” , tal que sat a

[por 2.4, pues v no está en a]

= ” tal que J7'-r (í>z J x ¡A ' Sat aa? v z

[pues 7 x (t)*(v) = z]= ” , tal que 7 Jx t)7'v sat 5® a [sup. induct.]

= ” , tal que 7 iy(t> sat 5" a [por 1.4.1, ya quex ^ v ]

7 z (A

= ” , tal que 7 \ x *' ' sat 5® a[pues y*(t) ~ y (t) ya que v no está en t]

= ” , tal que 7 * sat 5 45®a [sup. induct.]

= 7 (tu 5* 5® «)

= y ( 5 ‘ tz a)

b) No hay un único z, tal que 7 y(t)* sat a.7 y(t> (iz a) = a.

No hay un único z, tal que 7 yft>l sat a.

(como arribaren a))

No hay un único z, tal que y * sat 5 .5®, a.

.7 (tu 5 (5® a) = ay (5* tz a) = a = ^7yxw (tz <*)q.e.d.

III.4. Satisfacibilidad, validez y consecuencia

4.1. Una interpretación 7 de <S? satisface un conjunto 1' de fórmulas de í£ syss 7 satisface cada fórmula de I'.

Toda interpretación satisface al conjunto vacío 4> de fórmulas de =§?. En efecto:

116 SEMANTICA

7 sat 4> syss para toda a: si a e f entonces .7 sat a, y, puesto que para todo a, resulta que .7 sat <f>.

4.2. Definiciones: Una fórmula a de 57 es satisfacible si y sólo si hay al menos una interpretación de 57 que la satisface.

Una fórmula a es insatisfacible si y sólo si a no es satisfacible.Un conjunto T de fórmulas de 57 es satisfacible si y sólo si hay al menos

una interpretación de 57 que satisface T.Un conjunto T de fórmulas es insatisfacible si y sólo si T no es satis

facible.Una fórmula a de 57 es lógicamente válida si y sólo si toda interpre

tación de 57 satisface a.Una fórmula a de 57 es una consecuencia en 57 de un conjunto F de

fórmulas de 57 si y sólo si toda interpretación de 57 que satisface T satisface también a.

En lo sucesivo, y cuando no sea imprescindible, dejaremos de lado la alusión a 57.

4.3. Abreviaturas:

‘T \=¡r a” sea una abreviatura para “ores una consecuencia en 57 de T”.‘T i= a” sea una abreviatura “oc es una consecuencia de T”.“a t= /3” sea una abreviatura para “ ¡aj i= /3”.“a1 ;..., a„ i= /3” sea una abreviatura para “ ja1 ; anj i= /3”.“i= a” sea una abreviatura para “4> t= a”.

4.4. Teoremas:

a) t= a syss a es lógicamente válida.Prueba: i= a syss <f> \= a

syss para toda 7 : si 7 sat 4>, entonces 7 sat asyss para toda 7 : 7 sat a (por 4.1)syss a es lógicamente válida.

b) r t= a syss T U j- 1 aj es insatisfacible.

Prueba: T t= a syss para toda 7 : si 7 sat T, ent.. 7 sat a

syss ” ” : si 7 no sat a, 7 no sat Vsyss ” ” : si J7" sat —i a, 7 no sat Tsyss no hay ninguna 7 que satisfaga n a y T. syss F U j—i aj es insatisfacible.

INDEPENDENCIA 117

c) i= a si y sólo si —i ot es insatisfacible.Se sigue de h), para r = <¡fr.

d) o¡ es lógicamente válida si y sólo si —i a es insatisfacible.Se sigue de a) y c).

é) r es insatisfacible si y sólo si para alguna fórmula a del mismo lenguaje: r t= (* a n ¢),

Prueba:r t= (« a i a) syss para toda 7 : si 7 sat T, ent. 7 sat (s a d í )

syss ” ” : si 7 sat T, ent 7 sat a y 7 no sat «syss ” ” : 7 no sat Fsyss T es insatisfacible.

4.5. Teorema: Si todos los signos peculiares del formalismo 7 i lo son también de JS?2, ^ es un conjunto de fórmulas de 7 \ y T2 es un conjunto de fórmulas de 7-¿, Fj C T2 y r 2 es satisfacible en 7-¡ sobre un universo °>I, entonces Ti es satisfacible en sobre el mismo universo °tl.

Prueba: Sean todos los signos de 7 -l también signos de 7 1, F x sea un conjunto de fórmulas de 7 \ y T2 de JS?2, sea Fi C F2 y sea T2 satisfacible en 7 z sobre un universo °U.

Hay una interpretación 7 sobre °IL de 7 2, tal que:Para toda a e T2: 7 sat aPara toda a e T !: 7 sat a, pues Ti C r 2.Sea 7 ' — <M, a>, donde es la aplicación WC de 7 , restringida

a los signos de 7 \ . Por tanto, 7 ' interpreta todos los signos peculiares de 7 1 (que también lo son de 7 2} de igual modo que 7 .

Puesto que 7 e 7 ' sólo se diferencian respecto a signos peculiares que no están en 7 u 7 e 7 ' interpretan del mismo modo las fórmulas de 7 \ . Por tanto, para toda a e 7 ' sat a. Es decir, 7 ' sat

Ahora bien, 7 ’ es por definición una interpretación de 7 \ sobre °U-. Luego Ti es satisfacible en 7 \ sobre el mismo universo °U sobre el que T2 era satisfacible en 7-¿-

q.e.d.

III.5. Independencia

5.1. Si una sentencia a de 7 no es una consecuencia de un conjunto F de sentencias de 7 , decimos que « es independiente de F. Por tanto, dada una sentencia cualquiera a y un conjunto cualquiera F de sentencias, siempre ocurre que a es una consecuencia de T o que a es independiente de F.

118 SEMÁNTICA

5 .2 . Definición: a e s in d e p e n d i e n t e d e T si y s ó lo si a n o e s u n a c o n

s e c u e n c i a d e F .

Si a fuese una consecuencia de F, todas las interpretaciones que satisfaciesen T satisfarían también a. Ál no ser a una consecuencia de F, no será el caso que todas las interpretaciones que satisfacen F satisfagan también a, es decir, habrá alguna interpretación que satisface F, pero no «. Por tanto, otra manera de formular la definición sería: a es independiente de F si y sólo si hay una interpretación 7 de =2?, tal que .7 satisface F, pero 7 no satisface a.

Para probar que una sentencia a es independiente de un conjunto F de sentencias hay que probar que a no es una consecuencia de F. Para ello hay que ofrecer una interpretación 7 , tal que 7 satisface F, pero no a. No hace falta especificar la interpretación 7 en todos sus detalles. Basta con indicar cuál es el universo °il de la interpretación elegida 7 y cómo interpreta 7 los signos peculiares de S£ que aparecen en F y a. (Si aparecen descriptores en T o en a, hay que indicar también cuál es el individuo a de °ll al que habrán de referirse las descripciones impropias.)

5.3. En la conversación ordinaria, en el comercio, en la política, en los tribunales, etc. se usa con frecuencia de la argumentación. En una argumentación sacamos una conclusión a partir de una serie de datos, consideraciones o premisas.

Una argumentación es correcta, válida o concluyente si y sólo si su conclusión es una consecuencia de sus premisas; incorrecta o inválida, si su conclusión es independiente de sus premisas.

Para controlar una argumentación enunciada en el lenguaje ordinario hemos de empezar por formalizarla, es decir, por simbolizar cada una de sus premisas y su conclusión’ én un formalismo lógico. Probar la incorrección o invalidez de la argumentación consistirá entonces en probar la independencia de la fórmula-conclusión respecto al conjunto de las fóripulas-premisas.

5.4. A veces hablamos no de la independencia de una fórmula o sentencia respecto a un conjunto de sentencias, sino de la independencia de un conjunto de sentencias entre sí. Así se dice que determinados sistemas de axiomas son independientes, que Hilbert prohó la independencia de su axiomatización de la geometría euclídea, etc.

Al decir que un conjunto de sentencias es independiente (en este segundo sentido) queremos decir que cada sentencia de este conjunto es independiente (en el primer sentido) de las demás.

5 .5 . Definición: F es i n d e p e n d i e n t e si y s ó lo s i p a r a c a d a S e n te n c ia a e T :

<x es in d e p e n d i e n t e d e T — j ctj.

EJERCICIOS DE PRUEBA DE INDEPENDENCIA 119

En otras palabras: T es independiente si y sólo si cada sentencia de í es independiente de las demás; si y sólo si ninguna sentencia de 1’ es una consecuencia de las demás.

Para probar que un conjunto finito F = ja1; a„j de n sentencias de jz? es independiente hay que mostrar que ninguno de sus elementos es una consecuencia de los demás. Para ello hay que ofrecer n interpretaciones J i , . . . , JT„., tales que para cada \ (1 < -/< = »), satisface F — ja,-j, pero y i no satisface a¡. Bastará con indicar el universo, la interpretación de los signos peculiares de y la interpretación de las descripciones impropias (caso de que aparezcan descriptores en P; si no, no hace falta) para cada y ¡ (1 < ! j <C n).

JII.6. Ejercicios de prueba de independencia

Así como para aprender a deducir no basta con conocer la definición de la deducción, sino que es necesario ejercitarse en el arte de hacer deducciones, así también no basta con haber leído la definición de la independencia para saber probar la independencia de una sentencia respecto a un conjunto de sentencias o la independencia de las sentencias de un conjunto entre sí.

Si sospechamos que una determinada argumentación o una presunta prueba es válida, la formalizamos y tratamos de obtener una deducción de su conclusión a partir de sus premisas. Si, por el contrario, sospechamos que es incorrecta o inválida, hemos de tratar de obtener una prueba de independencia de su conclusión respecto a sus premisas.

A continuación ofrecemos al lector unos cuantos ejercicios de prueba de independencia. Es conveniente que el lector trate de hacerlos por su cuenta y sólo mire las pruebas de independencia correspondientes aquí presentadas después de haber hecho él mismo los ejercicios. El hecho de que la prueba de independencia que se le ocurra al lector sea distinta de la aquí presentada no significa en modo alguno que esté mal. Siempre que a es independiente de T hay un número infinito de pruebas distintas de la independencia de a respecto a F.


o¡x = Ax (Sx -»■ Mx) a2 = “ i S a

= —i Ma

Pruébese: a3 es independiente de jai, a2j

120 SEMANTICA

N o t a : Este ejercicio puede interpretarse como una prueba de que la siguiente argumentación es incorrecta: “Cualquiera que pueda solucionar este problema es un matemático. Antonio no puede solucionar este problema. Por consiguiente, Antonio no es un matemático”.

Prueba de independencia correspondiente al ejercicio número 1.

Sea 7 una interpretación con De a., = Ax (ñx Mx) a3 = Ax (Mx -> Jx) a4 = De

Pruébese: a4 es independiente de jai, a2, a3j.

N o t a : Este ejercicio puede interpretarse como una prueba de que l a

siguiente argumentación es incorrecta: “Si todos los justos merecen el respeto de sus compatriotas, entonces Coriolano mereció su destino. Todos los magnánimos, y sólo ellos, merecen el respeto de sus compatriotas. Todos los magnánimos son justos. Por consiguiente, Coriolano mereció su destino”.


Sea 7 una interpretación con

°a = ¡0}7 {c ) = oy ( j ) = ¡oj7 (R ) = 7 ( D ) = 7 ( M ) = *

Como fácilmente se compnieba,.7 sat j«i, a2, a3j 7 no sat a4

Ejercicio número 3.ai = Axy (Vu (Rxu aRyu) -> Rxy)a2 = Ax Vy Rxya3 = A xyz (Rxy a Ryz -> Rxz)

Pruébese:( 1 ) : a 2 e s in d e p e n d i e n t e d e j a i , a 3j

( 2 ) : a i e s in d e p e n d i e n t e d e ja 2, a 3j

N o t a : a 3 n o e s in d e p e n d i e n t e d e j a i , a 2J, s in o u n a c o n s e c u e n c ia d e

j a i , a 2j. R e c u e r d e e l l e c t o r q u e e n e l e j e r c ic io d e d e d u c c i ó n n ú m e r o 8 p r o

b a m o s :

j * i , a 2j f— a 3


(1) ¿71 sea una interpretación con°)1 = {0|•7 i(R ) =Como fácilmente se comprueba,^ i s a t j a i , a 3j

7 i n o s a t a 2

(2) y i sea una interpretación con , <i, o>;Como fácilmente se comprueba, y o sat ja2, a3jy 2 no sat ai (pues <0, 0> e y (R ), <1, 0> e y (R),

pero < 0 , 1> i y (R)j


ai = —i V x a — jxa2 = A xy (fx = fy —> x = y)a3 = Pa a Ax (Px -» Pfx) -> Ax Pxai = Axy (Px a Py -> Rxy v Ryx)a,-, = V xy (x¥= y a Rxy)a6 = Ax (Rxx -> Ay (Rxy v Ryx))a7 = Ax Vy (x¥=y a Rxy)xs = Ax (Rax v Px)

1 2 2 SEMANTICA

Pruébese: a7 y ot8 son independientes de jai, a2, a3, a4> a5, a6J.


Sea 7 una interpretación con°ll — 6) (el conjunto de los números naturales)7 (a) = 07 ( f ) ~ la función “el siguiente d e...” : n 1—>■ n -f- 17 (P ) = 4>7 (R ) = \<0, 1>|Como fácilmente se comprueba,7 sat jax, a2, as, a4, a¡¡, afij7 no sat a7 (pues para 1 no hay ningún número natural y, tal que

<1, y> € 7 (R )).7 no sat a8 (pues para 0 no es el caso que <0, 0> 6 7 (R) ni que

0 e 7 ( F ) ) .


a i = tx —i V r/ (Py a Myx) — d a2 = Pd0¡3 = Vx (Px A Ex)a 4 = Ax (Px a Ex —> A y (Py a — i Ey —> Mxy)) ag = Ed

N o t a : Este ejercicio puede interpretarse como una prueba de que la siguiente argumentación es incorrecta: “Dios es el ser mayor que el cual nada puede ser pensado. Dios puede ser pensado. Algún ser puede ser pensado y existe. Cualquier ser que pueda ser pensado y exista es mayor que cualquier otro que sólo pueda ser pensado, pero no exista. Por consiguiente, Dios existe”

Esta argumentación es el famoso “argumento ontológico” de San Anselmo para probar la existencia de Dios. Muchos filósofos se han encargado de mostrar la invalidez de este argumento, al que tampoco han faltado defensores. Según Kant, el “argumento ontológico” sólo sería válido si la existencia fuera un predicado, lo cual no es el caso. Pero aun considerando la existencia como un predicado, el argumento ontológico tampoco resulta válido, como se muestra en la prueba de independencia de este ejercicio.

Sin embargo, esto no significa que de las premisas del “argumento ontológico” no se siga nada. Se sigue, por ejemplo, que “si Dios no existe, entonces hay un ser que puede ser pensado y que es mayor que aquel mayor que el cual nada puede ser pensado”, como quedó probado en el ejercicio

de deducción número 34. De aquí se desprende que la expresión "el ser mayor que el cual nada puede ser pensado” es una descripción impropia a la que propiamente no corresponde ningún objeto.

Prueba de independencia correspondiente al ejercicio número 5.Sea 7 una interpretación con

^ = 1 0 , 1}a = 0

7 (d ) = 0 7 (P ) = |0, 1|7 ( E ) = \1\7 (M ) = \< 1, 0>, <1, l>j

Como fácilmente se comprueba,

7 sat jai, a2, as, a4j 7 no sat


ai Ax Rxxa 2 = Axy (Rxy —> Ryx)a s = Axyz (Rxy a Ryz -» Rxz)r = ja i , «2, a 3J

Pruébese la independencia del conjunto P.

N o t a : P e s u n c o n ju n t o d e a x io m a s q u e d e fin e u n a r e la c ió n d e e q u i

v a le n c i a .

Pruebas de independencia correspondientes al ejercicio número 6.

1 . °: a i e s in d e p e n d i e n t e d e ja 2, a 3j

7 \ s e a u n a in t e r p r e t a c ió n c o n

°U = j0},7i(R) = 4>7 1 s a t j a 2, a 3j, p e r o 7 i n o s a t a i

2. °: a2 es independiente de jai, a3¡

7 2 s e a u n a in t e r p r e t a c ió n c o n

^ = { 0 , 1}7 2(fl) = J<0, 0>, <1, 1>, <0, 1>J7 2 s a t j a x, a 3j, p e r o 7 2 n o s a t a 2

124 SEMANTICA

3.°: a3 es independiente de jai, a2j

y s sea una interpretación con

°U = jO, 1, 2jJ ( R ) = j<0, 0>, <1, 1>, <2, 2>, <0, 1>, <1, 0>, <1, 2>, <2, l>j

sat {a1; a2j, pero no sat a3


ax = Axi/z (Rxy a Ryz -> Rxz) a, = Axy • (Rxy a R ij x -> x = y )

«3 = Axy (Rxy v Ryx)A = jai, a2, a3j

Pruébese la independencia del conjunto A.

Pruebas de independencia correspondientes al ejercicio número 7.

1. °: a! es independiente de ja2, a3j

x sea una interpretación con

°U = jO, 1, 2jr / 1(R) = \<0, 0>, <1, 1>, <2, 2>, <0, 1>, <1, 2>, <2, 0>{J x sat j a2, a3j, pero y \ no sat «i

2 . °: a2 es independiente de jai, a3j

.7 2 sea una interpretación con°ll = jO, 1 J.7 2(R) = j<0 , 0>, <1, 1>, <0, 1>, <1, 0>1 .7 2 sat ¡ai, a3J, pero . 7 2 no sat a2

3. ": a3 es independiente de jax, a2j 7 a sea una interpretación con°U = jOjJs (R ) = 4>7 s sat ¡«i, a2j, pero y 3 no sat a3

Ejercicio número 8 .

ax = Axy (x y y a P x a Py - > V z (Rz a E x z a Etjz)) o¡2 = Axyuz (x 7= y a P x a Py a R u a R z

a Exu a Eyu a Exz a Eyz - > u ~ z )

as = Az (Rz -> Vxtj (x y a Px a Py a E xz a Et/z))« i = Vxzi/ ( x ^ y a y ¥=z a x z a Px a Py a Pz

a i V m (Rw a E xu a Eyu a E z u ) )

T = | a i , a 2 , « 3, « 4|

Pruébese la independencia del conjunto P.

N o t a : Las sentencias de F pueden considerarse como la formalización de los primeros axiomas de enlace en la axiomatización de la geometría euclídea por Hilbert:

1) Para cada dos puntos distintos hay una recta en la cual esos dos puntos están.

2) Para cada dos puntos distintos no hay más de una recta en la cual esos dos puntos estén.

3) Para cada recta hay al menos dos puntos distintos que están en ella.

4) Hay tres puntos distintos que no están en la misma recta.

Pruebas de independencia correspondientes al ejercicio número 8 .

1. °: «i es independiente de ¡a2, «3, a4j J ' i sea una interpretación con ^ = ¡ 0 , 1 , 2 ¡J ¿ P ) = jO, 1, 2JJ i ( R ) = *

(E) = +jT i sat ja2, a3, a4¡, pero .Ai no sat ai

2 . °: a2 es independiente de jai, a3, «4j2 sea una interpretación con

, <0, 4>, <1, 3>, <1, 5>, <1, 6 >,

<2, 4>, <2, 5>, <2, 6 >jJ 2 sat jai, a3, a4j pero J 2 no sat a2

3. °: a3 es independiente de jai, «a, «4j j f 3 sea una interpretación con, <0, 4>, <1, 4>, <1, 5>, <2, 5>, <2, 3>|

3 sat jai, a2, a4j, pero J 3 no sat a3

126 SEMANTICA

4.u: a4 es independiente de {«i, a2, a3¡

7 4 sea una interpretación con°a = ¡0 }

= ¡o¡7 4(ñ) = 4>J i ( E ) = <f>J i sat jai, a2, a3¡, pero J 4 no sat a4.


a! s \/y (Ax (Sx /\Gx<^>x = y) /\tj — r) . a2 = Ax (Sx a —1 x = r —> Arx) a3 5= Vx (Sx a Gx a Apx) xi = Axy (Axy -> — 1 Ai/x)A = ¡ai, «2, a3,

Pruébese la independencia del conjunto A.

Pruebas de independencia correspondientes al ejercicio

1 . ”: es independiente de ja2, “a, o¡4¡ y 1 sea una interpretación con

aa ~ jo, ijy i (t) = o y 1 (p) = oAA(S) = JO, lj AA(G) = {lj 7 X(A) = j<0, l>jy 1 sat j a2, «3, «ij, pero 7 i no sat ai

2 . ": a2 es independiente de jai, a3, a4j

y 2 sea una interpretación con

au = ¡o, ij 7 2(r) = o 7 3(p) = 1 7 2(S) = j0, 1¡•7 2(G) = ¡0!7 2(A) = 5<1, 0>jy 2 sat jai, a3, a4j pero no sat a2

número 9.

3.°: a3 es independiente de jai, a2, a4|

CORRECCIÓN SEMÁNTICA 127

H 3 sea una interpretación con°ll = jOj •7s(f) = 0 •7»(p) = 0 ■7s(S) = |0¡•7*(G) = |0|•7S(A) = 4>J :¡ sat ja¡i, a2, a4j, pero no sat a3

4.°: a4 es independiente de ja,, a2,H i sea una interpretación conCU = jOj .7 . , ( r ) = 0 •74(p) = 0 ,7.,(S) = |0j ■7.t(G) = j0¡•7,|(A) = j <0 , 0 >¡.7., sat ja,, a2, asj, pero *74 no sat a4.

1II.7. Corrección semántica

7.0. Una argumentación — 0 una prueba— es correcta, válida o concluyente cuando su conclusión es una consecuencia de sus premisas. El que su conclusión sea una consecuencia de sus premisas se prueba ofreciendo una deducción de la conclusión a partir de las premisas. Este proceder tiene sentido porque suponemos que, dado un conjunto T de sentencias, todo lo que podamos deducir (con nuestro cálculo deductivo) a partir de T será también una consecuencia de F. Esto se puede expresar con otras palabras diciendo que suponemos que nuestro cálculo deductivo es semánticamente correcto.

Un cálculo deductivo es un conjunto de reglas por medio de las cuales unas sentencias pueden deducirse de otras. El concepto de deducibilidad sólo depende- de ese conjunto de reglas, es un concepto sintáctico. El concepto de consecuencia es un concepto semántico. Son dos conceptos distintos que, en principio, pueden no coincidir. Sin embargo, un concepto de deducibilidad que no implique la consecuencia es de poca utilidad. Un cálculo deductivo por medio del cual puedan deducirse a partir de F sentencias que no son consecuencias de F es inaplicable desde el punto de vista del control de pruebas y argumentaciones.

7.1. Definición: Un cálculo deductivo es semánticamente correcto si y solo si para cualquier conjunto T de sentencias y para cada sentencia a:

9. — 1 LÓGICA DE PR IM ER ORDEN

128 SEMÁNTICA

si a es deducible a partir de T por medio de las reglas del cálculo, entonces 7, e s una consecuencia de F.

7.2. Teorema de corrección semántica de nuestro cálculo deductivo: Para cualquier conjunto T de sentencias de [£ V cualquier sentencia a de ' 7 :

Si T i—z a, entonces F a.

Para probar 7.2. tendríamos que mostrar que siempre que una sentencia es deducible a partir de otras en el cálculo deductivo, la primera es úna consecuencia de las últimas. Para ello habríamos de examinar todas las reglas de inferencia y construcción, etc. De las reglas de inferencia, la única que podría presentar dificultades es EP, pero su corrección en el cálculo queda garantizada por el teorema 7.3. que a continuación probaremos. De todos modos, aquí renunciamos al desarrollo detallado de la prueba de 7.2. El lector interesado la podrá encontrar en el artículo “Remarks on Descriptions and Natural Deduction”, de R. Montague y D. Kalish (1957).

7.3. Teorema:

!u no está en Y, z, ¡3; u ^ x r u ¡ 5 " « ¡ t= R Y\=\/xz

Entonces, r t= /3

Prueba de 7.3: u no esté en z, ¡3, Y; u ^ x.

Sea T U j5“ aj t=¡3 y T Vx a.

Hay que demostrar que toda interpretación que satisface a T, satisface también a ¡3. J ’ sea una interpretación cualquiera, tal que: J sat F. Entonces:

J sat Vx a pues T i= Vx a

Hay un x, tal que J * sat a, tal que sat a por 2.4, pues u no está en a, tal que sat a por 1.4, pues x fé u

, tal que 3"*-^u ^ sat a pues 7 r* (u) = x, tal que .7 * sat 5 “ a por 3.1

tal que sat T por 2.4, pues 7r sat T y u nono está en T

, tal que 7r* sat Y U ¡5 “ aj

CONSISTENCIA Y SATISFACIBILIDAD 129

Hay un x tal que sat /3 pues P U ¡5“ aj i= ¡3

CT sat ¡3 por 2.4, pues u no está en ¡3

Así, pues, r i= ¡3.

q.e.d.

111.8. Consistencia y satisfacibilidad

8.0. El concepto de consistencia es un concepto sintáctico, definido en función de la deducibilidad y, por tanto —indirectamente— , en función de las reglas del cálculo deductivo. En efecto habíamos dicho que un conjunto P de sentencias era consistente en el caso de que hubiera al menos una fórmula que no fuese deducible de P, y que era inconsistente o contradictorio en el caso de que todas las fórmulas fuesen deducibles de T. El concepto de satisfacibilidad, por el contrario, es un concepto semántico, definido con independencia del cálculo y en función sólo de las interpretaciones.

Aprovechando los resultados sintácticos obtenidos en II.8, probaremos aquí una serie de importantes teoremas referentes a la satisfacibilidad. En 8/1 probamos que todo conjunto satisfacible de sentencias es consistente, lo cual es bastante trivial. Lo que no es nada trivial es que todo conjunto consistente de sentencias es satisfacible, lo cual probamos en 8.3. En 8.5 resumimos ambos resultados, enunciando la equivalencia del concepto sintáctico do consistencia y el concepto semántico de satisfacibilidad. 8.6 es un león ana con importantes aplicaciones metamatemáticas. En 8.7, y como corolario de 8.3, obtenemos el famoso teorema de Skolem.

8.1. Teorema: Todo conjunto máximamente consistente y ejemplificado de .sentencias sin descriptores es satisfacible sobre un universo numerable.

Prueba de 8.1:Sea P un conjunto máximamente consistente y ejemplificado de sentencias

sin descriptores de i / .En el conjunto T y de los términos sin descriptores del formalismo J5f defi

nimos una relación diádiea, a la que designaremos con ~ , en función de T, de la siguiente manera: para cualesquiera términos b, f2 de T y: ~ t->syss í, t-> s P. Teniendo en cuenta que P es un conjunto máximamente consistente, resulta que

~ es una relación reflexiva: í ~ f, pues t = t s T, por II.8.2, (2), ya que i - t t, por I.

~ es una relación simétrica: si t¡ ~ U, entonces U ~ L, pues si t¡ = U e P, entonces t2 — t\ 6 T, por II.8.2, (1), ya que t-, = t < \— z U = L , por SI.

130 SEMÁNTICA

—- es una relación transitiva: si ti ~ t2 y L ~ tu, entonces ti ~ í3, pues si ti — t2 g T y t-> — t¿ e r , entonces L = í3 g T, por II.8.2, (1), ya que ti = í2, U = tx i—« ti = í3, por TI.

Por tanto, —■ es una relación de equivalencia.Mediante t designaremos la clase de equivalencia inducida por --, en

la que está t. Es decir,í0 = jí ¡ í0 ~ tj = jí | 40 = í g Tj.Ahora definimos una interpretación 7 de la siguiente manera:El universo %í de 7 sea el espacio cociente T^/— es decir, sea el con

junto de las clases de equivalencia inducidas por — en el conjunto de los términos sin descriptores de 7 .

La aplicación de 7 sea definida así: para cada relator n-ádico Pde 7 :

7 (P) = j<íti, tn) ¡ Pti, ..., tn e P jPara cada functor n-ádico f de 7 :

J ( f ) ti, . . . , t n = ftu . . . ,t n Para cada variable x: 7 ( 7 ) - % .Para cada constante individual a: 7(a)\ a.Estas definiciones utilizan representantes fi, ...,t„ de las clases f1; .

pero son independientes de los representantes elegidos. En efecto, sean 1 1—- t ' j , í (t—- P . Entonces, t 1= f'g P, ..., tn= P g T y, por II.8.2, (I), Pti,

tn g T syss Pt'v ..., t'n g T. Por tanto, 7 (P ) = j<íi , ..., tn> | Pp, tn g TJ = = j<íj j Pf'j,..., Pn g Pj. Es decir, la definición de 7 (P) es independiente de los representantes elegidos. Y lo mismo en los demás casos.

Para cada término sin descriptores t de 7 , 7 (t) = t.Esto puede probarse por inducción sobre la longitud de los términos de

7 sin descriptores. En efecto,

7 (x) = x por definición7 (c) = c por definición7 (/ti, . . . ,t n) = 7 ( f ) ti, ..., tn supuesto inductivo

= fti. ...,t„ por definición

Para cada sentencia sin descriptores a de 7 :7 sat a si y sólo si a g I\Esto puede probarse por inducción sobre el número de signos lógicos

de las sentencias sin descriptores de 7 . En efecto,

7 sat Ptu . . . ,t n syss <.7(ti), . . . , 7 ( t n)> g 7 (P )syss<t!, . € )<?!,.. . ,?„> | Pti, . . . , í„g rj

pues 7 (t ) = t

CONSISTENCIA Y SATISFACIBILIDAD 131

(En especial, 7 sat t-¡ — t-.

7 sat ■“i a

7 sat (a a /3)

7 sat (a v /3)

De igual modo:7 sat (a /3) 7 sat (a «-»/3)

7 sat Ax a

7 sat Vx a

syss Ptu í„ € r syss 7 (t i ) — 7 (ti) syss = syss ti ~ í2 syss ti — í-2 e T) syss no 7 sat a sys no « e r syss ctfT syss ~i a e F syss 7 sat a y 7 syss a e T y /3 e T syss (a a /3) e T syss *7" sat a o 7 syss a e r o /3 e T syss (a v /3) € F

pues 7 (t) — t por definición

supuesto inductivo

por II.8.2, (3) sat P

supuesto inductivo por II.8.2, (4)

sat /3supuesto inductivo por II.8.2, (5)

syss (a -> /3) e F syss (a /3) e T

syss para todo t: 7 ' sat a

syss ” ” designador t: 7 ^ sat asyss ” ” ” : 7 JW sat a

pues 7 (t ) = tsyss ” ” ” : 7 sat 5 ' a

por 3.1syss ” ” ” : 5* a e F

sup. inductivosyss Ax a e T por II.8.3, (2)

syss hay un t, tal que 7 ‘ sat a

syss hay un designador í, tal que 7 * sat a

syss ” ” ” , tal que 7 yrw sat apues 7 (i) ~ t

syss ” ” ” , tal que 7 sat 5(, apor 3.1

syss ” ” ” tal que 5* a e Vsup. induct.

syss Vx a e r por II.8.3, (1)

132 SEMÁNTICA

Puesto que T es un conjunto de sentencias sin descriptores de Jzf, y cada sentencia sin descriptores de S£ es satisfecha por y , resulta que y satisface cada fórmula de I', es decir, qüe y satisface P.

El universo °U de y es numerable, pues su cardinalidad ha de ser igual o menor que la cardinalidad de T x, y Ty es claramente numerable.

Luego T es satisfacible sobre un universo numerable.

q.e.d.

8.2. Teorema: Todo conjunto consistente de sentencias sin descriptores de y es satisfacible en y sobre un universo numerable.

Prueba de 8.2.

Sea T un conjunto consistente cualquiera de sentencias sin descriptoresde y.

Según II.8.4, hay un conjunto máximamente consistente y ejemplificado r ° de sentencias sin descriptores de S£ U ‘éí, donde 7? es una clase de constantes individuales, tal que

F ° es satisfacible sobre un universo numerable, por 8.1, ya que r ° es máximamente consistente y ejemplificado.

r es satisfacible sobre un universo numerable, por 4.5, ya que todos los signos peculiares de Jzf lo son también de ,5? U T es un conjunto de fórmelas de y y T* es un conjunto de fórmulas de í ? U 'g', F C I’*, y r * es satisfacible sobre un universo numerable.

q.e.d.

8.3. Teorema: Todo conjunto consistente de sentencias de y es satisfacible en y sobre un universo numerable.

Prueba de 8.3.

T sea un conjunto consistente de sentencias de y . c sea una constante individual que no pertenece a y .

T U je = ti/ y — y\ es consistente en y U jej por II.7.7.

Definición: A = \<x' a' es una fórmula de y U {c}; hay un a 6 F, tal que c = ay y = y a <-»• <x'; a' carece de descriptores y tiene las mismasvariables libres que ocj.

Como las fórmulas de T son sentencias y las de A tienen las mismas variables libres que ellas, A es un conjunto de sentencias.

A es, pues, el conjunto de las sentencias sin descriptores a' de y U {c} para las que existe una l e f , tal que c = ty y = y i— «.

CONSISTENCIA Y SATISFACÍBILIDAD 133

Para cada a' e A hay una a e T, tal que

c = iy y = yc = i y y = y i— a -» a' o = ílJ y = y, a i- ufe) a'

por definición de A por EB

F U je — iy y — y J i—ifujcj a pues a e T

Así, pues, todas las fórmulas de A son deducibles a partir de r u jc = ’.y y = yj. Si A fuese contradictorio, también lo sería T U \c = ty y = y\, por la transitividad de la deducibilidad (II.2.9, b). Pero TU je = ly y = y\ es consistente. Luego A es consistente también.

A es, pues, consistente en Se U jcj.A es satisfacible sobre un universo numerable, por 8.2, ya que A es un

conjunto consistente de sentencias sin descriptores.Hay una interpretación J7 de ,5? U jcj sobre un universo numerable °U,

tai que y satisface A.

Sea .7 = <% We, a>.y sat A.

Consideremos ahora la interpretación J ' de , 7 U jcj, que sólo se diferencia de y en aplicar las descripciones impropias a Ü (c) en vez de a a. Es decir, sea

En efecto, sea a una fórmula cualquiera de P. Según II.6.1, a), hay una fórmula sin descriptores a' de Sé’ U jcj con las mismas variables libres que a y tal que

o = iy y = y « <■>

Es decir, hay una fórmula a' s A, tal quec = u y y = y h-jfuicj a «-»<*'c = ly y = y ¡=^uíc) por 7.2y sat c =%y y = y pues y ' ( y y = y) = y (c ) , por

y = <% we, J {c )> J ' satisface. T.

definición de yy sat a-o- a' J sat a' por definición de y , ya que

a' e Ay sat «' pues a' carece de descriptores y

y e y ' sólo se diferencian respecto a las descripciones

y sat aAsí, pues, y sat T.

pues y sat a <-> a' y y sat a'

134 SEMANTICA

.7" es una interpretación de [£ U jcj. J " sea la interpretación de Jz? que coincide con Cf' en todo (excepto en no poseer c entre sus constantes a interpretar, pues c no pertenece a S£).

Por definición de J " , para cualquier fórmula de Jzf:J " sat a si y sólo si J ’ sat a.

J " sat T, pues £ ' sat P y T es un conjunto de fórmulas de ¡£ .El universo de J " es el mismo que el de . 7 : °U,, un universo numerable. Así, pues, hay una interpretación (a saber, J ”) de Jz? sobre un universo

numerable, tal que J " sat 1'. Luego T es satisfacible en ¡£ sobre un universo numerable,

q.e.d.

8.4. Teorema: Todo conjunto satisfacible de sentencias de jz? es consistente en jz?.

Prueba de 8.4:r sea un conjunto satisfacible de sentencias de Jz?.Hay una interpretación J de Jz?, tal que J sat P.Si r fuera inconsistente en ü£, habría un /3 de 7% tal que T i—se /3 A /3 por II.7.3P t=¿f /3 a i /3 por 7.2J sat /3 a i /3 pues J sat TJ sat /3 y J sat —i /3J sat /3 y .7 no sat /3, lo cual es imposible.Luego r es consistente en Jz?. q.e.d.De 8.3 y 8.4 se sigue:

8.5. Teorema de equivalencia entre satisfacibilidad y consistencia: Sea T un conjunto de sentencias de .

P es satisfacible en Jz? syss 1' es consistente en Jz?.

8.6. Teorema de finitud para la satisfacibilidad: Sea T un conjunto de sentencias de jz?.

T es satisfacible en í£ si y sólo si cada subconjunto finito A C T e s satisfacible en í£ .

Prueba de 8.6:Sea P satisfacible en Jz?.Entonces, cada subconjunto finito A C T es satisfacible en Jz?, por 4.5. Sea cada subconjunto finito A C P satisfacible en ¿f.Si P no fuera satisfacible en , entonces 1’ sería inconsistente en £ ,

por 8.5. Por tanto, habría un a de tal que f t—« « A ma , por II.7.3.

COMPLETUD SEMÁNTICA 135

Habría un subconjunto finito A c T , tal que

A i—% a a —i a, por II.2.8.A sería inconsistente.A no sería satisfacible, por 8.5.Pero A sí es satisfacible.Por tanto, T es satisfacible en 5?.

q.e.d.

8.7. Teorema de la satisfacibilidad numerable o teorema de Skolem: Para cualquier conjunto 1' de sentencias de í¿\ Si P es satisfacible en Jz?, entonces 1' es satisfacible en jz? sobre un universo numerable.

Dicho con otras palabras: Si hay al menos una interpretación (con el universo que sea, y, por tanto, posiblemente con un universo infinito no numerable) que satisface P, entonces hay también una interpretación con un universo finito o infinito numerable que satisface F.

Prueba: T sea un conjunto satisfacible de sentencias de J¿.Entonces, T es consistente en jz?, por 8.4.Y, por tanto, T es satisfacible en jz? sobre un universo numerable, por 8.3.q.e.d.

III.9. Completud semántica

9.0. El que nuestro cálculo deductivo sea semánticamente correcto, es decir, el que por medio de sus reglas sólo se puedan deducir de T consecuencias de T, no significa que con su ayuda se puedan obtener todas las consecuencias de F. Por ejemplo, para otro tipo de formalismos que los aquí estudiados, a saber, para los formalismos de segundo orden (en los que no sólo hay variables ligadas que se refieren a individuos, sino también variables ligadas que se refieren a propiedades o relaciones) no hay ningún cálculo susceptible de obtener o deducir con sus reglas todas las consecuencias de un conjunto dado de sentencias. No sólo no lo hay, sino que no lo puede haber, como mostró Gódel en 1931 en su famoso teorema de la in- completud semántica de la lógica de segundo orden. Pero el mismo Gódel había probado el año anterior, 1930, que en la lógica de primer orden éramos más afortunados. En su igualmente famoso teorema de la completud semántica de la lógica de primer orden, Gódel probó que para los formalismos de primer orden es posible construir cálculos deductivos con cuyas reglas pueden deducirse todas las consecuencias de un conjunto dado de sentencias.

En 9.2. se prueba la completud semántica de nuestro cálculo deductivo, aprovechando los resultados de III.8. Para llegar hasta aquí hemos

136 SEMÁNTICA

seguido un camino muy distinto al que siguió Gódel. Fundamentalmente hemos llegado a este importante teorema aplicando los métodos expuestos por Henkin en 1949 y refinados por Hasenjaeger en 1953.

Así como en 8.5 habíamos establecido la equivalencia del concepto sintáctico de consistencia con el concepto semántico de satisfacibilidad, así también podemos aquí establecer en 9.3 la equivalencia del concepto sintáctico de deducibilidad con el concepto semántico de consecuencia. Todo esto se resume a veces diciendo que en la lógica de primer orden la semántica y la sintaxis son equivalentes entre sí.

9.1. Definición: Un cálculo deductivo es semánticamente completo si y sólo si para cualquier conjunto T de sentencias y para cada sentencia a: si a es una consecuencia de T, entonces a es deducible a partir de F por medio de las reglas del cálculo.

9.2. Teorema de la completud semántica de nuestro cálculo deductivo o teorema de Gódel: Para cualquier conjunto F de sentencias de 27 y cualquier sentencia a de 27:

Si T 1=¾ a, entonces T i— z a.

Prueba de 9.2.Sea T un conjunto de sentencias de 27 v o. una sentencia de 27. Sea

r 1=¾ a.Toda interpretación de 27 que satisface F, satisface también a, pues

T 1=¾ a.No hay ninguna interpretación de 27 que satisfaga F, pero no satisfaga a.

Es decir, no hay ninguna interpretación 2/ de 27, tal que 27 sat F y 27 no sat a.

No hay ninguna interpretación 27 de .27, tal que 27 sat T y 27 sat ~i <x.

r U j—i «t es insatisfacible en 27.

Ahora bien, todo conjunto consistente de sentencias de 27 es satisfacible en 27, por 8 3.

Luego T U j~i aj es inconsistente en 27.

F U j—i cej i—s a r U {—i aj i— ¡e ~i ~i a

r i— ¡c — i ~ i a

q.e.d.

De 7.2 y 9.2 se sigue:

pues r U j-.a| es inconsist. por DN por II.5.3 por DN

COMPLETUD SEMÁNTICA 137

9.3. Teorema de equivalencia entre deduoibilidad y consecuencia: Sea r un conjunto de sentencias de ¡£ y * una sentencia de ,5?.

T i=^ a syss r aEs decir, una sentencia es una consecuencia de otras sentencias si y sólo

si es deducible a partir de ellas.De ahí se sigue, para r = </>:\=x X syss i—s? aEs decir, una-sentencia es lógicamente válida si y sólo si es un teorema

lógico.De II.2.8 y 9.3 se sigue:

9.4. Teorema de finitud para la consecuencia: Sea T un conjunto de sentencias de =5? y a una sentencia de .

E 1=^ a si y sólo si hay un subconjunto finito A C I', tal que A 1=¾ a.

9.5. El teorema 8.3, que dice que todo conjunto consistente de sentencias es satisfacible sobre un universo numerable, es llamado a veces “teorema de Henkin”, por haber sido León Henkin el primero en formularlo y probarlo de un modo parecido al aquí expuesto. En realidad, los teoremas que le siguen se obtienen como meros corolarios del teorema de Henkin: tanto el teorema de completud semántica de Godel (9.2.), como el teorema de satisfacibilidad numerable de Skolem (8.7.) y el teorema de finitud para la satisfacibilidad o corwpactness theorem. (8.6.).

El teorema de Skolem tiene profundas repercusiones en la filosofía de la matemática —pues implica, entre otras cosas, que cualquier teoría formal construida para caracterizar una estructura de universo infinito supernumerable es también satisfecha por interpretaciones sobre universos numerables,: por lo que lo supernumerable no es caracterizable en la lógica de primer orden— e importantes aplicaciones en la metateoría de conjuntos. El teorema de finitud para la satisfacibilidad tiene múltiples aplicaciones en meta- matemática, tales como la obtención de modelos no-standard de la aritmética —es decir, de sistemas no isomorfos con el de los números naturales pero que, sin embargo, cumplen cuanto exigen los axiomas de la aritmética de primer orden'—.

De hecho, ambos teoremas —el de Skolem y el de finitud— constituyen la base de la teoría de modelos, una de las ramas más florecientes de la lógica actual. Incluso es posible probar ambos teoremas sin hacer uso para nada de un cálculo deductivo ni, por tanto, de los teoremas de Henkin y Godel. En efecto, el teorema de Skolem puede ser probado directamente a partir del de finitud y éste, a su vez, puede ser probado dentro de la

138 SEMÁNTICA

teoría de modelos mediante la formación de ultraproductos adecuados y sin referencia alguna a un cálculo deductivo. El lector interesado por estos desarrollos puede consultar la sobras de Bell y Slomson, de Ghang y Keisler o de Schwabháuser.

BIBLIOGRAFÍA

Trabajos aludidos en este libro:

Be l l , j . y Slomson, A., M o d els a n d U ltraproducts. Amsterdam. 1971.

Cahnap, R., M ea n in g an d N ecessity, a Stud y in Sem antics an d M odal L o g ic . Chicago, 1947.

Chang, C. y Keisl e r , H. J., M o d el T h eo ry . Amsterdam. 1973.

F r e c e , G ., B egriffsschrift, e ine d e r arithm etischen m c h g e b ild e te n F orm elsprache d e s reinen D en k en s . Halle, 1879.

F hege, G., U eb er Sinn u n d B e d e u tu n g . Zeitsehrift für Philosophie und philoso- phische Kritik (vol. 100), 1892.

Gentzen, G., U n tersu ch u n gen líber das L o gisch e Schlíessen . Math. Zeischriít (vol. 39), 1934 .

Gódel, K., D ie V ollstandigkeit d e r A xio m e d es logischen Funktionenkalküls. Mo- natshefte für Mathematik und Physik (vol. 37), 1930.

Godet., K., U eb er form al u n en tsch eid b a re Satze d e r Principia M athem atica u n d verw andter S y stem e. Monatshefte für Mathematik und Physik (vol. 38), 1931 .

Hasenjaeger, G., E in e B e m erk u n g zu H e n k ín s B etceis fü r d ie V ollstandigkeit des P radikatenkalküls d er ersten Stufe. Journal of Svmbolic Logic (vol. 18), 1953.

Henkin, L ., T h e cóm pleteness of th e first-order functional calculas. Journal of Symbolic Logic (vol. 14), 1949.

Hermes, H ., E in fü h ru n o in d ie m athem atische L o gik . Stuttgart, 1963.H il b e r t , D. y Ackermann, W ., G ru n d z ü g e d e r theoretischen L ogik . Berlín, 1928 .

Kalish, D. y Montagtje, R., Remarles on descriptions an d natural d ed u ctio n . Ar- chiv für mathematische Logik und Grundlagenforschung (vol. 3), 1957.

Kalish , D. y Montagtje, R., L o g ic . Techniques of Form al Reasoning. New York, 1964.

P eano, G., N otation d e lo giq ue m athém atique. Turín, 1894 .

Q tjine, W . V., Set T h eo ry an d its L o g ic . Cambridge, Mass., 1963.

Schwabhauser, W ., M o d ellth eo rie . Mannheim. 1972.

140 BIBLIOGRAFÍA

T arski, A., Der Wahrheitshegriff in den formalisierten Sprachen. Studia Philoso- phica (vol. 1), 1936.

T arski, A., Rcmarks on the formalization of the predícate calculas. Bulletin of the American M athematical Society (vol. 57), 1951 .

W hitehead , A. N. y Ru ssell , B., Principia Mathematica. Cambridge, 1910-13 .

Algunos manuales de lógica escritos en castellano:

D eaño, A., Introducción a la lógica formal. Alianza Editorial. Madrid.

F errater M ora, J. y L eblanc, H., Lógica matemática. Fondo de Cultura E co nómica. México.

Garrido, M ., Lógica Simbólica. Editorial Tecnos. Madrid.

M osterín , J., Teoría axiomática de conjuntos. Ediciones Ariel. Barcelona.

S acristán, M .: Introducción a la lógica y al análisis formal. Ediciones Ariel. Barcelona.

Algunos manuales de lógica traducidos al castellano:

D alla Chiara S cabia, M. L ., Lógica. Editorial Labor. Barcelona.

H asenjaeger, H., Conceptos y problemas de la lógica moderna. Editorial Labor. Barcelona.

Hil b e r t , D. v Ackermann, W ., Elementos de lógica teórica (traducción de la 4 .íl edición alemana). Editorial Tecnos. Madrid.

Kleen e , S. C., Introducción a la metamatemática. Editorial Tecnos. Madrid.

M ates, B., Lógica Elemental. Editorial Tecnos. Madrid.

Quine, W . V ., Métodos de la lógica. Ediciones Ariel. Barcelona.Q uine, W . V., El sentido de la nueva lógica. Editorial Nueva Visión. Buenos Aires. Quine, W . V., Lógica matemática. Revista de Occidente. Madrid.

Suppes, P. y Hill, S., Introducción a la lógica matemática. Editorial Reverte. Barcelona.

Tarski, A., Introducción a la lógica matemática y a la metodología de las ciencias deductivas. Espasa-Calpe. Madrid.

El presente libro, Lógica d e p r im er o rd en , constituye un manual universitario sucinto y riguroso donde la parte central de la lógica se presenta con una considerable precisión, ofreciéndose al estudiante definiciones exactas y pruebas completas. Este rigor teórico se combina con la preocupación práctica por el dominio de las técnicas. Precisamente la abundancia de ejercicios resueltos, que ofrecen al lector amplia oportunidad de practicar lo aprendido, constituye una de las características peculiares de esta obra. Su autor, Jesús Mosterín, se licenció por la Universidad de Madrid y doctoró por la de Barcelona en filosofía. Se especializó en lógica durante 3 años en el Instituí für mathematische Logik und Grundlagenforschung de la Universidad de Münster (Alemania). Desde 1966 es profesor de lógica y filosofía de la ciencia de la Universidad de Barcelona.

Manuel Sacristán

INTRODUCCIÓN A LA LÓGICA Y AL ANÁLISIS FORMAL

No hace mucho más de siglo y medio que un gran filósofo consideraba la lógica como perfecta y conclusa en lo esencial desde los tiempos de Aristóteles. Hoy la lógica, tras haber mostrado, con los espectaculares progresos conseguidos en ese siglo y medio, que no estaba, ni mucho menos, perfecta, sigue además sin concluirse.Uno de los capítulos más interesantes, útiles y no conclusos de la lógica moderna es la aclaración de conceptos frecuentemente usados en las ciencias particulares, como los de sistema teórico o teoría, cálculo o algoritmo, función, isomorfías, estructuras, etc. Para precisar esos conceptos hay que familiarizarse, por de pronto, con el punto de vista lógico formal, y debe aclararse la relación entre la lógica y las ciencias reales. Este manual de introducción, que se abre precisamente con unas páginas dedicadas a las relaciones entre la lógica formal y las ciencias reales, se destina a dar una visión general del punto de vista lógico, sobre todo en la medida necesaria para estudiar aquellos conceptos formales que son de aplicación general en las ciencias. Sus destinatarios no son, pues, principalmente, los gremios tradicionales de cultivadores de la lógica — los filósofos y los matemáticos —, sino los estudiosos de ciencias reales que, cada vez en mayor número, notan la conveniencia de atender también a los fundamentos formales de sus conceptos y métodos.

Logica de Primer Orden. Jesus Moster¡n

Documents

Transcript of Logica de Primer Orden. Jesus Moster¡n