Hierarchy of arithmetical systems reveals role of negation principles

Arithmetical Characterizations of Two Intuitionistic Logical Principles

Logic in Computer Science

Summary

This paper studies how different ways of handling 'not' affect arithmetic logic systems. The authors introduce a basic arithmetic system with all primitive recursive functions and explore how adding two logical rules—one about negation and one about contradictions—changes what can be proven. They show that these systems build on each other, getting strictly stronger. Their work clarifies the connections between logic rules and arithmetic principles, and how certain functions are essential for weaker arithmetic.

What this means in practice

  • For proof system developers: Design logical frameworks that distinguish deductive strengths by controlling negation and contradiction rules to create tailored arithmetic proof systems.
  • For formal verification engineers: Develop verification tools that use minimal arithmetic logic with known deductive power to improve trustworthiness and understand when classical principles are necessary.

A theory result. No direct application yet.

Authors

Kaito Ichikura

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.