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.

**CLASSICAL COMPUTABILITY THEORY**

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.

**EFFECTIVE ALGEBRA and COMPUTABLE MODEL THEORY**

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) =
*liminf* _{s} 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) =*lim

_{t}

*g(x,t)*enumerates

*S*.

Other results discuss the relationship between these sets and the Σ

^{0}

_{3}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**.

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 *G _{S} := ⊕_{n ∈ S}
Q_{pn}* for sets

*S*⊆ω. We show that

*G*has a decidable copy if and only if

_{S}*S*is Σ

^{0}

_{2}and has a computable copy if and only if

*S*is Σ

^{0}

_{3}.

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 Δ^{0}_{2}-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.

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).

Decidability and Undecidability of the Theories of Classes of Structures

(Submitted)

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.

*Δ ^{0}_{2}*-Categoricity of Equivalence Structures

(New Zealand Journal of Mathematics, 39 (2009), 143-149)

With Turetsky

Abstract. We exhibit computable equivalence structures, one *Δ ^{0}_{2}*-categorical and one
not

*Δ*-categorical, having unbounded character, infinitely many infinite equivalence classes, and no

^{0}_{2}*s*

_{1}-function. This offers a natural example where

*Δ*-categoricity and relative

^{0}_{2}*Δ*-categoricity differ.

^{0}_{2}

**REVERSE MATHEMATICS**

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 WKL_{0} over RCA_{0}, and that the existence
of an infinite dimensional nontrivial proper subspace of such a vector
space is equivalent to ACA_{0} over RCA_{0}.

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.

**OTHER COMPUTATIONAL PARADIGMS**

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
*ω ^{CK}_{1}*
and larger countable ordinals are not. We show that perfect local computability
also fails for uncountable ordinals, and that ordinals

*α ≥ ω*are

^{CK}_{1}*θ*-extensionally locally computable for all

*θ < ω*, but not when

^{CK}_{1}*θ > ω*, nor when

^{CK}_{1}*θ = ω*.

^{CK}_{1}≤ α < ω^{CK}_{1}˙ ωComputability and Uncountable Linear Orders

(Submitted)

With Greenberg, Lempp, and Turetsky

Abstract. We study the effective algebra of linear orders within the
domain ω_{1}. In particular, we study degree spectra,
computably categorical linear orders, and the successor relation.

**BOOLEAN ALGEBRAS (CLASSICALLY)**

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.

**OTHER WRITINGS**

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 &omega 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
*B*_{u(S)} and *B*_{v(S)} are computable if and
only if *S*\{ω} is Σ^{0}_{n→ 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.

Computing a Ryll-Nardzewski Function

(In preparation)

With Andrews

The Ryll-Nardzewski Theorem shows that every ℵ_{0}-categorical
theory has a Ryll-Nardzewski function which assigns to every *n* the finite
number of *n*-types in *T*. We examine, for an
ℵ_{0}-categorical theory *T*, the complexity of computing or
dominating a Ryll-Nardzewski function. We show that there is a computable
ℵ_{0}-categorical structure *M* so that whenever *g*
dominates the Ryll-Nardzewski function of *M*, the function *g*
computes 0^{(ω+1)}. This is as complicated as possible, since the
Ryll-Nardzewski function of *T* is always computable in *T'*.

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 Δ

^{0}

_{n}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 low

_{n}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.

Classical and Effective Categoricity

(In preparation)

With Khoussainov and Melnikov

Abstract. We exhibit, for each *n > 0*, both
ℵ_{0}-categorical and ℵ_{1}-categorical,
computable structures that are Δ^{0}_{n+1}-categorical but not Δ^{0}_{n}-categorical.

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