Logical Approaches to Computational Barriers

Pell equations and weak regularity priciples

Speaker:
| Charalampos Cornaros |

Slot: |
Array, 11:00-11:20, col. 5 |

We study the strength of weak forms of the Regularity Principle in the presence of $IE_1$ (induction on bounded existential formulas) relative to other subsystems of $PA$. In particular, the Bounded Weak Regularity Principle is formulated, and it is shown that when applied to $E_1$ formulas, this principle is equivalent over $IE_1^-$ to $I\Delta_0+exp$.

websites: Arnold Beckmann | 2008-05-19 |