On the admissible sets of type \(\mathbb{H}\mathbb{Y}\mathbb{P}(\mathfrak M)\) over recursively saturated models (Q662638)

The paper under review is devoted to some aspects of computability on HYP-structures above recursively saturated structures. On the one hand, such admissible sets contain infinite elements; on the other hand, the height of them is as small as possible. The author proves \(\Sigma\)-reducibility of \(\mathbb{HYP}(\mathfrak{M})\) to \(\mathbb{HF}(\mathfrak{M})\) for each recursively saturated structure of a decidable model-complete theory, and gives the following criterion of uniformization: Theorem. Let \(\mathfrak{M}\) be a recursively saturated structure. Then the following conditions are equivalent: 1. \(\mathbb{HYP}(\mathfrak{M})\) satisfies uniformization; 2. For every \(A\subseteq\mathcal{P}(M)\setminus\{\emptyset\}\) with \(A\in \mathrm{HYP}(M)\) there exists a choice function \(f\in \mathrm{HYP}(M)\) (i.e., \(f(a)\in a\) for every \(a\in A\)). In fact, the second condition says that a weak choice holds on \(\mathbb{HYP}(\mathfrak{M})\). As a corollary, the author shows that \(\mathbb{HYP}(\mathfrak{N})\) and \(\mathbb{HYP}(\mathfrak{R})\) satisfy uniformization, where \(\mathfrak{N}\) and \(\mathfrak{R}\) are recursively saturated structures of arithmetics and of the theory of reals, respectively. Also, it is proved that \(\mathbb{HYP}(\mathfrak{M})\) and \(\mathbb{HF}(\mathfrak{M})\) do not satisfy uniformization whenever \(\mathfrak{M}\) is a saturated structure of an uncountably categorical theory. The author also discusses the existence of definable Skolem functions on structures. For proving the main results, the author introduces codes of the elements of \(\mathbb{HYP}(\mathfrak{M})\) by natural numbers.