Descriptive properties on admissible sets

DOI10.1007/S10469-010-9087-4MaRDI QIDQ619320zbMATH OpenOpenAlexFDO

Authors Vadim G. Puzarenko

Publication date 24 January 2011

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10469-010-9087-4

zbMATH Keywords

admissible setdescriptive propertyuniversal function

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Review text

The author explores the relation between various descriptive properties on admissible sets, with focus on reduction (\(\mathsf{Red}\)), existence of universal \(\Sigma\)-functions (\(\mathsf{UF}\)), existence of \(\{0,1\}\)-valued universal \(\Sigma\)-functions (\(\mathsf{UF2}\)) and separation (\(\mathsf{Sep}\)). It is shown that admissible sets behave rather badly in that almost every relation between these properties may be realized on a certain admissible set. And in most cases, such a set can be chosen as a hereditarily finite superstructure \(\mathbb{HF}(\mathfrak{M})\) over a computable model \(\mathfrak{M}\). The paper is divided into four parts. In Part I, the relations between the following properties are stated: enumerability, uniformization, reduction, (\(\mathsf{UF}\)), (\(\mathsf{UF2}\)), separation, and extension. Part II focuses on (\(\mathsf{Red}\)): various examples of classical structures \(\mathcal{M}\) are given so that \(\mathbb{HF}(\mathfrak{M})\) does not satisfy the reduction property. Part III considers (\(\mathsf{UF}\)) and provides computable models \(\mathbb{HF}(\mathfrak{M})\) that disprove the implications \((\mathsf{UF})\to(\mathsf{Red})\) and \((\mathsf{Red})\to(\mathsf{UF})\), respectively. Finally, Part IV deals with (\(\mathsf{UF2}\)): computable structures of the form \(\mathbb{HF}(\mathfrak{M})\) are specified where (\(\mathsf{Sep}\)) and (\(\mathsf{UF2}\)) fail, and where (\(\mathsf{Sep}\)) and (\(\mathsf{UF}\)) fail, but (\(\mathsf{UF2}\)) still holds.

Recommendations

• A certain reducibility on admissible sets
• scientific article; zbMATH DE number 5049507
• A universal recursive function on admissible sets
• On principles of computability on admissible sets
• On the admissible sets of type \(\mathbb{H}\mathbb{Y}\mathbb{P}(\mathfrak M)\) over recursively saturated models

Cites work

• A certain reducibility on admissible sets
• Computability in special models
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3494394 (Why is no real title available?)
• scientific article; zbMATH DE number 2047495 (Why is no real title available?)
• scientific article; zbMATH DE number 1534487 (Why is no real title available?)
• scientific article; zbMATH DE number 1746559 (Why is no real title available?)
• scientific article; zbMATH DE number 1396727 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On principles of computability on admissible sets
• Products of locally cyclic, torsion-free groups
• S-Subsets of Natural Numbers

Cited in

(8)

• A universal recursive function on admissible sets
• Properties of \(s\Sigma\)-reducibility
• scientific article; zbMATH DE number 5165178 (Why is no real title available?)
• COMPLEXITY OF INDEX SETS OF DESCRIPTIVE SET-THEORETIC NOTIONS
• Generalized reduction theorems for model-theoretic analogs of the class of coanalytic sets
• A certain reducibility on admissible sets
• On principles of computability on admissible sets
• On the admissible sets of type \(\mathbb{H}\mathbb{Y}\mathbb{P}(\mathfrak M)\) over recursively saturated models

This page was built for publication: Descriptive properties on admissible sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619320)