This article is cited in 1 paper

Mathematical Logic, Algebra, Number Theory and Discrete Mathematics

On decidability of finite subsets’ theory for discrete linear order

N. V. Avkhimovich

Tver State University, Tver

Abstract: Let us consider a discrete linear ordered set. On finite subsets of such set we introduce a new binary relation. This relation says that all items of a first set is less than all items of a second one. We show that the theory of such constructed structure admits quantifier elimination. For this purpose, we expand the language with four definable functions. As a corollary we get the theory of finite subsets of a discrete linear order to be decidable.

Keywords: theory, finite subsets, quantifiers elimination, discrete linear order, decidability.

UDC: 510.665, 510.53, 510.65

Received: 19.06.2022
Revised: 05.09.2022

DOI: 10.26456/vtpmk646

Bibliographic databases:

•