Nils Köpp ; Iosif Petrakis - Strong negation in the theory of computable functionals TCF

lmcs:11400 - Logical Methods in Computer Science, April 4, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:1)2025
Strong negation in the theory of computable functionals TCFArticle

Authors: Nils Köpp ; Iosif Petrakis

We incorporate strong negation in the theory of computable functionals TCF, a common extension of Plotkin's PCF and Gödel's system $\mathbf{T}$, by defining simultaneously strong negation $A^{\mathbf{N}}$ of a formula $A$ and strong negation $P^{\mathbf{N}}$ of a predicate $P$ in TCF. As a special case of the latter, we get strong negation of an inductive and a coinductive predicate of TCF. We prove appropriate versions of the Ex falso quodlibet and of double negation elimination for strong negation in TCF. We introduce the so-called tight formulas of TCF i.e., formulas implied by the weak negation of their strong negation, and the relative tight formulas. We present various case-studies and examples, which reveal the naturality of our definition of strong negation in TCF and justify the use of TCF as a formal system for a large part of Bishop-style constructive mathematics.


Volume: Volume 21, Issue 2
Secondary volumes: Selected Papers of the Conference "Continuity, Computability, Constructivity: From Logic to Algorithms" (CCC 2022)
Published on: April 4, 2025
Accepted on: February 3, 2025
Submitted on: May 30, 2023
Keywords: Mathematics - Logic, Computer Science - Logic in Computer Science

Consultation statistics

This page has been seen 2226 times.
This article's PDF has been downloaded 810 times.