• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Interpretations of presburger arithmetic in itself(
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
May 25, 2026
HSE Scientists Train Neural Network to 'Hear' Faults in Electric Motors
Researchers at the AI and Digital Science Institute of the HSE Faculty of Computer Science have developed a new method—the Signature-Guided Data Augmentation (SGDA) framework—that achieves 99% accuracy in motor fault detection and 86% accuracy in fault classification. The application of this approach can reduce industrial equipment repair costs, minimise downtime, and improve production safety. The study results have been published in Engineering Applications of Artificial Intelligence.
May 25, 2026
'The Humanities Serve as a Conscience'
Maria Mizernaia studies Soviet literature and the history of book publishing. In this interview for the HSE Young Scientists project, she discusses plans to publish a novel about besieged Leningrad, AI-provoked reflections on what it means to be human, and how novels can help satisfy our dopamine hunger.
May 25, 2026
Is It Possible to Predict a Citys Life Based on the Shape of Its Neighbourhoods?
Is it possible to predict, based on the configuration of streets and buildings, where a café will open or where traffic congestion will occur? Participants in the Spatial Analysis and Modelling of Urban Processes research and study group use open data and machine learning to identify universal patterns. Alexander Sheludkov and Eduard Somov discuss the purpose of comparing cities, the need for new forms of urban statistics, and how open data is transforming approaches to urban studies.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Interpretations of presburger arithmetic in itself(

P. 354–367.
Zapryagaev A., Pahomov F.

Presburger arithmetic PrA is the true theory of natural numbers with addition. We study interpretations of PrA in itself. We prove that all one-dimensional self-interpretations are definably isomorphic to the identity self-interpretation. In order to prove the results we show that all linear orders that are interpretable in (N,+) are scattered orders with the finite Hausdorff rank and that the ranks are bounded in terms of the dimension of the respective interpretations. From our result about self-interpretations of PrA it follows that PrA isn’t one-dimensionally interpretable in any of its finite subtheories. We note that the latter was conjectured by A. Visser.

Language: English
DOI
Text on another site
Keywords: Presburger ArithmeticInterpretations

In book

International Symposium on Logical Foundations of Computer Science, LFCS 2018
Vol. 10703. , Springer, 2018.
Similar publications
Some properties of Büchi Arithmetics
Zapryagaev A., / Series arXiv "math". 2023.
Büchi arithmetics BA_n, n≥2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. A rank of a linear order is the minimal number of condensations required to reach a finite order. We show that linear orders of arbitrarily large finite rank can be interpreted in BA_n. We also prove that the extension ...
Added: October 25, 2023
Об интерпретациях арифметики Пресбургера в арифметиках Бюхи
Zapryagaev A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 510 С. 3–7
Büchi arithmetics BAn, , are extensions of Presburger arithmetic with an unary functional symbol denoting the largest power of n that divides x. Definability of a set in BAn is equivalent to its recognizability by a finite automaton receiving numbers in their n-ary expansion. We consider the interpretations of Presburger Arithmetic in the standard model of BAn and ...
Added: July 27, 2023
К вопросу о применении гуманитарно-научных методов в процессе анализа историко-правовых источников
Zorile Dorina D., Тенденции развития науки и образования 2021 Т. 75 № 3 С. 37–42
The article deals with the involving into the history of law the methodology of a new branch - jurislinguistics and of a traditional one - comparativistics, wich supply methdological approaches to the historical investigations. The features of its implementation in order to acheave a correct translation of foreign legal texsts and interpretation of their terminology are ...
Added: December 4, 2022
Presburger arithmetic and Visser's conjecture
Zapryagaev A., , in: Logical Perspectives 2021 Workshop.: M.: [б.и.], 2021. Ch. 18.
Presburger Arithmetic the true theory of natural numbers with addition. We show that the interpretations of Presburger Arithmetic in itself are definably isomorphic to the trivial one, confirming the conjecture of A. Visser. To prove that, we develop a characterization of linear orderings interpretable in (N, +). We show that all interpretable linear orderings can ...
Added: December 14, 2021
Классификация линейных порядков, интерпретируемых многомерно в арифметике Пресбургера
Zapryagaev A., В кн.: Двенадцатые Смирновские чтения: материалы Международной научной конференции, Москва, 24–26 июня 2021 г.: М.: Русское общество истории и философии науки, 2021. С. 16–18.
Мы рассматриваем многомерные интерпретации линейных порядков в стандартной модели (N, +) арифметики Пресбургера. Устанавливается, что всякий такой порядок переводится определимым изоморфизмом в сужение лексикографического порядка Z 𝑛 на некоторое определимое множество для достаточно большого 𝑛. Это даёт более простое доказательство гипотезы Виссера об определимом изоморфизме тождественной всякой интерпретации самой арифметики Пресбургера в (N, +). ...
Added: June 28, 2021
Multi-dimensional Interpretations of Presburger Arithmetic in Itself
Pahomov F., Zapryagaev A., Journal of Logic and Computation 2020 Vol. 30 No. 8 P. 1681–1693
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 ...
Added: November 12, 2020
Interpretations of Linear Orderings in Presburger Arithmetic
Zapryagaev A., / Series arXiv "math". 2019. No. 1911.07182.
Presburger Arithmetic PrA is the true theory of natural numbers with addition. We consider linear orderings interpretable in Presburger Arithmetic and establish various necessary and sucient conditions for interpretability depending on dimension n of interpretation. We note this problem is relevant to the interpretations of Presburger Arithmetic in itself, as well as the characterization of ...
Added: November 28, 2019
Interpretations of Presburger Arithmetic in Itself
Zapryagaev A., Pahomov F., , in: International Symposium on Logical Foundations of Computer Science, LFCS 2018Vol. 10703.: Springer, 2018. P. 354–367.
Presburger arithmetic PrA is the true theory of natural numbers with addition. We study interpretations of PrA in itself. We prove that all one-dimensional self-interpretations are definably isomorphic to the identity self-interpretation. In order to prove the results we show that all linear orders that are interpretable in (N,+) are scattered orders with the finite Hausdorff rank and that the ranks ...
Added: October 25, 2019
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit