Effective algebraicity

DOI10.1007/S00153-012-0308-5MaRDI QIDQ1935364zbMATH OpenOpenAlexFDO

Authors Rebecca M. Steiner

Publication date 15 February 2013

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-012-0308-5

zbMATH Keywords

algebraic fieldcomputabilitycomputable categoricitycomputable graphcomputable treedegree spectra

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Applications of computability and recursion theory (03D80)

Review text

This paper contains lots of results on categoricity and degree spectra of graphs and trees under the predecessor function. The author compares the obtained results with some related results for fields and discusses and explains similarities and differences between them. It would take too much room to list all the results of this paper or it would mean too much responsibility for a reviewer to rank them and cite the brightest ones. Therefore, the review will contain a general description of the results only. The first series of results characterizes the behavior of the Turing degree of the valence function under isomorphism for finite-valence pointed graphs. Then the author studies the relationship between the computability of the branching function and the computable categoricity of finite-branching trees under the predecessor function. The author also gives a characterization of spectra and degrees of categoricity of connected finite-valence pointed graphs. The paper also contains a series of results on degrees and spectra of images of embeddings of trees into \(\omega^{<\omega}\) and on embeddings of pointed graphs into random pointed graphs. In addition, the paper contains some general results on graphs like the fact that two connected finite-valence pointed graphs are isomorphic if and only if they satisfy the same \(\Sigma_1\)-sentences, and that this could be not true for finite branching trees under predecessor, the characterization of \(\omega^{<\omega}\) as the unique countable universal ultrahomogeneous tree under predecessor which is universal for finite branching trees, as well as a similar characterization of the random graph with respect to the class of connected finite-valence graphs.

Recommendations

• Computable categoricity of trees of finite height
• Categoricity spectra of computable structures
• Degrees of categoricity of trees and the isomorphism problem
• Degree Spectra of Relations on Computable Structures
• Computability and categoricity of weakly ultrahomogeneous structures

Cites work

• d-computable categoricity for algebraic fields
• Categoricity properties for computable algebraic fields
• Computable categoricity for algebraic fields with splitting algorithms
• Computable fields and Galois theory
• Degrees coded in jumps of orderings
• Degrees of categoricity and the hyperarithmetic hierarchy
• Degrees of categoricity of computable structures
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 1302870 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 1554144 (Why is no real title available?)
• Spectra of Algebraic Fields and Subfields
• Spectra of structures and relations
• Turing computability. Theory and applications
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(6)

• Classifications of computable structures
• Effectively existentially-atomic structures
• Prime model with no degree of autostability relative to strong constructivizations
• d-computable categoricity for algebraic fields
• Bi‐embeddability spectra and bases of spectra
• On categoricity spectra for locally finite graphs

This page was built for publication: Effective algebraicity

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