Arithmetical Characterizations of Two Intuitionistic Logical Principles
Electronic Proceedings in Theoretical Computer Science · 2026-10-26 · 455 · 21-31
DOI: 10.4204/eptcs.455.3 ↗At a glance
Journal article in Electronic Proceedings in Theoretical Computer Science, published online on 2026-10-26. Written by Kaito Ichikura.
Abstract (original language)
This paper investigates the role of negation in arithmetic by analyzing subsystems based on subminimal logic. We introduce NA^PR, a system of subminimal arithmetic equipped with all primitive recursive functions, and answer the following four questions: (1) Can we develop reasonable arithmetic within NA^PR? (2) Can we characterize logical rules Absorption of Negation (An) and Ex Falso Quodlibet (ECQ) by arithmetical principles? (3) Are there strict differences in deductive power among NA^PR, MA^PR, and HA? (4) Do MA^PR and MA, and NA^PR and NA have a similar mutual interpretability relationship as HA? We show the following: First, Heyting Arithmetic (HA) is shown to be a conservative extension of NA^PR for positive formulas. Based on NA^PR, we prove that (ECQ) is equivalent to the definability of disjunction, and that (An) is equivalent to a variant of the least number principle. Furthermore, using the constant domain neighbourhood semantics, we show that the systems NA^PR, MA^PR (written as NA^PR+(An)) and HA (written as NA^PR+(An)+(ECQ)) form a strictly increasing hierarchy of strength. Finally, we demonstrate the essential role of primitive recursive functions in weak arithmetic using classical countermodels.
Cite
APA
Ichikura, K. (2026). Arithmetical Characterizations of Two Intuitionistic Logical Principles. Electronic Proceedings in Theoretical Computer Science, 455, 21-31. https://doi.org/10.4204/eptcs.455.3
Vancouver
Ichikura K. Arithmetical Characterizations of Two Intuitionistic Logical Principles. Electronic Proceedings in Theoretical Computer Science. 2026;455:21-31. doi:10.4204/eptcs.455.3
BibTeX
@article{Ichikura2026,
author = {Ichikura, Kaito},
title = {Arithmetical Characterizations of Two Intuitionistic Logical Principles},
journal = {Electronic Proceedings in Theoretical Computer Science},
year = {2026},
volume = {455},
pages = {21--31},
doi = {10.4204/eptcs.455.3}
}
EUVIMED