Index sets are used to measure the complexity of properties associated with the differentiability of real functions and the existence of solutions to certain classic differential equations. The new notion of a locally computable real function is introduced and provides several examples of Σ04 complete sets.

We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, (...) is Σ4 0 complete. We also look at computable presentability of these classes. (shrink)

An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property (...) R of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language. (shrink)

For a computable structure A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{A}}$$\end{document}, there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}, then the complexity of the index set I\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I}$$\end{document} is bounded by that of φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}. There are results giving “optimal” Scott sentences (...) for structures of various familiar kinds. These results have been driven by the thesis that the complexity of the index set should match that of an optimal Scott sentence. In this note, it is shown that the thesis does not always hold. For a certain subgroup of Q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Q}}$$\end{document}, there is no computable d-Σ2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma_2}$$\end{document} Scott sentence, even though the index set is d-Σ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document}. (shrink)

A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is (...) Σ02 complete. Various notions of boundedness are discussed and classified. For example, the index set of the recursively bounded classes is Σ03 complete and the index set of the recursively bounded classes which have infinitely many recursive members is Π04 complete. Consideration of the Cantor-Bendixson derivative leads to index sets in the transfinite levels of the hyperarithmetic hierarchy. (shrink)

This paper calculates, in a precise way, the complexity of the index sets for three classes of computable structures: the class $K_{\omega _{1}^{\mathit{CK}}}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}$ , the class $K_{\omega _{1}^{\mathit{CK}}+1}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}+1$ , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete $\Sigma _{1}^{1},\,I(K_{\omega _{1}^{\mathit{CK}}})$ is m-complete $\Pi _{2}^{0}$ relative to Kleen's O, and $I(K_{\omega _{1}^{\mathit{CK}}+1})$ is m-complete $\Sigma _{2}^{0}$ relative to (...) O. (shrink)

I introduce an effective enumeration of all effective enumerations of classes of r. e. sets and define with this the index set IE of injectively enumerable classes. It is easy to see that this set is ∑5 in the Arithmetical Hierarchy and I describe a proof for the ∑5-hardness of IE.

A many-one degree is functional if it contains the index set of some class of partial recursive functions but does not contain an index set of a class of r.e. sets. We give a natural embedding of the r.e. m-degrees into the functional degrees of 0'. There are many functional degrees in 0' in the sense that every partial-order can be embedded. By generalizing, we show there are many functional degrees in every complete Turning degree. There is a (...) natural tie between the studies of index sets and partial-many-one reducibility. Every partial-many-one degree contains one or two index sets. (shrink)

Let X be any infinite, coinfinite r.e. set. We show that the index set $\{e: W_e \equiv_1 X\}$ is Σ 0 3 -complete, answering a question posed by Odifreddi in [2].

We prove the following results: every recursively enumerable set approximated by finite sets of some set M of recursively enumerable sets with index set in π 2 is an element of M , provided that the finite sets in M are canonically enumerable. If both the finite sets in M and in M̄ are canonically enumerable, then the index set of M is in σ 2 ∩ π 2 if and only if M consists exactly of the sets (...) approximated by finite sets of M and the complement M̄ consists exactly of the sets approximated by finite sets of M̄ . Under the same condition M or M̄ has a non-empty subset with recursively enumerable index set, if the index set of M is in σ 2 ∩ π 2 . If the finite sets in M are canonically enumerable, then the following three statements are equivalent: the index set of M is in σ 2 \ π 2 , the index set of M is σ 2 -complete, the index set of M is in σ 2 and some sequence of finite sets in M approximate a set in M̄ . Finally, for every n ⩾ 2, an index set in σ n \ π n is presented which is not σ n -complete. (shrink)

For a class K of structures, closed under isomorphism, the index set is the set I of all indices for computable members of K in a universal computable numbering of all computable structures for a fixed computable language. We study the complexity of the index set of class of structures with decidable theories. We first prove the result for the class of all structures in an arbitrary finite nontrivial language. After the complexity is found, we prove similar results (...) for some well-known classes of structures, such as directed graphs, undirected graphs, partial orders and lattices. (shrink)

We obtain a large class of significant examples of n-random reals (i.e., Martin-Löf random in oracle $\varphi ^{(n - 1)} $ ) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set O ⊆(ℕ). In particular, we develop methods to transfer $\Sigma _n^0 $ or $\Pi _n^0 $ or many-one completeness results of (...) index sets to n-randomness of associated probabilities. (shrink)

Let$ \le _c $be computable the reducibility on computably enumerable equivalence relations. We show that for every ceerRwith infinitely many equivalence classes, the index sets$\left\{ {i:R_i \le _c R} \right\}$,$\left\{ {i:R_i \ge _c R} \right\}$, and$\left\{ {i:R_i \equiv _c R} \right\}$are${\rm{\Sigma }}_3^0$complete, whereas in caseRhas only finitely many equivalence classes, we have that$\left\{ {i:R_i \le _c R} \right\}$is${\rm{\Pi }}_2^0$complete, and$\left\{ {i:R \ge _c R} \right\}$ is${\rm{\Sigma }}_2^0$complete. Next, solving an open problem from [1], we prove that the index (...) set of the effectively inseparable ceers is${\rm{\Pi }}_4^0$complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a${\rm{\Sigma }}_3^0$complete preordering relation, a fact that is used to show that the preordering relation$ \le _c $on ceers is a${\rm{\Sigma }}_3^0$complete preordering relation. (shrink)

We extend the techniques of Jahn to show the index set of the major subsets to be ∑5-complete. This was a question left open in Lempp and its solution involves a level-4 construction. We also show how the measuring of e-states arises naturally out of our iterated-trees approach to breaking up requirements.

We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”.

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in descriptive set theory. (...) In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. (shrink)

Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we (...) analyze the complexity of the question "Does B have invariant x?" For each x ∈ In we define a complexity class Γx that could be either Σⁿ, Πⁿ, Σⁿ ∧ Πⁿ, or Πω+1 depending on x, and we prove that the set of indices for computable Boolean algebras with invariant x is complete for the class Γx. Analogs of many of these results for computably enumerable Boolean algebras were proven in earlier works by Selivanov. In a more recent work, he showed that similar methods can be used to obtain the results for computable ones. Our methods are quite different and give new results as well. As the algebras we construct to witness hardness are all dense, we establish new similar results for the complexity of various isomorphism problems for dense Boolean algebras. (shrink)

We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”.

We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering ψ satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems are left for the (...) reader. (shrink)

We prove that there exists a function f which reduces a given Π1 1 subset P of an internal set X of an ω1-saturated nonstandard universe to the set WF of well-founded trees possessing properties similar to those possessed by the standard part map. We use f to define the Lusin-Sierpinski index of points in X, and prove the basic properties of that index using the classical properties of the Lusin-Sierpinski index. An example of a Π1 1 (...) but not Σ1 1 set is given. (shrink)

This article reports on the methodology for setting the Mexican User Satisfaction Index for Social Programs as tested in seven national social programs. The evaluation is based on Structural Equation Modeling. How satisfaction takes the central place of the SEM, which postulates its causes and effects, contributes to the increased validity and reliability of satisfaction indicators that allow benchmarking between social programs. The MUSI model is an adaptation of the American Customer Satisfaction Index model. The MUSI methodology includes (...) qualitative and quantitative techniques. The estimation model is by the Partial Least Squares. In each of the seven social programs, no statistical evidence was found to reject the main relationships postulated by the ACSI’s model: that Perceived Quality impacts Satisfaction, and Satisfaction impacts Trust. The improvement opportunity areas were also identified for each program. These results give valid and reliable feedback to public policies. (shrink)

The German philosopher and philologist Friedrich Ast published this monumental lexicon in three volumes. A professor of classical literature at the University of Landshut and member of the Bavarian Academy of Sciences, Ast wrote widely on the history of philosophy. He edited a complete edition of Plato with Latin translation, identifying spurious interpolations and false attributions, using this as a basis for his Lexicon. The entries give citations both from Plato and from later works that extensively quote Plato. Though the (...) Lexicon met with criticism for omissions of particles, prepositions and proper names, and the lack of systematic arrangement, it had a high reputation throughout the nineteenth century. It remains a milestone in Plato scholarship and is an indispensable resource for readers interested in the history of philology and methods in textual criticism. (shrink)

The paper seeks to develop an account of indexical phenomena based on the highly general theory of structure and dependence set forth by Husserl in his Logical Investigations. Husserl here defends an Aristotelian theory of meaning, viewing meanings as species or universals having as their instances certain sorts of concrete meaning acts. Indexical phenomena are seen to involve the combination of such acts of meaning with acts of perception, a thesis here developed in some detail and contrasted with accounts of (...) indexicals suggested by Frege, Wittgenstein and by the later Husserl himself in his Ideas I. Implications are drawn also for our understanding of the categorial grammar sketched by Husserl in his 4th Logical Investigation, as also for our understanding of the nature of proper names and other candidate indexical expressions. (shrink)

The paper uses the formalism of indexed categories to recover the proof of a standard final coalgebra theorem, thus showing existence of final coalgebras for a special class of functors on finitely complete and cocomplete categories. As an instance of this result, we build the final coalgebra for the powerclass functor, in the context of a Heyting pretopos with a class of small maps. This is then proved to provide models for various non-well-founded set theories, depending on the chosen axiomatisation (...) for the class of small maps. (shrink)