An increasingly common phenomena in combinatorics is the use of higher order notions, objects and principles to prove combinatorial facts about the natural numbers N (or some other countable set) and its subsets. One particularly fruitful such notion has been that of (nonprincipal) ultrafilters on N. These results provide a challenge to the analysis of the inherent complexity of such second order theorems in terms of the axioms (of second order arithmetic) needed to prove them and the computational complexity of the objects whose existence are asserted by such theorems. The study of such questions of complexity in general is the realm of reverse mathematics and recursion theory.
We will briefly discuss several different approaches to this topic that use tools from set theory (forcing and inner models), proof theory and combinatorics (recursion theoretic and set theoretic).