-
13Punctual Categoricity and UniversalityJournal of Symbolic Logic 85 (4): 1427-1466. 2020.We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus …Read more
-
47Limitwise monotonic functions, sets, and degrees on computable domainsJournal of Symbolic Logic 75 (1): 131-154. 2010.We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing limitwise monotonic sets on cer…Read more
-
68Two More Characterizations of K-TrivialityNotre Dame Journal of Formal Logic 59 (2): 189-195. 2018.We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is immediate, so we have the second characterization of K-triviality.The p…Read more
-
50Linear orders realized by C.e. Equivalence relationsJournal of Symbolic Logic 81 (2): 463-482. 2016.LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}…Read more
-
20Computability-theoretic categoricity and Scott familiesAnnals of Pure and Applied Logic 170 (6): 699-717. 2019.
-
29Computability and uncountable linear orders II: Degree spectraJournal of Symbolic Logic 80 (1): 145-178. 2015.
-
24Computability and uncountable linear orders I: Computable categoricityJournal of Symbolic Logic 80 (1): 116-144. 2015.
-
67Decidability and Computability of Certain Torsion-Free Abelian GroupsNotre Dame Journal of Formal Logic 51 (1): 85-96. 2010.We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$
-
38Galvin’s “Racing Pawns” Game, Internal Hyperarithmetic Comprehension, and the Law of Excluded MiddleNotre Dame Journal of Formal Logic 54 (2): 233-252. 2013.We show that the fact that the first player wins every instance of Galvin’s “racing pawns” game is equivalent to arithmetic transfinite recursion. Along the way we analyze the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas
-
95
-
5
-
42Lowness for effective Hausdorff dimensionJournal of Mathematical Logic 14 (2): 1450011. 2014.We examine the sequences A that are low for dimension, i.e. those for which the effective dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf ran…Read more