Effective algebraicity (Q1935364)

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.