The provably total functions of basic arithmetic and its extensions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F25%3A00617052" target="_blank" >RIV/67985840:_____/25:00617052 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00153-024-00939-0" target="_blank" >https://doi.org/10.1007/s00153-024-00939-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00153-024-00939-0" target="_blank" >10.1007/s00153-024-00939-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The provably total functions of basic arithmetic and its extensions

Popis výsledku v původním jazyce

We study Basic Arithmetic, BA introduced by Ruitenburg (Notre Dame J Formal Logic 39:18–46, 1998). BA is an arithmetical theory based on basic logic which is weaker than intuitionistic logic. We show that the class of the provably total recursive functions of BA is a proper sub-class of the primitive recursive functions. Three extensions of BA, called BA+U, BAc and EBA are investigated with relation to their provably total recursive functions. It is shown that the provably total recursive functions of these three extensions of BA are exactly the primitive recursive functions. Moreover, among other things, it is shown that the well-known MRDP theorem does not hold in BA, BA+U, BAc, but holds in EBA.

Název v anglickém jazyce

The provably total functions of basic arithmetic and its extensions

Popis výsledku anglicky

We study Basic Arithmetic, BA introduced by Ruitenburg (Notre Dame J Formal Logic 39:18–46, 1998). BA is an arithmetical theory based on basic logic which is weaker than intuitionistic logic. We show that the class of the provably total recursive functions of BA is a proper sub-class of the primitive recursive functions. Three extensions of BA, called BA+U, BAc and EBA are investigated with relation to their provably total recursive functions. It is shown that the provably total recursive functions of these three extensions of BA are exactly the primitive recursive functions. Moreover, among other things, it is shown that the well-known MRDP theorem does not hold in BA, BA+U, BAc, but holds in EBA.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Archive for Mathematical Logic

ISSN

0933-5846

e-ISSN

1432-0665

Svazek periodika

64

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

53

Strana od-do

205-257

Kód UT WoS článku

001290663900001

EID výsledku v databázi Scopus

2-s2.0-85201190493