Damir D. Dzhafarov

Department of Mathematics University of Connecticut (Estados Unidos)



Computable combinatorics: the past, present, and future

Early on in the history of computability theory, it was noticed that the subject can be applied to study the effectivity not just of subsets of the natural numbers but also of various classes of mathematical theorems. This has taken on many forms over the years, from effective mathematics to computable structure theory to reverse mathematics. One especially prominent class of theorems in this endeavor are those that have the form of PI1/2 statements of second-order arithmetic, or more generally, the form for every set X of numbers, there is a set Y with certain properties. The effective study of these theorems has been especially fruitful in the realm of combinatorics, giving rise to a highly active industry of research. I will survey some of the work in this area, from the pioneering results of Jockusch in the 1970s on Ramseys theorem, through the ongoing investigation in reverse mathematics of so-called irregular principles, and into some of the exciting new directions of research being opened up by interactions between computable combinatorics and computable analysis. Along the way, I will mention a number of open problems.


Damir Dzhafarov obtuvo su doctorado en 2011 de la Universidad de Chicago bajo la supervisión de Denis Hirschfeldt, Antonio Montalbán y Robert Soare.

Realizó una estancia postdoctoral con beca de la NSF en la Universidad de Notre Dame y en la Universidad de California, Berkeley, antes de unirse al Departamento de Matemáticas de la Universidad de Connecticut, donde es Director Asociado del Grupo de Lógica Filosófica y Matemática en Connecticut.

Su investigación es en las áreas de teoría de la computabilidad, matemática inversa, combinatoria eficaz y el análisis computable. También ha trabajado en el desarrollo de aplicaciones de la lógica a otras disciplinas, incluyendo filosofía de las matemáticas y ciencia cognitiva.