Effective algebraicity
type: Item
instance of: scholarly article
title: Effective algebraicity
zbMATH Open document ID: 1300.03021
author: Rebecca M. Steiner
published in: Archive for Mathematical Logic
publication date: 2013-02-15T00:00:00Z
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.
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D80
zbMATH DE Number: 6136594
zbMATH Keywords: computability
zbMATH Keywords: computable categoricity
zbMATH Keywords: algebraic field
zbMATH Keywords: computable graph
zbMATH Keywords: computable tree
zbMATH Keywords: degree spectra
reviewed by: Andrei S. Morozov
MaRDI profile type: Publication
full work available at URL: s00153-012-0308-5
OpenAlex ID: W2914384462
cites work: Degrees of categoricity and the hyperarithmetic hierarchy
cites work: Q4423053
cites work: Degrees of categoricity of computable structures
cites work: Spectra of Algebraic Fields and Subfields
cites work: Q4249356
cites work: Spectra of structures and relations
cites work: Categoricity properties for computable algebraic fields
cites work: Q4336034
cites work: ∏ 0 1 Classes and Degrees of Theories
cites work: Degrees coded in jumps of orderings
cites work: d-computable categoricity for algebraic fields
cites work: Q3588177
cites work: Computable categoricity for algebraic fields with splitting algorithms
cites work: Q4526525
cites work: Q3819052
cites work: Turing Computability
DOI: 10.1007/S00153-012-0308-5
description: scientific article; zbMATH DE number 6136594