Logic TK: algebric notions from Tarski's consequence operator

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

L'assioma della scelta e il paradosso di Banach-Tarski

La tesi tratta della formulazione dell'assioma della scelta fatta da Zermelo e di alcune sue forme equivalenti. Inoltre si parlerà della sua storia, delle critiche che gli sono state mosse e degli importanti teoremi che seguono direttamente dall'assioma. Viene anche trattato il paradosso di Hausdorff che introduce il problema della misura e il paradosso di Banach-Tarscki.

Quase-verdade e pragmatismo

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Truths ancient and modern

The paper presents a comparison of the theories of truth, and the solutions of the liar paradox, proposed by Thomas Bradwardine (c. 1290-1349), Jean Buridan (c. 1295-1358), and Alfred Tarski (1901-1983).

Koko totuus totuudesta

Nimekkeen selitys: Ilkka Niiniluodon, Alfred Tarskin ja Peter Ungerin totuusteoriat.

Progresso Científico e Verdade em Popper

O presente trabalho pretende mostrar que, para solucionar a questão da possibilidade do progresso científico, Popper precisou introduzir a ideia de verdade no âmbito de sua teoria da ciência. Essa concepção de progresso, em termos da noção de verdade, só será delineada na obra Conjectura e refutações (1963), pois a ideia de que o alvo da ciência é a verdade ainda não aparece teorizada em suas primeiras obras. Quando Popper escreveu sua A lógica da pesquisa científica(1934), a ciência era definida em termos de regras lógico-metodológicas e não de suas metas. O avanço científico é concebido a partir das noções de testabilidade e de corroborabilidade das teorias, exigências lógicometodológicas para que uma teoria seja considerada como científica. Popper não relacionou a questão do progresso científico à noção de verdade, nessa obra, porque, quando a escreveu, não dispunha de uma consistente teoria da verdade. Foi somente após Tarski ter escrito seu artigo sobre a concepção semântica da verdade que Popper, tendo por base essa concepção de verdade, pôde complementar as suas teses sobre o progresso da ciência, expostas em sua A lógica da pesquisa cientifica, com uma teoria acerca do conteúdo de verdade e da aproximação da verdade.

Sobre el valor de la verdad: una crítica a Richard Rorty

En el presente texto se sostiene, con Rorty, que la verdad no es una propiedad de hechos –ni mucho menos de objetos–. Sin embargo, contra Rorty, se afirma que asumir esta posición no implica la eliminación del concepto de verdad de nuestros discursos teóricos y filosóficos, esto es, que sigue teniendo sentido hacer una reflexión filosófica sobre la verdad. La estrategia para mostrar esto es abiertamente pragmatista: se inicia con el análisis de las prácticas de los hablantes para mostrar que no adquirimos los mismos compromisos cuando atribuimos verdad y cuando atribuimos justificación (sección 1); posteriormente, se evidencia en qué sentido la distinción filosófica entre verdad y justificación es útil socialmente (sección 2); y para finalizar, se muestra que dicha distinción no entraña ninguna metafísica misteriosa (sección 3).

Terceiro problema de Hilbert e Teorema de Dehn

Pós-graduação em Matemática em Rede Nacional - IBILCE

A neighbourhood semantic for the Logic TK

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Quase-verdade e pragmatismo

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Fixed point theorems in partially ordered spaces and aplications

[ES]Recientemente, en la Teoría del punto fijo, han aparecido muchos resultados que obtienen condiciones suficientes para la existencia de un punto fijo si trabajamos con aplicaciones en un conjunto dotado de un orden parcial. Generalmente, estos resultados combinan dos teoremas del punto fijo fundamentales: el Teorema de la contracción de Banach y el Teorema de Knaster-Tarski.

Logiche proposizionali polivalenti

In questa tesi si intende presentare le logiche proposizionali polivalenti con alcuni esempi: esse sono estensioni dalla logica classica a insiemi (in generale ancora finiti come in questa tesi) di valori di verità maggiori di due. La sintassi è la stessa ma non la semantica, rappresentata però sempre da tavole di verità o interpretazioni. Nel primo capitolo sono presentate le definizioni e gli elementi della logica classica che serviranno per studiare questo nuovo tipo di logiche. Nel secondo capitolo è esposto l'esempio di una logica a quattro valori. Si dimostra la completezza di questo calcolo, in una forma diversa rispetto alla logica classica usando tecniche simili. Non valgono infatti il principio del terzo escluso e la Legge di Lewis. Si analizza la validità delle regole del calcolo della deduzione naturale e la riscrittura delle leggi di De Morgan. Nell'ultimo capitolo si affrontano le logiche a n valori con n>2 e varianti a tre valori (vero, falso e indefinito) con i principali esempi di Lukasiewicz-Tarski, Kleene, Priest e Bochvar. Nelle conclusioni si ricordano alcune applicazioni di questo tipo di logiche facendo riferimento alla meccanica quantistica, all'informatica e all'elettronica.

Relational and Allegorical Semantics for Constraint Logic Programming

El cálculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schröder. Tarski, Givant, Freyd y Scedrov demostraron que las álgebras relacionales son capaces de formalizar la lógica de primer orden, la lógica de orden superior así como la teoría de conjuntos. A partir de los resultados matemáticos de Tarski y Freyd, esta tesis desarrolla semánticas denotacionales y operacionales para la programación lógica con restricciones usando el álgebra relacional como base. La idea principal es la utilización del concepto de semántica ejecutable, semánticas cuya característica principal es el que la ejecución es posible utilizando el razonamiento estándar del universo semántico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las álgebras relacionales distributivas con un operador de punto fijo capturan toda la teoría y metateoría estándar de la programación lógica con restricciones incluyendo los árboles utilizados en la búsqueda de demostraciones. La mayor parte de técnicas de optimización de programas, evaluación parcial e interpretación abstracta pueden ser llevadas a cabo utilizando las semánticas aquí presentadas. La demostración de la corrección de la implementación resulta extremadamente sencilla. En la primera parte de la tesis, un programa lógico con restricciones es traducido a un conjunto de términos relacionales. La interpretación estándar en la teoría de conjuntos de dichas relaciones coincide con la semántica estándar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la corrección y equivalencia operacional de esta nueva semántica, así como se define un algoritmo de unificación mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una semántica para la programación lógica con restricciones usando la teoría de alegorías—versión categórica del álgebra de relaciones—de Freyd. Para ello, se definen dos nuevos conceptos de Categoría Regular de Lawvere y _-Alegoría, en las cuales es posible interpretar un programa lógico. La ventaja fundamental que el enfoque categórico aporta es la definición de una máquina categórica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la máquina modela la ejecución eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el cálculo de pullbacks en Categorías Regulares de Lawvere. Los dominios de las tabulaciones aportan información sobre la utilización de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificación de la máquina induce la derivación formal de un juego de instrucciones eficiente. El marco categórico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el carácter 100% declarativo de nuestra semántica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schröder, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.