Multi-dimensional interpretations of Presburger arithmetic in itself

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00536783" target="_blank" >RIV/67985840:_____/20:00536783 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1093/logcom/exaa050" target="_blank" >https://doi.org/10.1093/logcom/exaa050</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1093/logcom/exaa050" target="_blank" >10.1093/logcom/exaa050</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Multi-dimensional interpretations of Presburger arithmetic in itself

Popis výsledku v původním jazyce

Presburger arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by Visser (1998, An overview of interpretability logic. Advances in Modal Logic, pp. 307–359). In order to prove the result, we show that all linear orderings that are interpretable in (N,+) are scattered orderings with the finite Hausdorff rank and that the ranks are bounded in the terms of the dimensions of the respective interpretations.

Název v anglickém jazyce

Multi-dimensional interpretations of Presburger arithmetic in itself

Popis výsledku anglicky

Presburger arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by Visser (1998, An overview of interpretability logic. Advances in Modal Logic, pp. 307–359). In order to prove the result, we show that all linear orderings that are interpretable in (N,+) are scattered orderings with the finite Hausdorff rank and that the ranks are bounded in the terms of the dimensions of the respective interpretations.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA19-05497S" target="_blank" >GA19-05497S: Složitost matematických důkazů a struktur</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

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

Journal of Logic and Computation

ISSN

0955-792X

e-ISSN

—

Svazek periodika

30

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

13

Strana od-do

1681-1693

Kód UT WoS článku

000606031500011

EID výsledku v databázi Scopus

2-s2.0-85099385476