# Blog Archives

# Topic Archive: uncountable computability

# Uncountable free abelian groups via κ-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 Σ^{0}_{1} 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 Σ

^{1}

_{1}-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.

# Σ-Presentable structures over *HF(R)*

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

**of reals), we obtain its generalization, namely, the notion of Σ-presentable structures over**

*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**

*HF(R)***, not approximations, where we in addition have opportunity to find roots of polynomials and use them in further computations.**

*R*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.