|
This article is cited in 4 scientific papers (total in 4 papers)
Comparing classes of finite sums
U. Andrewsa, D. I. Dusheninb, C. Hillc, J. F. Knightd, A. G. Melnikove a Department of Mathematics, University of Wisconsin, Madison, WI, 53706-1388, USA
b SNIIGGiMS, Krasnyi pr. 67, Novosibirsk, Russia
c Department of Mathematics and Computer Science, Wesleyan University, Middletown, CT, 06459, USA
d Department of Mathematics, Univ. Notre Dame, 255 Hurley, Notre Dame, IN, 46556, USA
e Institute of Natural and Mathematical Sciences, Massey University, Palmerston North, 4442, New Zealand
Abstract:
The notion of Turing computable embedding is a computable analog of Borel embedding. It provides a way to compare classes of countable structures, effectively reducing the classification problem for one class to that for the other. Most of the known results on nonexistence of Turing computable embeddings reflect differences in the complexity of the sentences needed to distinguish among nonisomorphic members of the two classes. Here we consider structures obtained as sums. It is shown that the $n$-fold sums of members of certain classes
lie strictly below the $(n+1)$-fold sums. The differences reflect model-theoretic considerations related to Morley degree, not differences in the complexity of the sentences that describe the structures. We consider three different kinds of sum structures: cardinal sums, in which the components are named by predicates; equivalence sums, in which the components are equivalence classes under an equivalence relation; and direct sums of certain groups.
Keywords:
Turing computable embedding, classes of finite sums, Morley degree, complexity of sentences.
Received: 08.07.2013 Revised: 18.02.2015
Citation:
U. Andrews, D. I. Dushenin, C. Hill, J. F. Knight, A. G. Melnikov, “Comparing classes of finite sums”, Algebra Logika, 54:6 (2015), 748–768; Algebra and Logic, 54:6 (2016), 489–501
Linking options:
https://www.mathnet.ru/eng/al723 https://www.mathnet.ru/eng/al/v54/i6/p748
|
Statistics & downloads: |
Abstract page: | 237 | Full-text PDF : | 31 | References: | 66 | First page: | 31 |
|