Please note that links below are to draft forms of my mathematical papers. Obtain the final version from the appropriate journal. Papers are sorted by research area (links below), then alphabetically by coauthor.
Classical Computability Theory
Effective Algebra and Computable Model Theory
Reverse Mathematics
Other Computational Paradigms
Boolean Algebras (Classically)
Other Writings
Most of these papers are copyrighted. All may be downloaded and/or
printed only for personal or non-profit educational use. For further
information about these copyrights, visit here.
Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains
(Journal of Symbolic Logic, 75:1 (2010), 131-154)
With Turetsky
Abstract. We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing (support strictly 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 Q and note relationships between the class of order-computable sets and the class of support increasing (support strictly increasing) limitwise monotonic sets on certain domains.
Computable Shuffle Sums of Ordinals
(Archive for Mathematical Logic, 47:3 (2008), 211-219)
Abstract. The main result is that for sets S ⊆ ω+1, the
following are equivalent:
(1) The shuffle sum σ(S) is computable.
(2) The set S is a limit infimum set, i.e., there is a total
computable function f(x,s) such that the function F(x) =
liminfs f(x,s) enumerates S.
(3) The set S is a limitwise monotonic set relative to 0',
i.e., there is a total 0'-computable function g(x,t)
satisfying g(x,t) ≤ g(x,t+1) such that the function G(x) =
limt g(x,t) enumerates S.
Other results discuss the relationship between these sets and the
Σ03 sets.
Depth Zero Boolean Algebras
(Transactions of the American Mathematical Society, 362 (2010), 4243-4265)
Abstract. We study the class of depth zero Boolean algebras, both from a
classical viewpoint and an effective viewpoint. In particular, we
provide an algebraic characterization - constructing an explicit measure
for each depth zero Boolean algebra and demonstrating there are no
others - and an effective characterization - providing a necessary a
sufficient condition for a depth zero Boolean algebra of rank at most
&omega to have a computable presentation.
Jump Degrees of Torsion-Free Abelian Groups
(Journal of Symbolic Logic, 77:4 (2012), 1067-1100)
With Andersen, Melnikov, and Solomon
Abstract. We show, for each computable ordinal α and degree
a > 0(α), the existence of a torsion-free
abelian group having proper αth jump degree a.
Computing a Ryll-Nardzewski Function
(Algebra and Logic, 53:2 (2014), 176-183)
With Andrews
We study, for a countably categorical theory T, the complexity of
computing and the complexity of dominating the function specifying the number of
n-types consistent with T.
Euclidean Functions of Computable Euclidean Domains
(Notre Dame Journal of Formal Logic, 52:2 (2011), 163-172)
With Downey
Abstract. We study the complexity of (finitely-valued and
transfinitely-valued) Euclidean functions for computable Euclidean
domains. We examine both the complexity of the minimal Euclidean
function and any Euclidean function.
Decidability and Computability of Certain Torsion-Free Abelian Groups
(Notre Dame Journal of Formal Logic, 51:1 (2010), 85-96)
With Downey, Goncharov, Knight, Kudinov, Melnikov, and Turetsky
Abstract. We study completely decomposable torsion-free abelian groups of
the form GS := ⊕n ∈ S
Qpn for sets S⊆ω. We
show that GS has a decidable copy if and only if
S is Σ02
and has a computable copy if and only if S is Σ03.
The Complexity of Computable Categoricity
(Advances in Mathematics, 268 (2015), 423-466)
With Downey, Lempp, Lewis, Montalbán, and Turetsky
Abstract: We show that the index set complexity of the computably categorical
structures is Π11-complete, demonstrating that
computable categoricity has no simple syntactic characterization. As a
consequence of our proof, we exhibit, for every computable ordinal α, a
computable structure that is computably categorical but not relatively
categorical.
Computable Categoricity Versus Relative Computable Categoricity
(Fundamenta Mathematicae, 221 (2013), 129-159)
With Downey, Lempp, and Turetsky
Abstract. We study the notion of computable categoricity of computable
structures, comparing it especially to the notion of relative computable
categoricity and its relativizations. We show that every 1-decidable
computably categorical structure is relatively Δ02-categorical. We study the
complexity of various index sets associated with computable categoricity and
relative computable categoricity. We also introduce and study a variation of
relative computable categoricity, comparing it to both computable categoricity
and relative computable categoricity and its relativizations.
Limitwise Monotonic Functions and Applications
(Proceedings of the Eleventh Asian Logic Conference, 2011, 59-85)
With Downey and Turetsky
Abstract. We survey what is known about limitwise monotonic functions
and sets and discuss their applications in effective algebra and
computable model theory. Additionally, we characterize the computably
enumerable degrees that are totally limitwise monotonic and show
the support strictly increasing 0'-limitwise monotonic sets on
Q do not capture the sets with computable strong
η-representations.
Jump Inversions of Algebraic Structures and the Σ-Definability
(Mathematical Logic Quarterly, 65:1 (May 2019), 37-45)
With Faizrahmanov, Kalimullin, Montalbán, and Puzarenko
Abstract. It is proved that for every countable structure A and a
successive computable ordinal α there is a countable structure
A−α which is ≤Σ-least
among all countable structures C such that A is
Σ-definable in the α-th jump C(α). We also show that
this result does not hold for the limit α = ω.
Moreover, we prove that there is no countable structure A with the
degree spectrum {d : a ≤ d(ω)} for
a > 0(ω).
Orders on Computable Torsion-Free Abelian Groups
(Annals of Pure and Applied Logic, 164:7-8 (August 2013), 822-836)
With Lange and Solomon
Abstract. We construct two computable presentations of computable
torsion-free abelian groups, one of isomorphism type
Qω and one of isomorphism type
Zω, having computable orders but not having orders of
every Turing degree.
Embeddings of Computable Structures
(Notre Dame Journal of Formal Logic, 51:1 (2010), 55-68)
With Levin and Solomon
Abstract. We study what the existence of a classical embedding between
computable structures implies about the complexity of such embeddings.
Cuts of Linear Orders
(Order, 28:3 (2011), 593-600)
With Montalbán
Abstract. We study the connection between the number of ascending and
descending cuts of a linear order, its classical size, and its effective
complexity (how much [how little] information can be encoded into it).
Undecidability of the Theories of Classes of Structures
(Journal of Symbolic Logic, 79:4 (2014), 1001-1019)
With Montalbán
Abstract. Many classes of structures have natural functions and relations
on them: concatentation of linear orders, direct product of groups,
disjoint union of equivalence structures, and so on. Here, we study the
(un)decidability of the theory of several natural classes of structures
with appropriate functions and relations. For some of these classes of
structures, the resulting theory is decidable; for some of these classes
of structures, the resulting theory is bi-interpretable with true
second-order arithmetic.
Δ02-Categoricity of Equivalence Structures
(New Zealand Journal of Mathematics, 39 (2009), 143-149)
With Turetsky
Abstract. We exhibit computable equivalence structures, one Δ02-categorical and one not Δ02-categorical, having unbounded character, infinitely many infinite equivalence classes, and no s1-function. This offers a natural example where Δ02-categoricity and relative Δ02-categoricity differ.
Subspaces of Computable Vector Spaces
(Journal of Algebra, 314 (2007), 888-894)
With Downey, Hirschfeldt, Lempp, Mileti, and Montalbán
Abstract. We show that the existence of a nontrivial proper sub-space of a
vector space of dimension greater than one (over an infinite field) is
equivalent to WKL0 over RCA0, and that the existence
of an infinite dimensional nontrivial proper subspace of such a vector
space is equivalent to ACA0 over RCA0.
Cappable CEA Sets and Ramsey's Theorem
(Proceedings of the Eleventh Asian Logic Conference, 2011, 114-127)
With Lerman and Solomon
Abstract. We begin a search for degree-theoretic properties that might be used to separate Ramsey's Theorem for Pairs from its stable version in the Reverse Mathematics sense. This paper introduces the notion of c-cappability and shows that this property cannot be used to obtain such a separation when combined with 2-CEA-ness.
Local Computability for Ordinals
(Proceedings for Computability in Europe, 2013)
With Franklin, R. Miller, and Solomon
Abstract. We examine the extent to which well orders satisfy the properties
of local computability, which measure how effectively the finite suborders
of the ordinal can be presented. Known results prove that all computable
ordinals are perfectly locally computable, whereas
ωCK1
and larger countable ordinals are not. We show that perfect local computability
also fails for uncountable ordinals, and that ordinals
α ≥ ωCK1
are θ-extensionally locally computable for all
θ < ωCK1,
but not when
θ > ωCK1,
nor when
θ = ωCK1
≤ α
< ωCK1 ˙ ω.
Computability and Uncountable Linear Orders I:
Computable Categoricity
(Journal of Symbolic Logic, 80:1 (2015), 116-144)
With Greenberg, Lempp, and Turetsky
Abstract: We study the computable structure theory of linear orders of size
ℵ1 within the framework of admissible computability theory. In
particular, we characterize which of these linear orders are computably
categorical.
Computability and Uncountable Linear Orders I:
Degree Spectra
(Journal of Symbolic Logic, 80:1 (2015), 145-178)
With Greenberg, Lempp, and Turetsky
Abstract: We study the computable structure theory of linear orders of size
ℵ1 within the framework of admissible computability theory. In
particular, we study degree spectra and the successor relation.
Downward Closure of Depth in Countable Boolean Algebras
(Algebra Universalis, 68 (2012), 57-74)
With Lempp
Abstract. We study the set of depths of subalgebras of countable Boolean algebras, in particular the extent to which this set may not be downward closed within the countable ordinals for a fixed countable Boolean algebra. Doing so, we exhibit a structural difference between the class of arbitrary rank countable Boolean algebras and the class of rank one countable Boolean algebras.
Book Review: The Structure of Models of Peano Arithmetic
(Studia Logica, 100:3 (2012), 659-662)
Characterizing the Computable Structures: Boolean Algebras and Linear Orders
(Ph.D. Thesis, University of Wisconsin, Madison, August 2007)
A countable structure (with finite signature) is computable if its universe can be indentified with &omega in such a way as to make the relations and operations computable functions. In this thesis, I study which Boolean algebras and linear orders are computable.
Making use of Ketonen invariants, I study the Boolean algebras of low Ketonen depth, both classically and effectively. Classically, I give an explicit characterization of the depth zero Boolean algebras; provide continuum many examples of depth one, rank ω Boolean algebras with range ω+1 and provide continuum many examples of depth ω, rank one Boolean algebras. Effectively, I show for sets S ⊆ ω+1 with greatest element, the depth zero Boolean algebras Bu(S) and Bv(S) are computable if and only if S\{ω} is Σ0n→ 2n+3 in the Feiner Σ-hierarchy.
Making use of the existing notion of limitwise monotonic functions and the new notion of limit infimum functions, I characterize which shuffle sums of ordinals below ω+1 have computable copies. Additionally, I show that the notions of limitwise monotonic functions relative to 0' and limit infimum functions coincide.
Though these papers are in preparation, drafts are (should be) available for those sufficiently interested. Please contact me if you would like an early version.
A Feiner Look at the Intermediate Degrees
(In preparation)
With Hirschfeldt and Montalbán
Abstract. We say a set S is Δ0(n)(X) if membership of n in S is a Δ0n question, uniformly in n. A set X is low for Δ-Feiner if every set S that is Δ0(n)(X) is also Δ0(n)(0). It is easy to see that every lown set is low for Δ-Feiner, but we show that the converse is not true by constructing a c.e. intermediate degree that is low for Δ-Feiner.
We also study variations of this notion, like the class of degrees that are Δ0(bn+a)(X), Σ0(bn+a)(X), or Π0(bn+a)(X) and the classes of sets that are low, intermediate, and high for them.
In doing so, we obtain results about computable and non-computable Boolean
algebras.
Embeddings of Computable Linear Orders
(In preparation)
With J. Miller
Abstract. We study what the existence of a classical embedding between
computable linear orders implies about the complexity of such embeddings.
In particular, we study embeddings of η into computable non-scattered
linear orders and embeddings of ω* into computable non-well-ordered
linear orders. The major results are the existence of a computable
non-scattered linear order that is intrinsically computably scattered; and
the existence of a computable non-well-ordered linear order that is
intrinsically computably well-ordered.
It's All Relative, Except When It's
Not: Conference on Definability in Computable Structures, May 2012
Shift Complex Sequences:
AMS Eastern Sectional Meeting, March 2012
Theories of Classes of Structures:
Oberwolfach Workshop on Computability Theory, February 2012
Orders on Computable Torsion-Free Abelian Groups:
Asian Logic Conference, December 2011
Orders on Computable Torsion-Free Abelian Groups:
Midwest Computability Theory Meeting, November 2011
Computable Categoricity and Relative Computable Categoricity:
AMS Eastern Sectional Meeting, April 2011
Jumps of Torsion-Free Abelian Groups:
AMS Eastern Sectional Meeting, November 2010
Embeddings of Computable Structures:
Australian Math Society Annual Meeting, September 2009
Embeddings of Computable Linear Orders:
ASL Annual Meeting, March 2008
Boolean Algebras and Ketonen Invariants:
Computability Workshop in Novosibirsk, August 2007
Atoms: The Building Blocks of Nature (Boolean Algebras):
Graduate Student Conference in Logic, April 2007
Shuffle Sums:
Graduate Student Conference in Logic, April 2006
Non-Standard Models of Arithmetic:
Graduate Student Conference in Logic, April 2004
The Smiley Face Theorem: Lindstrom's First Theorem:
Graduate Student Conference in Logic, April 2003
Computable Euclidean Domains:
Southern Wisconsin Logic Colloquium, October 2012
It's All Relative, Except When It's
Not: Cornell Logic Seminar, September 2012
Computable Structure Theory of
Uncountable Linear Orders: Cornell Logic Seminar, September 2012
The Complexity of Computable
Categoricity: Notre Dame Logic Seminar, April 2012
Decidability and Undecidability of Theories of Classes
of Structures:
Southern Wisconsin Logic Colloquium, December 2011
Computable Categoricity and Relative Computable Categoricity:
University of Waterloo, March 2011
Computable Euclidean Functions and Euclidean Domains:
University of Waterloo, March 2011
Jump Degrees of Countable Structures:
Southern Wisconsin Logic Seminar, November 2010
Computable Structure Theory of Uncountable Linear Orders:
CT Logic Seminar, September 2010
Effective Algebra of Uncountable Linear Orders:
University of Auckland, April 2010
Euclidean Domains and Euclidean Functions:
Victoria University of Wellington, March 2010
Effective Notions of Categoricity:
University of Auckland, February 2010
Embeddings of Computable Structures:
CUNY Logic Seminar, March 2009
Embeddings of Computable Structures:
Notre Dame Logic Seminar, January 2009
Cuts of Linear Orders:
Notre Dame Logic Seminar, January 2009
Embeddings of Computable Structures:
MIT Logic Seminar, October 2008
Embeddings of Computable Linear Orders:
Southern Wisconsin Logic Colloquium, March 2008
Embeddings of Computable Linear Orders:
Dartmouth Logic Seminar, February 2008
Invariants of Boolean Algebras (Part I and Part II):
CT Logic Seminar, February 2008
Boolean Algebras and Ketonen Invariants:
University of Chicago Logic Seminar, November 2007
Boolean Algebras:
UConn SIGMA Seminar, October 2007
Characterizing the Computable Structures:
Southern Wisconsin Logic Colloquium, May 2007
Characterizing the Computable Depth Zero Boolean Algebras:
Notre Dame Logic Seminar, April 2006