Seminário de Lógica Matemática

Modified realizability and functional interpretations: some logical and mathematical observations (still continuation)

Sala 6.2.33, FCUL, Lisboa

Fernando Ferreira
CMAF-CIO, Faculdade de Ciências da Universidade de Lisboa

Abstract: We review some basic and well-known facts about the possibility of extracting computational information from proofs in classical, intuitionistic and semi-intuitionistic systems. Intuitionistic reasoning is tailored to have a clear constructive content and Kleene’s (numerical) realizability was a way of establishing precisely what this means for intuitionistic proofs in arithmetic. We review the variant of modified realizability due to Kreisel and see it as a form of a functional interpretation. An emphasis throughout is on the fact that there are some semi-intuitionistic principles which are amenable to computational extraction. Even Kreisel’s modified realizability displays not only the constructive content of intuitionistic logic but goes a bit further since it also realizes a certain (non-intuitionistic) principle of independence of premises. This principle is a characteristic principle of modified realizability. We explain what are these characteristic principles and compare them with so-called side principles, which are also amenable to computational extraction.

Markov’s principle is a characteristic principle of Gödel’s functional dialectica interpretation. We review the dialectica interpretation and also analyze Markov’s principle via the so-called Friedman’s trick. We make a short comparison between both treatments of Markov’s principle. We introduce a new interpretation (the H-interpretation: H for herbrandized) and see that LLPO (the lesser limited principle of omniscience) is one of its characteristic principles. The extraction of computational information now takes the form of bounds, not of precise witnesses. We discuss this issue and a monotonicity condition now so central in several recently defined functional interpretations. Finally, we extend the H-interpretation to the second-order arithmetical setting in such a way that WKL (weak König’s lemma) turns out to be a characteristic principle.

Some open questions and some projects will be discussed during the talk.

This seminar is supported by National Funding from FCT - Fundação para a Ciência e a Tecnologia, under the project: UID/MAT/04561/2013.

15h00
CMAF-CIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional
Logótipo do evento

No dia 04 de abril, pelas 14h30, será gravado um episódio em direto do podcast "A Escala do Clima" de Filipe Duarte Santos (Professor Jubilado de CIÊNCIAS).

Fotografia de coleção de insetos

The course includes several case studies of insect adaptation, and the most recent overview on insect evodevo, plasticity, ecophysiological responses and conservation under global change.

Fotografia de aluna

Uma iniciativa aberta a toda a comunidade académica da ULisboa.

A iniciativa, promovida pela Rede Campus Sustentável (da qual CIÊNCIAS faz parte), é direcionada para o incentivo à colaboração entre as pessoas que pertencem a estruturas existentes ou em fase de constituição.

Título/data/local do evento e fotografia aérea de vias urbanas

Conferência da redeMOV, por Gabriel Costa Valença.

Logótipo CIE

A leading venue for presenting and discussing the latest research, industrial practice and innovations in dependable and secure computing.

Seminário do Centro de Física Teórica e Computacional, por João Neves (CFTC).

Edição anterior da Jobshop Ciências

O maior evento de empregabilidade de CIÊNCIAS, a decorrer nos dias 08 e 09 de abril.

RSS Meetup, por Rodrigo Bruno (IST, ULisboa).

Título do evento

A collaborative initiative supported by five Portuguese research centers, aimed at strengthening and connecting the geometry research community in Portugal.

Equipa da Raiz Vertical Farms

Uma Experiência Única sobre Agricultura Urbana e Energia Renovável.

Título/data/local do evento e fotografia da cidade de Lisboa

The conference aims to bring together students and young researchers working in Mathematics, Statistics, and Applications with a view to fostering discussions and collaborations amongst participants.

Seminário do Instituto de Astrofísica e Ciências do Espaço, por Amidou Sorgho (Instituto de Astrofísica de Andalucía - IAA-CSIC, Spain).

Título/data/local do evento e representação de ser humano

Workshop de Medicina Nuclear, organizado pelo Instituto de Biofísica e Engenharia Biomédica.

Título "Para um ensino humanista das ciências" e logótipos das entidades organizadoras

O evento tem como tema principal "Para um ensino humanista das ciências" e conta com a participação de vários professores de CIÊNCIAS.

Microplásticos em suspensão no oceano

O curso tem como objetivo dar formação sobre a problemática da contaminação por detritos de plástico dos nossos ecossistemas, bem como alertar para os potenciais efeitos deletérios nos organismos - candidaturas até 22 de março.

Banner do Dia de Ciências 2025

A 29 de abril assinalamos o 114.º aniversário de CIÊNCIAS.

Junte-se a nós no Grande Auditório de CIÊNCIAS para uma tarde de celebração que reúne toda a comunidade da Faculdade.

Fotografia de fábrica a emitir poluição para a atmosfera

The course aims at enabling the participants to use different methods to measure the impacts of pollutants on ecosystems.

Logótipo C-Academy

O curso oferece uma base sólida sobre os fundamentos e práticas essenciais para proteger sistemas e dados num mundo cada vez mais digital - candidaturas até 13 de abril.

Banner Dia Aberto de CIÊNCIAS 2025.

Bem-vindos a Ciências ULisboa!

Um concurso de programação dirigido aos alunos do ensino secundário (11.º e 12.º anos), que visa promover a prática e o gosto pela programação.

Fotografia de Chapim-azul

The goal of this course is to provide the participants with the most recent and practical knowledge on the use of Functional Diversity.

Mão a segurar em globo de vidro

Curso acreditado pelo CCPFC para efeitos de progressão na carreira dos professores na dimensão cientifico-pedagógica dos grupos 230, 420, 510, 520 e 560, com candidaturas até 30 de abril.

Título/data/local do evento, logótipos das entidades organizadoras e fotografia de peixe

The event aims to facilitate the exchange of information and knowledge among professionals to advance the understanding, collaboration and capabilities of aquaculture to respond to the impact of climate change in a rapidly changing global environment.

Uma oportunidade única para interagir com a comunidade global de computação científica, com inscrições (preço reduzido) até 02 de maio.

Páginas