29/11/2017 – Hendrick Maia

Complexidade Computacional entre Espaços Topológicos e Lógica

Hendrick Maia
Universidade Estadual de Campinas-UNICAMP

Abstract

      Uma das principais características do trabalho matemático no século XX foi a abordagem de problemas da Teoria dos Números, como as conjecturas de Weil, sendo dada por meio de métodos geométricos, e os problemas geométricos, por sua vez, sendo tratados por meio de ferramentas altamente abstratas. Algumas dessas ferramentas foram desenvolvidas por Alexander Grothendieck. Trata-se de um dos mais belos e elegantes edifícios da matemática contemporânea. O alcance do trabalho de Grothendieck tem se mostrado muito mais amplo do que o campo para o qual foi desenvolvido, e, por certo, as consequências e aplicações de seus desenvolvimentos não foram ainda suficientemente exploradas. Dentre tais consequências surge uma conexão impensável, nas palavras de Saunders Mac Lane: “Um aspecto surpreendente da teoria de toposes é que ela unifica dois campos matemáticos aparentemente totalmente distintos: por um lado, topologia e geometria algébrica, e por outro, lógica e teoria de conjuntos”([9], Prólogo). A minha proposta é, então, explorar essa conexão no âmbito da Teoria da Complexidade Computacional.
O principal objetivo do programa da Teoria da Complexidade Descritiva[7, 8] é caracterizar complexidade computacional do ponto de vista da lógica (sendo mais preciso, da Teoria de Modelos), ou seja, para cada nível de complexidade importante, o programa objetiva fornecer sistemas lógicos cujo poder expressivo (sobre estruturas finitas, ou sobre um domínio particular de estruturas finitas) coincida exatamente com esse nível de complexidade. A ideia é estabelecer resultados afirmando que, dado um domínio D de estruturas, uma lógica L, e uma classe de complexidade Comp, L captura Comp sobre D. Isso significa duas coisas: (i) para cada sentença fixada ψL, a complexidade de dados de avaliar ψ sobre as estruturas de D é um problema na classe de complexidade Comp; e (ii) cada propriedade das estruturas em D que pode ser decidida com complexidade Comp é definível na lógica L. Intuitivamente, L captura Comp sobre D se as propriedades de estruturas L-definíveis são precisamente aquelas que são decidíveis em Comp. O meu objetivo é usar uma parte do imenso maquinário abstrato desenvolvido por Grothendieck para tentar investigar as relações entre classes de complexidade capturadas por lógicas do ponto de vista da conexão entre espaços topológicos e lógica. Eu irei utilizar duas abordagens relacionáveis. A primeira é a Teoria dos Feixes de Estruturas, desenvolvida por Xavier Caicedo [4], a qual foi baseada nos trabalhos de Grothendieck. Feixes de estruturas são governados por uma lógica intermediária entre a lógica intuicionista e a lógica clássica, e essa intermediação, por sua vez, é dada pelas propriedades dos espaços topológicos que determinam o feixe, ou seja, as propriedades dos espaços determinarão o quão próxima ou distante de cada lógica estará a lógica intrínseca do feixe. Por exemplo, dado um feixe de estruturas p : EX, onde E e X são espaços topológicos, a validade do terceiro-excluído é determinada num ponto x do espaço base do feixe se, e somente se, existir uma vizinhança U de x tal que p-1(U) é um espaço de Hausdorff. Ou seja, a propriedade de Hausdorff no espaço E em determina a validade do terceiro-excluído na lógica do feixe p. Outro exemplo diz respeito à topologia do espaço base: 𝔄⊩x ¬¬φ[σ1, …,σn](lê-se “o feixe de estruturas 𝔄 força [σ1, …,σn] no ponto xX para seções σ1, …,σn de 𝔄 definidas no ponto xX“) se, e somente se, existe uma vizinhança aberta U de x tal que {yU : 𝔄⊩yφ[σ1, …,σn]} é denso em U. Isso significa exatamente que propriedades de espaços topológicos determinam propriedades lógicas. Assim, a ideia é investigar as relações entre classes de complexidade por meio das propriedades de espaços topológicos que definem as propriedades de lógicas que capturam as classes em questão.
A segunda abordagem diz respeito a um desenvolvimento direto de Grothendieck que revolucionou a geometria algébrica, a saber, a Teoria dos Esquemas [5, 6]. Cada anel comutativo determina um esquema afim consistindo de um par (Spec(R),OR), onde Spec(R) é um espaço topológico (o espectro do anel R) e OR é um feixe de anéis locais (o feixe estrutural). Assim, um esquema codifica dados geométricos e algébricos. Steve Awodey e Spencer Breiner[1, 3] têm desenvolvido “esquemas lógicos”, entidades geométricas que representam teorias no mesmo sentido em que esquemas algébricos representam anéis. Esquemas lógicos são constituídos de um espaço espectral semântico e um feixe estrutural sintático. Por exemplo, cada fórmula φ(x1, …,xn) determina um “feixe definível” ‖φ‖ sobre o espectro, de tal modo que em cada ponto do espectro (um modelo M), a fibra de ‖φ‖ sobre M é o conjunto definível {ā ∈ |M|n: M ⊨ φ(ā)}. Como veremos, o problema sobre computar conjuntos definíveis, chamado “problema de avaliar uma fórmula”, está intimamente ligado a problemas de model-checking, que possuem um papel central na Teoria da Complexidade Descritiva: se o problema de avaliar é dado para uma fórmula com k variáveis livres sobre uma estrutura com n elementos, então tal problema é redutível a nk problemas de model-checking. Assim, nessa segunda abordagem, meu objetivo é tentar utilizar o maquinário da Teoria dos Esquemas de Grothendieck (desenvolvendo a adaptação de Awodey e Breiner) na Teoria da Complexidade Descritiva, desde que é possível construir uma 2-categoria de esquemas lógicos que compartilha algumas das úteis propriedades de esquemas algébricos.

Keywords: Espaços Topológicos, Lógica, Complexidade Computacional.

1. Referências
[1 ] AWODEY, S. BREINER, S. 2014, Scheme representation for first-order logic. In: Nikolaos Galatos, Alexander Kurz and Constantine Tsinakis (editors). TACL 2013. Sixth International Conference on Topology, Algebra and Categories in Logic, vol 25, pages 10-13.
[2 ] BORCEUX, F. 1994, Handbook of categorical algebra, Encyclopedia of Mathematics Series, Cambridge University Press, 3 vols.
[3 ] BREIMER, S. 2014, Scheme representation for first-order logic. PhD thesis, Carnegie Mellon University.
[4 ] CAICEDO, X. 1995, Logica de los haces de estructuras (The logic of sheaves of structures). Rev. Acad. Colombiana Cienc. Exact. Fís. Natur. 19, no. 74, 569-586.
[5 ] EISENBUD, D. HARRIS, J. 2000, The geometry of schemes. Springer-Verlag, New York.
[6 ] GÖRTZ, W. 2010, Algebraic Geometry I, Schemes with Examples and Exercises. Springer Science e Business Media.
[7 ] GRÄDEL, E. 2007, Finite Model Theory and Descriptive Complexity.
In Finite Model Theory and Its Applications, pp. 125-230. Springer-Verlag.
[8 ] IMMERMAN, N. 1995, Descriptive Complexity: a Logician’s Approach
to Computation in Notices of the American Mathematical Society, fi1127 -1133
[9 ] MAC LANE, S; MOERDIJK, I. 1992, Sheaves in Geometry and Logic: A first introduction to topos theory. Springer Verlag, New York Inc.

Anúncios

22/11/2017- Aldo Figallo-Orellano

Non-deterministic algebraization of logics by swap structures

Aldo Figallo-Orellano
Departament of Mathematics, National University of the South, Bahia Blanca, Argentina
and
Centre for Logic, Epistemology and The History of Science, University of Campinas, Campinas, SP, Brazil.
e-mail: aldofigallo@gmail.com

This is a joint work with Marcelo Esteban Coniglio and Ana Claudia Golzio, see [4]. Multialgebras (or hyperalgebras, or non-deterministic algebras) have been very much studied in Mathematics and in Computer Science. A semantics based on an special kind of multialgebra called swap structure was proposed in [3, Chapter 6], which generalizes the characterization results of LFIs by means of nite Nmatrices due to Avron (see [1]). Moreover, the swap structures semantics allows soundness and completeness theorems by means of a very natural generalization of the well-known Lindenbaum-Tarski process. In 2016, Carnielli and Coniglio introduced swap structures as a semantic framework for dealing with several logics of formal inconsistency (or LFIs) which cannot be semantically characterized by a single finite matrix. In particular, these LFIs are not algebraizable by the standard tools of abstract algebraic logic. In this paper, the first steps towards a theory of non-deterministic algebraization of logics by swap structures are given. Specifically, a formal study of swap structures for LFIs is developed, by adapting concepts of universal algebra to multialgebras in a suitable way. A decomposition theorem similar to Birkhoff’s representation theorem is obtained for each class of swap structures. Moreover, when applied to the 3-valued algebraizable logic J3 the usual class of agebraic models is recovered, and the swap structures semantics became twist-structures semantic(as introduced by Fidel-Vakarelov). These twist-structures semantics are semisimple Nelson algebras which is polynomially equivalent to the variety of MV-algebras of order 3 (see [5]). In the case of the algebraizable 3-valued logic J3, our representation theorem coincides with the original Birkhoff’s representation theorem. Moreover, the swap structures became twist structures in the sense of Fidel [6] and Vakarelov [7]. This fact, together with the existence of a functor from the category of Boolean algebras to the category of swap structures for each LFI, which is closely connected with Kalman’s functor, suggests that swap structures can be considered as non-deterministic twist structures.

References

[1] A. Avron. Non-deterministic matrices and modular semantics of rules. In J.-Y. Beziau, editor, Logica Universalis, pages 149-167. Birkhauser Verlag, 2005.
[2] W. A. Carnielli, M. E. Coniglio, and J. Marcos. Logics of Formal Inconsistency. In: D. M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic (2nd. edition), volume 14, pages 1-93. Springer, 2007.
[3] W. A. Carnielli and M. E. Coniglio. Paraconsistent Logic: Consistency, Contradiction and Negation. Volume 40 of Logic, Epistemology, and the Unity of Science. Springer, 2016.
[4] M. E. Coniglio, A. Figallo-Orellano and A. C. Golzio, Non-deterministic algebraization of logics by swap structures, submitted.arXiv:1708.08499 [math.LO]
[5] R. Cignoli. The class of Kleene algebras satisfying an interpolation property and Nelson algebras. Algebra Universalis, 23, 262-292, 1986.
[6] M. M. Fidel. An algebraic study of a propositional system of Nelson. In A. I. Arruda, N. C. A. da Costa, and R. Chuaqui, editors, Mathematical Logic. Proceedings of the First Brazilian Conference on Mathematical Logic, Campinas 1977, volume 39 of Lecture Notes in Pure and Applied
Mathematics, pages 99-117. Marcel Dekker, 1978.

[7] D. Vakarelov. Notes on N-lattices and constructive logic with strong
negation. Studia Logica, 36(1-2):109-125, 1977.

08/11/2017 – Paniel Reyes

Philosophical aspects of the Riemann Hypothesis and its critical strip

Paniel Reyes-Càrdenas
UPAEP, puebla, Mexico

Throughout his lifetime, Riemann only published one paper on Number theory. This document was enough to challenge the minds of his and our own time (we still have the problem of this hypothesis in the Millennium  Prize list). However, little has been said about the philosophical consequences of the hypothesis contained here, the Zeta function and the so-called critical strip. What kind of assumptions has this to the nature of number theory and of mathematical thought in general? In this talk I will explore some ideas that spin out from these problems and will relate them to the problems of applicability and mathematical realism.

25/10/2017 – Rogério Júnior

Modalidades paraconsistentes como possibilidade de tratamento para Paradoxos Epistêmico-Doxásticos
 

Os Paradoxos da Cognoscibilidade(ou de Fitch) e da Credibilidade são resultados indesejados das lógicas modais alético-epistêmicas e alético-doxásticas, que causam o colapso dos operadores de conhecimento e crença, respectivamente. Algumas soluções foram propostas para tratá-los, dentre elas, a de rejeitar alguns pressupostos, como por exemplo, o Princípio da Cognoscibilidade. Neste contexto, nosso trabalho segue outra tendência, a saber, que busca dotar os sistemas nos quais os Paradoxos ocorrem de bases paraconsistentes. O aparato lógico pretendido para esta tarefa são os sistemas catódicos, sistemas modais contendo em sua linguagem negações subclássicas, que podem ser vistos como combinações entre lógicas modais e paraconsistentes. Em particular averiguamos a possibilidade de algumas Lógicas da Inconsistência Formal (LFIs), em constituir sistemas catódicos promissores para tratar os Paradoxos.

Referências:
ALMEIDA, Dante Cardoso Pinto de. A Persistência do Paradoxo da Cognoscibilidade.
Dissertação de Mestrado, IFCH – Unicamp. Campinas, SP, Brasil, 2011, pp. 1-74.
 
BUENO, J.: Multimodalidades Anódicas e Catódicas: a negação controlada em lógicas
multimodais e seu poder expressivo. Tese (doutorado) – Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas, Brasil, 2009, pp. 1-135.
 
CARNIELLI, W. A.; CONIGLIO, M. E. ; MARCOS, J.: Logics of Formal Inconsistency. In Gabbay, D. e F. Guenthner (editores): Handbook of Philosophical Logic, Vol. 14, Amsterdã, 2007. Springer-Verlag, pp. 1-41.
 
COSTA-LEITE, A.: Paraconsistência, Modalidades e Cognoscibilidade. Dissertação de
Mestrado, IFCH-Unicamp, Campinas, SP, Brasil, 2003, pp.1-98.
 
HINTIKKA, J.: Knowledge and Belief: an introduction to the logic of the two notions. Cornell University Press, 1962.
 
MORTARI, C. A.: Lógicas epistêmicas, In: Nos Limites da Epistemologia Analítica, UFSC, Florianópolis, 1999, pp. 17- 68.

11/10/2017 – Vincenzo Cicarelli

Identidade de proposição no princípio de Hume

De acordo com a definição implícita de número natural dada por Frege nos Fundamentos da aritmética (Princípio de Hume), uma sentença que expressa a identidade entre dois termos númericos tem o mesmo conteúdo conceptual de uma sentença que expressa a correspondência um a um entre dois conceitos. No caso de dois conceitos individuados pelas fórmulas abertas Fx e Gx, a sentença “o número do conceito Fx = o número do conceito Gx” expressa o mesmo conteúdo conceptual da sentença “existe uma relação (de segunda ordem) um a um entre Fx e Gx”.
Se interpretarmos identidade de conteúdo conceptual como identidade de proposição expressa, e se aplicarmos a clássica teoria das proposições como conjuntos de mundos possíveis (que podemos chamar de teoria lewisiana), a relação de identidade de conteúdo conceptual coincide com a relação de equivalência material. Uma consequência indesejada disto é que se interpretarmos o Princípio de Hume numa semântica dos mundos possíveis para uma linguagem de segunda ordem que incluia o operador de cardinalidade, os termos que referem-se aos números naturais não têm a mesma interpretação em todos os mundos possíveis: em outra palavras, nada garante que o número 2 no mundo W seja o mesmo que o número 2 no mundo W´.
Nesta fala será apresentado o rascunho de um argumento cujo objetivo é provar que os termos numéricos são designadores rígidos: este objetivo pode ser alcançado sem desistir da teoria lewisiana das proposições.

Três ideias fundamentais serão apresentadas: (1) existem proposições de equinumerosidade (correspondência um a um) que não são representáveis linguisticamente, (2) elas são obtidas como resultado de uma generalização da ideia de proposição como condição sobre mundos possíveis, (3) a identidade numérica correspondente a este tipo de proposição garante a designação rígida dos termos numéricos.
A primeira ideia é baseada na aplicabilidade universal das relações lógicas; por exemplo, a relação de equinumerosidade não se aplica apenas entre conceitos que existem no mesmo mundo possível mas também entre conceitos existentes em diferentes mundos possíveis. Para justificar o status de proposição de uma equinumerosidade “trans-mundana” (a segunda ideia) precisaremos generalizar a teoria lewisiana das proposições: assim como uma proposição pode ser vista como uma predicação sobre um dado mundo W, ou como uma quantificação sobre mundos possíveis (no caso em que a sentença associada contenha operadores modais), uma relação entre mundos possíveis também representa uma proposição. E uma equinumerosidade entre conceitos existentes em diferentes mundos possíveis pode ser representada como um conjunto de pares ordenados de mundos possíveis, isto é uma relação “transmundana”. Uma vez que as condições de verdade de uma equinumerosidade trans-mundana serão definidas, provaremos que, em alguns casos específicos, a identidade numérica associada para esta proposição é a identidade de interpretação dos termos numéricos em diferentes mundos possíveis.

04/10/2017 – Gesiel Borges

 

Axiomatic approach to the problem of theodicy

O problema do mal e as teodiceias tem uma longa história na tradição filosófica. No contexto desta problemática, alguns autores contemporâneos desenvolveram seus argumentos valendo-se da lógica formal. Pretendemos apresentar uma destas abordagens, a saber, aquela desenvolvida por Nieznanski (2007)¹, na qual o filósofo e lógico polonês desenvolve um sistema axiomático no âmbito do problema da teodiceia. Motiva-nos particularmente o estudo e emprego de métodos formais, os quais, por meio de procedimentos efetivos e de uma linguagem precisa, que evita ambiguidades, favorecem a clareza da argumentação e do entendimento.

Referência
¹NIEZNAŃSKI, E. Aksjomaticzne ujecie problemu teodycei (Axiomatic approach to the problem of theodicy). Roczniki Filosoficzne 2007, LV(1), pp 201-217.

23/08/2017 – German Tadeo Gómez

Semantics of triples for the first-order paraconsistent logic QCiore
M. Coniglio*, G. T. Gomez** and M. Figallo**
*Department of Philosophy – IFCH, University of Campinas, Brazil
e-mail: coniglio@cle.unicamp.br
**Departament of Mathematics, National University of the South, Bahia Blanca, Argentina
e-mail: {tadeogerman, figallomartin}@gmail.com

In this talk the logic QCiore is introduced as a first-order version of the 3-valued paraconsistent proposicional logic LFI2, introduced in [2] and additionally studied in [1]under the name of Ciore. As semantical counterpart for QCiore we consider the so-called LFI2-structures, which are defined as 〈A| · |LFI2〉, such that A is a partial structure as introduced in [3], and      | · |LFI2 is a mapping which assigns to each formula of the language of QCiore a partial set over the set of all the variable assingments in the domain of A, where Μ is the logical matrix of Ciore. Soundness and Completeness theorems for QCiore with respect to LFI2-structures are obtained.

Additionally, several notions from model theory such as morphism, elementary equivalence and elementary sub-structure (among others) are introduced for LFI2-structures. Based on this, suitable versions of classical results of Model Theory such as the Tarski-Vaught Theorem, the Downward Löwenheim-Skolem Theorem and the Elementary Chain Theorem are obtained. Finally, a proper formulation of the notions of diagram and elementary diagram allows us to characterize embeddings and elementary embeddings. Using this, the Elementary Amalgamation Theorem is proved. As a consequence of these results, the Robinson’s Consistency Theorem and the Craig’s Interpolation Theorem are proved.

References
[1] W.A. Carnielli and M.E. Coniglio. Paraconsistent Logic: Consistency, Contradiction and Negation. Volume 40 in the Logic, Epistemology, and the Unity of Science Series. Springer, 2016.
[2] W. A. Carnielli, J. Marcos, and S. de Amo. Formal inconsistency and evolutionary databases. Logic and Logical Philosophy, 8:115-152, 2000.
[3] M. E. Coniglio and L. H. Silvestrini. An alternative approach for quasitruth. Logic Journal of the IGPL, 22(2):387-410, 2014.