We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the Σβ hierarchy. We focus on linear orderings. We show that at the Σ1 level, all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the Σα+2 level for any α∈ω1CK the set of linear orderings with generically or coarsely computable copies is Σ11-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results, we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy.

Abstract We study possible Scott sentence complexities of linear orderings using two approaches. First, we investigate the effect of the Friedman–Stanley embedding on Scott sentence complexity and show that it only preserves $\Pi ^{\mathrm {in}}_{\alpha }$ complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except $\Sigma ^{\mathrm {in}}_{3}$ and $\Sigma ^{\mathrm {in}}_{\lambda +1}$ for $\lambda $ a limit ordinal. We show that the former cannot be the Scott sentence complexity of a linear ordering. In the process we develop new techniques which appear to be helpful to calculate the Scott sentence complexities of structures.