25/04/2018 – Mattia Petrolo

A proof-theoretic analysis of paradoxes

Mattia Petrolo (CCNH, UFABC)

Abstract. A proof-theoretic criterion for paradoxicality was famously proposed by Tennant: a paradox must yield a closed derivation of absurdity with no normal form. Drawing on the observation that all derivations of a given proposition can be transformed into derivations in normal form of a logically equivalent proposition, we investigate the possibility of paradoxes in normal form. We compare paradoxes à la Tennant and paradoxes in normal form from the viewpoint of the computational interpretation of proofs. (Joint work with Paolo Pistone).

Anúncios

11/04/2018 – Bruno Mendonça

Urn semantics, semantic information and the scandal of deduction

Bruno R Mendonça (Unicamp/ CNPq)

Abstract. In this talk I present a general theory of semantic information without the so-called scandal of deduction, a thesis according to which logical truths carry null-amount of information. This general theory is obtained from the traditional theory of semantic information (originally proposed by Bar-Hillel and Carnap (1953)) by replacing classical logic by urn semantics (Rantala 1979) as a privileged metatheory. In this sense, I present some interesting formal properties of urn semantics (such as decidability and completeness results) and present a philosophical justification for using this system as a metatheory of semantic information. In order to do this, I explore the equivalence between the scandal of deduction and logical omniscience, a classical consequence of normal systems of epistemic logic. Given that the problems of logical omniscience and the scandal of deduction can be solved based on a correct account of epistemic possibility, I argue that urn semantics, by providing a nice analysis of this concept, is an adequate ground for a theory of semantic information.

04/04/2018 – Alejandro Hernandez

 

A Hilbert-type axiomatic system for CG’3

 

The CG’3  logic is a three-valued paraconsistent logic of recent creation, introduced in 2014 by Osorio et al. by means of multi-valued semantics. The definitions of  CG’3 and G’3  by means of many valued matrix are very close, actually the only difference is that the sets of designated values are diferent; {1, 2} for CG’3 and {1} for G’3 .

In 2016 Borja et al. define a Kripke-type semantics for CG’3 in two different ways. In this talk we continue and extends that work providing a Hilbert-type axiomatic system for CG’3. It is shown that this formal axiomatic theory L is sound and complete with respect to CG’3.

28/03/2018 – João Toniolo

 

A auto-afirmação do cognoscente e o problema cético de Agripa

João Toniolo (CLE/IFCH – Unicamp)
Seminários do Programa (CLE) – 28/03/2018

 

O presente trabalho lida com uma versão contemporânea do problema cético de Agripa. Tal problemática é particularmente conhecida na tradição analítica como “problema do regresso epistêmico” ou “trilema de Agripa”. Nessa abordagem, tal tipo de ceticismo é visto como um desafio à justificação de nossas crenças (e.g. Williams, 2004; Fogelin, 1994). Colocadas no desafio, reivindicações de conhecimento inevitavelmente cairiam ou 1) em um regresso infinito, ou 2) em raciocínio circular ou 3) em uma assunção arbitrária, e tais são os modos do trilema. No entanto, trabalhos mais recentes (Lammenranta, 2008; Machuca, 2015; Williams, 2015) apontam para o fato de que a referida abordagem não constitui um sério desafio cético. Isso porque, entre outros, além dos modos de regresso infinito, raciocínio circular e assunção, há também os modos da discrepância e relatividade. Considerados em conjunto, tais modos são estratégias céticas para levar à suspensão do juízo. Assim como no trilema, as reivindicações de conhecimento colocadas nos cinco modos cairiam em um deles e o ceticismo seria inevitável.
Dentre formulações recentes da problemática, tomamos aquela oferecida por Lammenranta (2008). Nesta apresentação, então, procuramos responder a algumas perguntas: Como evitar esse tipo de ceticismo? E como bloquear a argumentação cética? Para isso, o objetivo do trabalho é oferecer uma resposta à problemática com base na teoria cognitiva e na teoria do conhecimento de Bernard Lonergan. Isso será feito a partir da tese da auto-afirmação do cognoscente, presente no Insight: a study of human understanding (1957(1992)), sua principal obra. Há ao menos dois modos de responder ao problema, um direto e outro indireto. Para esta apresentação, centramo-nos no modo direto, que revela certo caráter puzzling do problema.

21/03/2018 – Rodolfo C. Ertola-Biraben

Distributivity in logic and algebra
Rodolfo C. Ertola-Biraben (UNICAMP)
Abstract Talk CLE March 21, 2018 16:00

The present talk is the second part of a talk given last year. We had shown that the algebraic translation of the concept of distributivity given by Gentzen’s rules with only disjunction, corresponds to the join-semilattice version of the notion of distributivity for posets given by Larmerová and Rachůnek in 1988, which will be denoted (LR). In particular, we saw that Grätzer and Schmidt’s notion (G) of 1962 is stronger, not allowing for finite examples that are not lattices.
We will begin reminding the audience of the contents of the previous talk. Afterwards, we will see that there are infinite notions of distributivity for semilattices. Notion (G) is the strongest of the notions we have found so far. Then, we have a notion by Katriňák in 1968, the already mentioned (LR), and also a notion by Balbes in 1969. Finally, there are infinite notions given by Schein in 1972. We will see that the given notions are linearly ordered. Also, we will talk about the corresponding counterexamples in order to see that they are not equivalent.

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.

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.