Search for: All records

Abstract Given a countable structure, the Scott complexity measures the difficulty of characterizing the structure up to isomorphism. In this paper, we consider the Scott complexity of linear orders. For any limit ordinal , we construct a linear order whose Scott complexity is . This completes the classification of the possible Scott sentence complexities of linear orderings. Previously, there was only one known construction of any structure (of any signature) with Scott complexity , and our construction gives new examples, for example, rigid structures, of this complexity. Moreover, we can construct the linear orders so that not only does have Scott complexity , but there are continuum‐many structures and all such structures also have Scott complexity . In contrast, we demonstrate that there is no structure (of any signature) with Scott complexity that is only ‐equivalent to structures with Scott complexity . Our construction is based on functions that are almost periodic but not periodic, such as those arising from shifts of the ‐adic valuations. 

We work in the setting of Zermelo-Fraenkel set theory without assuming the Axiom of Choice. We consider sets with the Boolean operations together with the additional structure of comparing cardinality (in the Cantorian sense of injections). What principles does one need to add to the laws of Boolean algebra to reason not only about intersection, union, and complementation of sets, but also about the relative size of sets? We give a complete axiomatization. A particularly interesting case is when one restricts to the Dedekind-finite sets. In this case, one needs exactly the same principles as for reasoning about imprecise probability comparisons, the central principle being Generalized Finite Cancellation (which includes, as a special case, division-by-$$m$$). In the general case, the central principle is a restricted version of Generalized Finite Cancellation within Archimedean classes which we call Covered Generalized Finite Cancellation. 

In this paper, we answer two questions on the complexities of decision problems of groups, each related to a classical result. First, Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to the word problem of a finitely presented group is [Formula: see text]-complete, which is the maximal possible complexity.