University of Connecticut

Events Calendar

Connecticut Logic Seminar
Lowness of the Pigeonhole Principle
Benoit Monin (Creteil University)

Monday, November 4, 2019
4:45pm – 6:00pm

Storrs Campus
MONT 214

Given a coloring $c:\omega \rightarrow \{0, 1\}$, there must be, by the Pigeonhole principle, an infinite set $X$ such that $c$ assigns the same color to every element of $X$. This rather easy theorem is known as the $\mathrm{RT^1_2}$ principle in reverse mathematics : An instance of $\mathrm{RT^1_2}$ is a coloring $c:\omega \rightarrow \{0, 1\}$, and a solution of this instance is an infinite set $X$ whose every element are assigned the same color via $c$.

We study the general question of the computational power of $\mathrm{RT^1_2}$: Given a notion of computational strength, that is, an upward closed class $\mathcal{C}$ in the Turing degree, can we build an instance $c$ of $\mathrm{RT^1_2}$ such that every solution to $c$ is a member of $\mathcal{C}$? The general paradigm is that $\mathrm{RT^1_2}$ has very little computational power. For almost every known natural notion of computational strength $\mathcal{C}$, it is known that $\mathrm{RT^1_2}$ is low for this notion : for every instance $c$ of $\mathrm{RT^1_2}$, there is a solution of $c$ which is not a member of $\mathcal{C}$.

One of the first of these result is that for any non computable set $X$ and any instance $c$ of $\mathrm{RT^1_2}$, one solution of $c$ does not compute $X$ (Dzhafarov and Jockusch). To show this, the authors designed a special forcing notion : the computable Mathias forcing, with which one can control the truth of $\Sigma^0_1$ statements. Later, Monin and Patey designed a new forcing notion, that builds upon computable Mathias forcing, in order to control the truth of $\Sigma^0_2$ statements. This lead to the following result : for every instance $c$ of $\mathrm{RT^1_2}$, there is a solution of $c$ which is not of high degree, that is whose jump does not compute the double jump.

Later the same authors could obtain a generalization of this forcing in two ways : the first one to control the truth of $\Sigma^0_\alpha$ statements for $\alpha$ a computable ordinal, and the second one by "iterating" the forcing within product spaces, in order to obtain non-cohesive solutions, leading a separation of the reverse mathematical principles $\mathrm{RT^2_2}$ and $\mathrm{SRT^2_2}$.


Reed Solomon,

Connecticut Logic Seminar (primary), UConn Master Calendar

Control Panel