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, then alphabetically by coauthor.
A Feiner Look at the Intermediate Degrees
(In preparation)
With Hirschfeldt and Montalbán
Abstract. We say a set S is &Delta0(n)(X) if membership of n in S is a &Delta0n question, uniformly in n. A set X is low for Δ-Feiner if every set S that is &Delta0(n)(X) is also &Delta0(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 &Delta0(bn+a)(X), &Sigma0(bn+a)(X), or &Pi0(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.
Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains
(To Appear in JSL)
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 of Mathematical Logic, 47:3 (2008), 211-219)
Abstract. The main result is that for sets S &sube &omega+1,
the following are equivalent:
(1) The shuffle sum &sigma(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) &le 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
&Sigma02 sets.
Depth Zero Boolean Algebras
(To Appear in TAMS)
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.
&Delta02-Categoricity of Equivalence Structures
(Submitted)
With Turetsky
Abstract. We exhibit computable equivalence structures, one &Delta02-categorical and one not &Delta02-categorical, having unbounded character, infinitely many infinite equivalence classes, and no s1-function. This offers a natural example where &Delta02-categoricity and relative &Delta02-categoricity differ.
Effective Notions of Categoricity
(In preparation)
With Day, Downey, Lempp, Ng, and Turetsky
Abstract. We study the relationship between computable categoricity and relative categoricity and index sets related to these notions.
Limitwise Monotonic Functions and Applications
(In preparation)
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.
Embeddings of Computable Structures
(Submitted)
With Levin and Solomon
Abstract. We study what the existence of a classical embedding between computable structures implies about the complexity of such embeddings.
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 &eta into computable non-scattered linear orders and embeddings of &omega* 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.
Automatic Linear Orders
(In progress)
With Minnes
Abstract. We study automatic linear orders, particularly issues of categoricity, homogeneity, and complexity of suborders.
Linear Orders and Descending Cuts
(In preparation)
With Montalbán
Abstract. We study the connection between how much (little) information the isomorphism type of a linear order can encode and the order type of its ascending and descending cuts.
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
(Submitted)
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.
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 &omega+1; and provide continuum many examples of depth &omega, rank one Boolean algebras. Effectively, I show for sets S &sube &omega+1 with greatest element, the depth zero Boolean algebras Bu(S) and Bv(S) are computable if and only if S\{&omega} is &Sigma0n&rarr 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 &omega+1 have computable copies. Additionally, I show that the notions of limitwise monotonic functions relative to 0' and limit infimum functions coincide.
Embeddings of Computable Structures:
Australian Math Society Annual Meeting, September 2009
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:
ASL Annual Meeting, March 2008
Embeddings of Computable Linear Orders:
SWLC Seminar, March 2008
Embeddings of Computable Linear Orders:
Dartmouth Logic Seminar, February 2008
Boolean Algebras:
UConn SIGMA Seminar, October 2007
Boolean Algebras and Ketonen Invariants:
Novosibirsk, August 2007
Characterizing the Computable Structures: Boolean Algebras and Linear Orders:
SWLC Seminar, May 2007
Atoms: The Building Blocks of Nature (Boolean Algebras):
GSCL Annual Meeting, April 2007
Reverse Mathematics and Vector Spaces":
GPSLogic Seminar, February 2007
Shuffle Sums:
GSCL Annual Meeting, April 2006
Characterizing the Computable Depth Zero Boolean Algebras:
Notre Dame Logic Seminar, April 2006
Non-Standard Models of Arithmetic:
GSCL Annual Meeting, May 2004
The Smiley Face Theorem: Lindstrom's First Theorem:
GSCL Annual Meeting, April 2003