Skip navigation

The proof by Frank Fu which I mentioned in my last post was missing an important lemma: non-emptiness of the set \textit{Red}_T, for all simple types T.  This was pointed out in a comment to that post, by Chris Casinghino.  Frank has added the proof of this property to a revised version of the proof, as an additional property CR 4.  The step case of the induction for CR 1 (stating that reducible terms are closed and strongly normalizing) needs to choose an element of \textit{Red}_{T_1}, and so must appeal to IH(CR 4) for the fact that such an element exists.

Now the question I would want to know is, if we extended this particular proof to System F, would the reducibility candidates have to be defined as satisfying CR 4?  Since this is needed for CR 1, one would presume the answer is yes.  This would quite worrisome for some proofs (e.g., the one in Girard’s Proofs and Types), where \textit{Red}_T is a set of terms of type T — and of course, System F has types which are uninhabited in the empty context (contradicting CR 4).  But in the proof Frank has done, reducible terms need not be typable.  So perhaps requiring CR 4 would not be a problem.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: