Proof & Computation

The Ramsey theorem was the first example of a natural result escaping the Big Five phenomenon, which had so far identified every result to have equivalent strength to one of five classical axiomatic bases. It has since then been thoroughly studied, and we present a form of generalization of said theorem, as "Ramsey like" theorems. A Ramsey like theorem is of the form: "For every k-coloring of n-tuples of integers, there exists an infinite set avoiding a set of finite patterns P". Depending on the properties of the patterns in P, these results have vastly different strengths. In particular, we will use the notions of preservation of hyperimmunity (or hyperimmunities) and 2-dimensional hyperimmunity as strength quantifiers, and find necessary and sufficient conditions for the patterns in P for each to hold. We also study Ramsey-like theorems that don't ask to avoid every pattern in P, but at least one. We also see colorings as graphs and prove the existence of a computable infinite graph of which every computable subgraph contains every possible finite subgraph.

In this talk we investigate what happens when we take concepts from computable structure theory and forbid the use of unbounded search. In other words, we discuss the primitive recursive content of computable structure theory. The central definition is that of punctual structures, introduced by Kalimullin, Melnikov and Ng in 2017. A common theme is that new techniques are required in the primitive recursive analogue of computable structure theory concepts. We also discuss a degree structure within punctual presentations which is induced by primitive recursive isomorphisms. This degree structure is a new concept that does not arise in computable structure theory.