Editing Lambda cube (section)

===λ2===

In λ2, such terms can be obtained as<math display="block">\vdash (\lambda \beta : * . \lambda x : \bot . x \beta) : \Pi \beta : * . \bot \to \beta</math>with <math display="inline">\bot = \Pi \alpha : * . \alpha</math>. If one reads <math display="inline">\Pi</math> as a universal quantification, via the Curry-Howard isomorphism, this can be seen as a proof of the principle of explosion. In general, λ2 adds the possibility to have [[Impredicativity|impredicative]] types such as <math display="inline">\bot</math>, that is terms quantifying over all types including themselves.<br />The polymorphism also allows the construction of functions that were not constructible in λ→. More precisely, the functions definable in λ2 are those provably total in second-order [[Peano arithmetic]].<ref>{{cite book |first1=Jean-Yves |last1=Girard |first2=Yves |last2=Lafont |first3=Paul |last3=Taylor |title=Proofs and Types |publisher=Cambridge University Press |year=1989 |isbn=9780521371810 |volume=7 |series=Cambridge Tracts in Theoretical Computer Science }}</ref> In particular, all primitive recursive functions are definable.