| my mathematics |
My academic family tree (compliments of Chris Alfeld).
Papers (Published, Accepted, and Submitted)

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

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.

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.

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.

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



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



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 ω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
(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 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.

Papers (In Preparation)

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

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 Δ0n+1-categorical but not Δ0n-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.

Invited Conference Talks


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

Selected Seminar Talks


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

 
 

© 2011 Asher Kach