An Elementary Proof of Strong Normalization for Atomic F

Abstract

We give an elementary proof (in the sense that it is formalizable in Peano arithmetic) of the strong normalization of the atomic polymorphic calculus F_{at} (a predicative restriction of Girard’s system F).