This project involves research in computability theory (recursion theory) and its connection with other areas of mathematics, especially combinatorics and algebra. A particular focus will be Ramsey's theorem from combinatorics, which asserts the existence of infinite sets which are homogeneous with respect to certain partitions. Methods from computability theory will be used to analyze the complexity of these homogeneous sets relative to the complexity of the partition, both for single partitions and families of partitions. Also, the logical strength of various versions of Ramsey's theorem and related principles will be studied, again largely using the methods of computability theory. Other topics of investigation include the conditions under which a Boolean algebra has a computable copy and the conditions under which a group has a finitely presented expansion.
The purpose of this work is to achieve a better understanding of what can in principle be computed and of relationships among noncomputable sets of numbers. Many proofs of mathematical results show the existence of certain sets without giving a procedure (or algorithm) for determining membership in the sets. This work involves an attempt to come as close as possible to giving an algorithm. This is closely related to finding what axioms are needed to prove the result and finding the consequences of the result. The particular result this work is centered on, Ramsey's theorem, states, roughly speaking, that in the midst of patterns which may be very complicated, there must be patterns which are very simple. However, it may be impossible to compute where the simple patterns occur, even when the original complicated patterns can be computed. In this work, the possibilities for finding optimally simple descriptions of the places where the pattern is simple will be investigated, as well as the consequences that can be obtained from various versions of Ramsey's theorem in restricted logical systems.
