An official website of the United States government
Abstract Recall that B is PA relative to A if B computes a member of every nonempty $$\Pi ^0_1(A)$$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $$\Pi ^0_1$$ class relative to an enumeration oracle A , which they called a $$\Pi ^0_1{\left \langle {A}\right \rangle }$$ class. We study the induced extension of the relation B is PA relative to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the $${\left \langle {\text {self}\kern1pt}\right \rangle }$$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $$\Pi ^0_1$$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question.
more »
« less
CHARACTERIZING THE CONTINUOUS DEGREES
The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees, we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. We prove that the enumeration degree of A is continuous if and only if A is codable, meaning that A is enumeration above the complement of an infinite tree, every path of which enumerates A.
more »
« less
- Award ID(s):
- 1762648
- PAR ID:
- 10090721
- Date Published:
- Journal Name:
- Israel journal of mathematics
- ISSN:
- 0021-2172
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Brattka, Vasco; Greenberg, Noam; Kalimullin, Iskander; Soskova, Mariya (Ed.)In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees a 0 and a 1 such that every enumeration degree x < a 0 is ⩽ a 1 . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ 2 0 -enumeration degrees a 0 and a 1 such that every enumeration degree x 0 < a 0 is ⩽ a 1 and such that every enumeration degree x 1 < a 1 is ⩽ a 0 . In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ 2 0 -enumeration degrees a 0 , a 1 and a 2 such that both ( a 0 , a 1 ) and ( a 1 , a 2 ) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ 2 0 -enumeration degrees a 0 , a 1 and a 2 such that every enumeration degree x < a 0 is also ⩽ a 1 or ⩽ a 2 ; however neither ( a 0 , a 1 ) nor ( a 0 , a 2 ) is an Ahmad pair.more » « less
-
Abstract A result of Gyárfás says that for every 3‐coloring of the edges of the complete graph , there is a monochromatic component of order at least , and this is best possible when 4 divides . Furthermore, for all and every ‐coloring of the edges of the complete ‐uniform hypergraph , there is a monochromatic component of order at least and this is best possible for all . Recently, Guggiari and Scott and independently Rahimi proved a strengthening of the graph case in the result above which says that the same conclusion holds if is replaced by any graph on vertices with minimum degree at least ; furthermore, this bound on the minimum degree is best possible. We prove a strengthening of the case in the result above which says that the same conclusion holds if is replaced by any ‐uniform hypergraph on vertices with minimum ‐degree at least ; furthermore, this bound on the ‐degree is best possible.more » « less
-
In this paper, we answer two questions on the complexities of decision problems of groups, each related to a classical result. First, Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to the word problem of a finitely presented group is [Formula: see text]-complete, which is the maximal possible complexity.more » « less
-
This paper explores several topics related to Woodin’s HOD conjecture. We improve the large cardinal hypothesis of Woodin’s HOD dichotomy theorem from an extendible cardinal to a strongly compact cardinal. We show that assuming there is a strongly compact cardinal and the HOD hypothesis holds, there is no elementary embedding from HOD to HOD, settling a question of Woodin. We show that the HOD hypothesis is equivalent to a uniqueness property of elementary embeddings of levels of the cumulative hierarchy. We prove that the HOD hypothesis holds if and only if every regular cardinal above the first strongly compact cardinal carries an ordinal definable omega Jónsson algebra. We show that if the HOD hypothesis holds and HOD satisfies the Ultrapower Axiom, then every supercompact cardinal is supercompact in HOD.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
