Relational methods in algebraic logic

Abstract

[eng] This thesis is concerned with three instances of relational methods in algebraic logic. First, determining which partially ordered sets are isomorphic to the spectrum of a Heyting algebra. This is an open question related to the classical problem of representing partially ordered sets as spectra of bounded distributive lattices or, equivalently, commutative rings with unit. We prove that a root system (the order dual of a forest) is isomorphic to the spectrum of a Heyting algebra if and only if it satisfies a simple order theoretic condition, known as "having enough gaps", and each of its nonempty chains has an infimum. This strengthens Lewis' characterisation of the root systems which are spectra of commutative rings with unit. While a similar characterisation for arbitrary forests currently seems out of reach, we show that a well-ordered forest is isomorphic to the spectrum of a Heyting algebra if and only if it has enough gaps and each of its nonempty chains has a supremum. Second, Sahlqvist theorem provides sufficient syntactic conditions for a normal modal logic to be complete with respect to an elementary class of Kripke frames. We extend Sahlqvist theory to the fragments of the intuitionistic propositional calculus that include the conjunction connective. This allows us to introduce a Sahlqvist theory of intuitionistic character amenable to arbitrary protoalgebraic deductive systems. As an application, we obtain a Sahlqvist theorem for the fragments of the intuitionistic propositional calculus that include the implication connective and for the extensions of the intuitionistic linear logic. Third, Blok's celebrated dichotomy theorem proves that each normal modal logic shares its Kripke frames with exactly one or continuurn-many logics. It is an outstanding open problem to characterise the number of logics having the same posets of an axiomatic extension of the intuitionistic propositional calculus. We solve this question in the case of implicative logics, the axiomatic extensions of the implicative fragment of the propositional intuitionistic logic. In this case, a trichotomy holds: every irnplicative logics shares its posets exactly with 1, N0, or 2(No) many logics.

[cat] Aquesta tesi tracta tres casos de mètodes relacionals en lògica algebraica. En primer lloc, es pretén determinar quins conjunts parcialment ordenats són isomorfs a l'espectre d'una àlgebra de Heyting. Es tracta d'una qüestió oberta relacionada amb el problema clàssic de representar conjunts parcialment ordenats com a espectres de reticles distributius afitats o, equivalentment, d'espectres d'anells commutatius amb unitat. Demostrem que un sistema d'arrels (el dual d'ordre d'un bosc) és isomorfa l'espectre d'una àlgebra de Heyting si, i només si satisfà una simple condició teòrica d'ordre, coneguda com a "tenir prou buits", i cadascuna de les seves cadenes no buides tenen un ínfim. Això reforça la caracterització de Lewis dels sistemes d'arrels que són espectres d'anells commutatius amb unitat. Encara que una caracterització similar per boscos arbitraris sembla actualment difícilment assolible, demostrem que un bosc ben ordenat és isomorf a l'espectre d'una àlgebra de Heyting si, i només si, té prou buits i cadascuna de les seves cadenes no buides té suprem. En segon lloc, recordem que el teorema de Sahlqvist proporciona condicions sintàctiques suficients perquè una lògica modal normal sigui completa respecte a una classe elemental de marcs de Kripke. Estenem la teoria de Sahlqvist als fragments del càlcul proposicional intuïcionista que inclouen la conjunció. Això ens permet introduir un tipus de teoria de Sahlqvist de caràcter intuïcionista per sistemes deductius protoalgebraics arbitraris. Com a aplicació, obtenim un teorema de Sahlqvist pels fragments del càlcul proposicional intuïcionista que inclouen la implicació i per les extensions de la lògica lineal intuïcionista En tercer lloc, recordem que el cèlebre teorema de dicotomia de Blok demostra que cada lògica modal normal comparteix els seus marcs de Kripke amb exactament 1 o 2(N°) lógiques. Caracteritzar el nombre de lògiques que tenen els mateixos conjunts parcialment ordenats d'una extensió axiomàtica del càlcul proposicional intuïcionista és un problema obert. Resolem aquesta qüestió en el cas de les lògiques implicatives, les extensions axiomàtiques del fragment implicatiu de la lògica intuïcionista proposicional. En aquest cas, es compleix una tricotomia: cada lògica implicativa comparteix els seus conjunts parcialment ordenats exactament amb 1, N(o), o 2(No) lògiques.

[spa] Esta tesis se ocupa de tres casos de métodos relacionales en lógica algebraica. En primer lugar, se pretende determinar qué conjuntos parcialmente ordenados son isomorfos al espectro de un álgebra de Heyting. Se trata de una cuestión abierta relacionada con el problema clásico de representar conjuntos parcialmente ordenados como espectros de retículos distributivos acotados o, equivalentemente, anillos conmutativos con unidad. Demostramos que un sistema de raíces (el dual de orden de un bosque) es isomorfo al espectro de un álgebra de Heyting si y sólo si satisface una simple condición teórica de orden, conocida como "tener suficientes huecos", y cada una de sus cadenas no vacías tiene un ínfimo. Esto refuerza la caracterización de Lewis de los sistemas de raíces que son espectros de anillos conmutativos con unidad. Aunque una caracterización similar para los bosques arbitrarios parece actualmente difícilmente alcanzable, demostramos que un bosque bien ordenado es isomorfo al espectro de un álgebra de Heyting si y sólo si tiene suficientes huecos y cada una de sus cadenas no vacías tiene un supremo. En segundo lugar, el teorema de Sahlqvist proporciona condiciones sintácticas suficientes para que una lógica modal normal sea completa con respecto a una clase elemental de marcos de Kripke. Extendemos la teoría de Sahlqvist a los fragmentos del cálculo proposicional intuicionista que incluyen la conjunción. Esto nos permite introducir una teoría de Sahlqvist de carácter intuicionista susceptible de sistemas deductivos protoalgebraicos arbitrarios. Como aplicación, obtenemos un teorema de Sahlqvist para los fragmentos del cálculo proposicional intuicionista que incluyen la implicación y para las extensiones de la lógica lineal intuicionista. En tercer lugar, el célebre teorema de dicotomía de Blok demuestra que cada lógica modal normal comparte sus marcos de Kripke con exactamente 1 o 2(N)o lógicas. Caracterizar el número de lógicas que tienen los mismos conjuntos parcialmente ordenados de una extensión axiomática del cálculo proposicional intuicionista es un problema pendiente. Resolvemos esta cuestión en el caso de las lógicas implicativas, las extensiones axiomáticas del fragmento implicativo de la lógica intuicionista proposicional. En este caso, se cumple una tricotomía: cada lógica implicativa comparte sus conjuntos parcialmente ordenados exactamente con 1, o, o 2(No) lógicas.