I've been reading Girard et al's 'Proofs and Types', which in Chapter 6 presents a proof of strong normalisation for the simply typed lambda calculus with products and base types. The proof is based on Tait's method of defining a set of 'reducible terms for type $T$' by induction on the type $T$. For example a term $t$ is reducible for type $A\to B$ if for all reducible $u$ for type $A$, $t\,u$ is reducible for type $B$.


However I don't see how to extend this proof to (binary) sums, which are covered in a later chapter, because the elimination for sums involves a 'parasitic' type which prevents one from defining reducible terms of type $A+B$ via the elimination by induction on $A+B$.


How (if at all) does this proof style extend to sums? I can't find a good reference that presents this.



How to handle sums in Tait's reducibility proof of strong normalisation?
The typical strategy when you're building a model to perform normalisation by evaluation (i.e. the computational part of Tait's method, see [1]) with sum types is to have as a semantics for `A + B`:


* either the semantics of `A`
* or the semantics of `B`
* or a neutral term of type `A + B` (i.e. a head variable with a spine of eliminators)


This makes it possible for the proof to go through. I'd wager that the same strategy works for the proof of SN. In other words, your reducibility candidate $R\_{A+B}(t)$ would be:


* either $t \leadsto^\* \texttt{inl}(a)$ and $R\_A(a)$
* or $t \leadsto^\* \texttt{inr}(b)$ and $R\_B(b)$
* or $t \leadsto^\* \textit{ne} = x(t\_1)\dots(t\_n)$ and $SN(\textit{ne})$


[1] [COQUAND, T., & DYBJER, P. (1997). Intuitionistic model constructions and normalization proofs. Mathematical Structures in Computer Science, 7(1), 75-94.](https://www.cambridge.org/core/journals/mathematical-structures-in-computer-science/article/div-classtitleintuitionistic-model-constructions-and-normalization-proofsdiv/15AE4B790FF9E4B1998CE92054DBD3CF)


