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.
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...
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· Electronic Proceedings in Th...· 0 citations
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· Australasian Journal of Logi...· 0 citations
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· Acta INFOLOGICA· 0 citations
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...
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· Bulletin of the Section of L...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.