This article is cited in 10 papers

Recursive terms in semantic programming

S. S. Goncharov, D. I. Sviridenko

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: For constructing an enrichment of a language with restricted quantifiers, we extend the notion of term by the construction of the terms conditional and recursive with respect to lists. We show that the so-obtained extension of the language of formulas with restricted quantifiers over structures with hereditary finite lists is a conservative enrichment and the new terms are $\Delta$-definable in the basic language.

Keywords: formula, term, restricted quantifier, $\Delta_0$-formula, $\Delta$-formula, $\Sigma$-formula, semantic programming, computability, computability over abstract structures, conditional term, recursive term, model, hereditary finite list, hereditary finite set.

UDC: 510.2+510.3+510.6+51.8+004.8

Received: 17.03.2018

DOI: 10.17377/smzh.2018.59.605

 English version: Siberian Mathematical Journal, 2018, 59:6, 1014–1023

Bibliographic databases:

• 
• 
•