Topic Archive: uncountable computability
One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ01 definable (with parameters, in the language of set theory) over Lκ provides the notion of κ-computability. We may also quantify over subsets of Lκ, providing a notion of a κ-analytic set (here we assume V=L). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ11-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.
If we replace in the definition of computable structures the concept of classical computability over ω with Σ-definability over the structure HF(R) (the hereditarily finite superstructure over the ordered field R of reals), we obtain its generalization, namely, the notion of Σ-presentable structures over HF(R). This generalization could correspond to the hypothetical situation when we have an opportunity to use algorithms written in a powerful programming language with “real” reals, elements of R, not approximations, where we in addition have opportunity to find roots of polynomials and use them in further computations.
In the talk, a survey will be given of the results on the existence of Σ-presentations for various structures, on the number of non Σ-isomorphic presentations, and on the existence of Σ-parameterizations for classes of presentations.