Constructive and Non-Constructive Infinite Formulas in Computable Structures期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Constructive and Non-Constructive Infinite Formulas in Computable Structures

Authors:	P E Alaev

Institution:	(1) Akademika Koptyuga Prospekt, 4, Institute of Mathematics SB RAS, Novosibirsk, 630090, Russia

Abstract:	A transition from arbitrary $L_{\omega _{\text{1}} \omega }$ -formulas to computable formulas in the class of computable structures is considered. It is shown that transition of a certain type is possible which doubles the complexity of the formulas. In addition, the complexity jump is analyzed for the transition from an arbitrary Scott family consisting of $L_{\omega _{\text{1}} \omega }$ -formulas to a computable Scott family in a fixed computable structure. Exact estimates of this jump are found.

Keywords:	computable structure computable formula Scott family
本文献已被 SpringerLink 等数据库收录！