The Omega Rule is ${\mathbf{\Pi }}_1^1$-Complete in the $\lambda \beta$-Calculus

Benedetto Intrigila, Richard Statman

In a functional calculus, the so called Ω-rule states that if two terms P and Q applied to any closed term <i>N</i> return the same value (i.e. PN = QN), then they are equal (i.e.…