Skip to content
Open access

Arithmetical Characterizations of Two Intuitionistic Logical Principles

Oct 2026 · Electronic Proceedings in Theoretical Computer Science · Vol 455, pp. 21-31 · 0 citations · 13 references
Computer Science

Abstract

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.

Read PDF

Similar papers

Preprint Nov 2026

Arithmetical and set-theoretic semantics of the logic of problems and propositions

Kolmogorov interpreted intuitionistic logic as a calculus of problems and later remarked that a complete treatment should deal with problems and propositions together. Melikhov's logic HC is such a joint two-sorted system: it combines classical propositions with intuitionistic problems by means of two modalities, the p...

A. Onoprienko, N. Vereshchagin · 0 citations
Open access Oct 2026

Restricted Peirce's Law and Natural Deduction

The constructive logic JP'is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by...

Satoru Niki · 0 citations
Open access Sep 2026

Model-Theoretic Inferentialism and Paraconsistency in Multiple-valued Structures

Carnap [5] in 1943 noticed that there exist some non-normal valuations that do not respect the usual truth conditions of classical connectives, yet are sound. This finding reveals an asymmetry between the syntax and semantics of classical logic and might be counted as a challenge to the inferentialist program. While se...

Javid Jafari, D. Hosseini · 0 citations
Open access Nov 2026

Operators in Two-Valued Symbolic Logic

In this study we ask how logical systems are built in two-valued symbolic logic and which logical operator(s) should be taken as primitive. There are three criteria which are usually used to justify the choice of implication. These are functional completeness, inferential naturalness, and axiomatic economy. We show tha...

İbrahim Halil Çetres, Vedat Kamer · 0 citations
Preprint Oct 2026

Inductive Grounded Arithmetic: Goodstein, the Hydra, and $\Gamma_0$

What does a recursive definition mean in a grounded logic, where a sentence is true only if a terminating process makes it so? This paper takes Kripke's answer for truth, the least fixed point, as a rule. Reflective Grounded Arithmetic (RGA) writes any recursive definition as one self-referential term; Inductive Ground...

B. Ford · 0 citations
Review Open access Oct 2026

Universal Constructions for Identity and Number

The scheme that Gentzen designed to specify the definitions of logical connectives has a wider reach than is usually recognized, extending naturally to terms that Gentzen did not treat explicitly, including predicate symbols.  After explaining (§2) how the introduction and elimination rules of natural deduction calculi...

Curtis Franks · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.