Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Pell equations and weak regularity priciples


Speaker: Charalampos Cornaros
Slot: Array, 11:00-11:20, col. 5

Abstract

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