Turing Computable Embeddings and Coding Families of Sets

摘要

In [7] the notion of Turing computable embeddings is introduced as an effective counterpart for Borel embeddings. The former allows for the study of classes of structures with universe a subset of ω. It also allows for finer distinctions, in particular, among classes with No isomorphism types. The hierarchy of effective cardinalities that arises from TC embeddings has been studied, among other places, in [7] and [2]. In this work, we prove that the special class of 'daisy graphs', a subclass of undirected graphs used to code families of sets, has the same effective cardinality as the class of archimedian real closed fields. As a consequence, the class of abelian p-groups and the class of archimedian real closed fields are TC incomparable.