This paper focuses on the evolution of the notion of completeness in contemporary logic. We discuss the differences between the notions of completeness of a theory, the completeness of a calculus, and the completeness of a logic in the light of Gödel's and Tarski's crucial contributions.We place special emphasis on understanding the differences in how these concepts were used then and now, as well as on the role they play in logic. Nevertheless, we can still observe a certain ambiguity in (...) the use of the close notions of completeness of a calculus and completeness of a logic. We analyze the state of the art under which Gödel's proof of completeness was developed, particularly when dealing with the decision problem for first-order logic. We believe that Gödel had to face the following dilemma: either semantics is decidable, in which case the completeness of the logic is trivial or, completeness is a critical property but in this case it cannot be obtained as a corollary of a previous decidability result. As far as first-order logic is concerned, our thesis is that the contemporary understanding of completeness of a calculus was born as a generalization of the concept of completeness of a theory. The last part of this study is devoted to Henkin's work concerning the generalization of his completeness proof to any logic from his initial work in type theory. (shrink)

Este libro es un compendio de diversos artículos del ámbito de la Lógica que cubren un amplio abanico de temas ofreciendo una panorámica sobre esta disciplina. Encontraremos artículos sobre aspectos históricos y sobe el desarrollo de la lógica en la filosofía, la informática y las matemáticas actuales; otros sobre cuestiones de metalógica, y otros sobre diferentes tipos de lógicas: intuicionista, híbridas e intensionales, y sus lenguajes, semánticas y aplicaciones. El resultado en su conjunto es, además, una reflexión sobre el papel (...) de la Lógica en el pasado, presente y futuro de la ciencia y el pensamiento. Pero este libro quiere ser, sobre todo, un homenaje a una de las lógicas más reconocidas de España, María Manzano, que con su actividad académica ha contribuido de forma fundamental al desarrollo del área de Lógica y Filosofía de la Ciencia en España, a la vez que es apreciada en la gran comunidad internacional de lógicos. Con la excusa de su jubilación como catedrática de la Universidad de Salamanca, veintitrés autores que han compartido con ella aventuras en el mundo de la Lógica se han reunido para contarle (y contarnos) algunas de esas apasionantes aventuras. (shrink)

The semantic analysis of logical consequence must obey a set of requisites which nowadays have acquired a dogmatic status. This situation prevents the development of other varieties of this fundamental relation. In this issue we try to define what we call a naive variety of logical consequence. The main feature of this relation is the way it depends on formulas in premises and conclusion: every sentence must contribute to the acceptability of an argument in a significative way. This circumstance can (...) be of some interest for research programs demanding a logical apparatus sensitive to application context. We think of the logic LP developed by G. Priest -- Priest [1979] -- in relation to Gödel incompleteness theorems as a test for our points of view. (shrink)

Este trabajo aborda el estado actual de la cuestión en el ámbito de la computación teórica desde una perspectiva especialmente dirigida a lectores no expertos y con una clara vocación filosófica. En la primera parte, secciones 1 a 4, se ofrecen algunas de las claves para entender la importancia de la Teoría clásica de la Computación extrayendo conclusiones filosóficas de fundamental importancia para entender el nacimiento de la I.A. En su segunda parte se analizan los nuevos modelos propuestos haciendo balance (...) de sus dificultades y su interés relativo. (shrink)

La Teoría de la Computación es un campo especialmente rico para la indagación filosófica. EI debate sobre el mecanicismo y la discusión en torno a los fundamentos de la matemática son tópicos que estan directamente asociados a la Teoria de la Computación desde su misma creación como disciplina independiente. La Tesis de Turing-Church constituye uno de los resultados mas característicos en este campo estando, además, lleno de consecuencias filosóficas. En este ensayo se ofrece una guía de referencia útil a aquellos (...) que desean prestar alguna atención a estos asuntos y carecen de la base técnica o histórica que se precisa. En primer lugar se ofrece un resurnen de los principales problemas relacionados con la Tesis de Turing-Church para ofrecer a continuación información sobre sus aspectos más controvertidos. Se proponen algunos problemas no resueltos y se analiza su relevancia filosófica.Computer Science is a field specially rich for philosophical inquiry. Mechanism and the discussion around foundations of mathematics are topics directly asociated to Computer Science for its very constitution as an independent discipline. Church-Turing Thesis is one of the most characteristic results in this field and is plenty of philosophical consequences. In this article I offer a referenee guide useful for those who are willing to pay some attention to these matters and ignore the technical and historical basis needed for this task. I resume the main topics related to Church-Turing Thesis and give some informationabout the most controversial aspects of this subject. Some open questions are settled for further investigation paying special attention to their philosophical importance. (shrink)

La Teoría de la Computación es un campo especialmente rico para la indagación filosófica. EI debate sobre el mecanicismo y la discusión en torno a los fundamentos de la matemática son tópicos que estan directamente asociados a la Teoria de la Computación desde su misma creación como disciplina independiente. La Tesis de Turing-Church constituye uno de los resultados mas característicos en este campo estando, además, lleno de consecuencias filosóficas. En este ensayo se ofrece una guía de referencia útil a aquellos (...) que desean prestar alguna atención a estos asuntos y carecen de la base técnica o histórica que se precisa. En primer lugar se ofrece un resurnen de los principales problemas relacionados con la Tesis de Turing-Church para ofrecer a continuación información sobre sus aspectos más controvertidos. Se proponen algunos problemas no resueltos y se analiza su relevancia filosófica.Computer Science is a field specially rich for philosophical inquiry. Mechanism and the discussion around foundations of mathematics are topics directly asociated to Computer Science for its very constitution as an independent discipline. Church-Turing Thesis is one of the most characteristic results in this field and is plenty of philosophical consequences. In this article I offer a referenee guide useful for those who are willing to pay some attention to these matters and ignore the technical and historical basis needed for this task. I resume the main topics related to Church-Turing Thesis and give some informationabout the most controversial aspects of this subject. Some open questions are settled for further investigation paying special attention to their philosophical importance. (shrink)

Este trabajo constituye una revisión de los contenidos, orientación y objetivos de una parte significativa de los manuales de lógica elemental de las décadas de 1960 y 1970 redactados por autores españoles. En concreto, analizamos los prólogos, los rudimentos prerios, y la presentación de los distintos cálculos gue aparecen en tales obras. EI estudio de la semántica, los contenidos metatcóricos o las extensiones de Ia lógica elemental quedan para una segunda etapa de esta investigacion.This work is a critical examination of (...) contents, orientation, and goals of a significative portion of elementary spanish logic textbooks in the 60’s and 70’s. It is centered on an analysis ofprefaces, preliminaries and the different kinds of calculi appearing in these books. Topics, like semantics, metatheory or extensiones of elementary logic, are left for futrher analysis. (shrink)

En este estudio analizamos dos tendencias claramente distintas y contrapuestas en la forma de impartir cursos elementales de Lógica en la formación superior. Para este propósito, se ha seleccionado una muestra de manuales angloamericanos clásicos, así como otra más pequeña de la tradición iberoamericana para comprobar nuestras hipótesis. Los estilos identificados y analizados en dichos manuales son lo que hemos denominado lógica matemática y lógica para filósofos. En ambos casos se trata de tendencias muy generales reconocibles en las más diversas (...) tradiciones locales. El periodo analizado, 1940-1980, responde al proceso de introducción de la Lógica contemporánea en el ámbito académico occidental. (shrink)

In this paper we will discuss the active part played by certain diagonal arguments in the genesis of computability theory. 1 In some cases it is enough to assume the enumerability of Y while in others the effective enumerability is a substantial demand. These enigmatical words by Kleene were our point of departure: When Church proposed this thesis, I sat down to disprove it by diagonalizing out of the class of the λ–definable functions. But, quickly realizing that the diagonalization cannot (...) be done effectively, I became overnight a supporter of the thesis. (1981, p. 59) The title of our paper alludes to this very work, a task on which Kleene claims to have set out after hearing such a remarkable statement from Church, who was his teacher at the time. There are quite a few points made in this extract that may be surprising. First, it talks about a proof by diagonalization in order to test—in fact to try to falsify—a hypothesis that is not strictly formal. Second, it states that such a proof or diagonal construction fails. Third, it seems to use the failure as a support for the thesis. Finally, the episode we have just described took place at a time, autumn 1933, in which many of the results that characterize Computability Theory had not yet materialized. The aim of this paper is to show that Church and Kleene discovered a way to block a very particular instance of a diagonal construction: one that is closely related to the content of Church's thesis. We will start by analysing the logical structure of a diagonal construction. Then we will introduce the historical context in order to analyse the reasons that might have led Kleene to think that the failure of this very specific diagonal proof could support the thesis. This is a joint paper. We have both attempted to add a small piece to an amazing historical jigsaw puzzle at a juncture we feel to be appropiate. In the paper by Manzano 1997 the aforementioned words by Kleene were quoted, and since then several logicians, Enrique Alonso first and foremost, have questioned her on this issue. Here we both submit our reply. (1999, pp. 249--273). (shrink)

Este trabajo constituye una revisión de los contenidos, orientación y objetivos de una parte significativa de los manuales de lógica elemental de las décadas de 1960 y 1970 redactados por autores españoles. En concreto, analizamos los prólogos, los rudimentos previos, y la presentación de los distintos cálculos que aparecen en tales obras. El estudio de la semántica, los contenidos metateóricos o las extensiones de la lógica elemental quedan para una segunda etapa de esta investigación.

Leon Henkin (1921–2006) was not only an extraordinary logician, but also an excellent teacher, a dedicated professor and an exceptional person. The first two sections of this paper are biographical, discussing both his personal and academic life. In the last section we present three aspects of Henkin’s work. First we comment part of his work fruit of his emphasis on teaching. In a personal communication he affirms that On mathematical induction, published in 1969, was the favourite among his articles with (...) a somewhat panoramic nature and not meant exclusively to specialists. This subject is covered in the first subsection. Needless to say that we also analyse Henkin’s better known contribution: his completeness method. His renowned results on completeness for both type theory and first order logic were part of his thesis, The Completeness of Formal Systems, presented at Princeton in 1947 under the advise of Alonzo Church. It is interesting to note that he obtained the proof of completeness for first order logic readapting the argument for the theory of types. The last subsection is devoted to philosophy. The work most directly related to philosophy is an article entitled: Some Notes on Nominalism which appeared in the Journal of Symbolic Logic in 1953. Unfortunately, we are not covering his contribution to the field of cylindric algebras. As a matter of fact, Henkin spent many years investigating algebraic structures with Alfred Tarski and Donald Monk, among others. (shrink)

Este ensayo ofrece un análisis crítico del último argumento que el matemático y filósofo Roger Penrose ofrece a favor de la tesis según la cual hay habilidades de la mente humana que nunca podrán ser igualadas por ingenio mecánico alguno. Al mismo tiempo se ofrece una descripción general de los últimos episodios del eterno enfrentamiento entre mentalismo y mecanicismo y se concluye con una sugerencia acerca de los puntos en los que cabe esperar nuevas situaciones de tensión entre estos dos (...) grandes paradigmas. Este trabajo pretende, además, mostrar la vigencia de un tipo de filosofía elaborada a partir de las herramientas de la ciencia moderna cuyos problemas son, no obstante, los del pensamiento filosófico tradicional. (shrink)